:::: MENU ::::

Llevemos el factorial al extremo

En este post vamos a utilizar como lenguaje C#, Scala y PHP, no obstante sería posible hacerlo con otros lenguajes con sus correspondientes librerías de BigInteger.

Si habéis hecho cualquier curso, universitario, por internet, etc; para practicar recursividad, siempre se suele plantea el siguiente ejercicio:

Haga un método recursivo para calcular n! (n factorial).

Cuando se nos plantea el ejercicio, siempre hacemos algo así:

public static UInt32 Fact(UInt32 n)
{
    if (n < 2)
        return 1;
    return n * Fact(n - 1);
}

Tenemos un UInt32 llamado n, es decir, un int pero sin signo, de forma que no puede ser negativo, como argumento.
Si n es menor que 2, sabemos que 1! y 0! son 1, así que devolvemos 1 directamente.
De lo contrario, devolvemos n * (n-1)!.

«Bien, ya le he enseñado a hacer el ejercicio a mi alumna de repaso», pensé.
Pero luego empecé a darle vueltas a la cabeza; sé cuanto es el máximo para enteros de 32 bits, también el de 64 bits…
Sabía que los factoriales, al ser exponenciales, se dispararían en cuanto a dígitos se refiere, así que busqué en Google: «factorial de 1.000», «factorial de 2.000», «factorial de 3.000″… Así hasta llegar a 10.000, numero posterior al cual no encontré resultados…

En ese momento yo y mi curiosidad, y aprovechando que mi alumna utilizaba C#, me propuse calcular todos los factoriales de 0! a 1.000.000! (simplemente por curiosidad) con la librería BigInteger.

public static BigInteger Fact(BigInteger n)
{
    if (n < 2)
        return 1;
    return n * Fact(n - 1);
}

Sí, era fácil adaptarlo… El problema fue que al ponerlo en práctica descubrí que haciéndolo recursivamente llegaba a un límite muy por debajo de lo esperado, en concreto alrededor de 7.000!, ya que depende del tamaño de la pila de llamadas del sistema, y esta no es muy grande (en mi caso), por lo que hacerlo de esta forma no era la solución.

StackOverflowException

Si bien es cierto que se puede cambiar el límite de la pila (en Unix suele ser mayor por defecto) y algunos compiladores podrían hacerlo con saltos, no es el caso, así que optaremos por un clásico bucle for.

A la función que nos devuelve el Factorial sin recursividad, la llamaremos NRFact(n).

public static BigInteger NRFact(UInt32 n)
{
    BigInteger r = 1;
    for (; n > 1; n--)
        r *= n;
    return r;
}

Si nos fijamos, es un simple for que va decrementando n y multiplicándolo por r en cada iteración, siendo este inicialmente 1.
El bucle for no tiene inicializador ya que n per se es el valor inicial.

Con esto ya podemos calcular factoriales enormes. Necesita cierto tiempo para calcular valores grandes, ya que tiene que iterar muchas veces y el proceso de multiplicación es más costoso de forma exponencial conforme aumentemos n.

No obstante, yo no quería quedarme ahí, así que decidí hacer un programa que calculase los factoriales de 0 a 1.000.000 y, de esa forma, poder mostrarlos luego en una página web, o de la forma deseada, pues calcularlos es costoso y podemos necesitarlos de forma más rápida, así que decidí guardarlos como documentos de texto plano cuyo nombre era el valor a factorializar.

Aquí entraba en cuestión el que las memorias secundarias (como es el caso de un SSD) no son comparables de ninguna forma en cuanto a velocidad con las primarias (como puede ser la RAM), por lo que se crea un gran cuello de botella, y tarda muchísimo más en guardar el resultado en disco que calcularlo en sí.

O eso pensé yo al obtener tiempos de más de 6 segundos… Hasta que pasé mi código de C# a Scala, es decir, ejecutado en la Java Virtual Machine y utilizando el IO de Java, y pasó de 6 segundos a escasos 100 milisegundos por archivo escrito.
Diréis que en C# hay diferentes alternativas y así es, probé muchísimas alternativas para escribir los archivos, incluso intenté hacerlo asíncrono o crear 8 threads escribiendo un archivo por vez… Pero no mejoró en absoluto.

Diferencia Milisegundos/archivo guardado.
Menor es mejor.

Es importante recalcar que ambos tardan 0 milisegundos en calcular cada factorial (al menos en los números que se manejan ahora), la diferencia es puramente en sus librerías de I/O y/o rendimiento.

Por ello, os dejo el código completo para ir generando los Factoriales y guardarlos en .txt en Scala:

package main

import java.math.BigInteger
import java.io._

object Factorial {
  def main(args: Array[String]): Unit = {
    var r = new BigInteger("1")
    for(i <- 1 to 1000000) {    // Aquí ponemos el valor límite a calcular
      val startTime = System.currentTimeMillis
      r = r multiply new BigInteger(i.toString)

      val fileName = "C:\\Factorial\\" + i + ".txt";  // Aquí la ruta
      val file = new File(fileName)
      if(!file.exists) {
        file.createNewFile
        val writer = new BufferedWriter(new FileWriter(fileName))
        writer.write(r.toString)
        writer.close
      }

      println(i + " - " + (System.currentTimeMillis - startTime) + "ms")
    }
  }
}

Por petición popular, he traducido el código de Scala a Java pese a ser muy similares, pues de hecho las librerías utilizadas en Scala son las de Java y compilan ambos a Java Byte Code, por lo que el rendimiento será igual:

package main;

import java.math.BigInteger;
import java.io.*;

public class Factorial {
    public static void main(String[] args) throws IOException {
        BigInteger r = new BigInteger("1");
        for (int i = 0; i < 1000001; i++) {
            long startTime = System.currentTimeMillis();
            r = r.multiply(new BigInteger(String.valueOf(i)));

            String fileName = "C:\\Factorial\\" + i + ".txt";
            File file = new File(fileName);
            if (!file.exists()) {
                file.createNewFile();
                BufferedWriter writer = new BufferedWriter(new FileWriter(fileName));
                writer.write(r.toString());
                writer.close();
            }

            System.out.println(i + " - " + (System.currentTimeMillis() - startTime) + "ms");
        }
    }
}

Finalmente, también he traducido el código a PHP, con la librería BigInteger (cuyo manual podéis encontrar aquí) que podéis descargar haciendo click en el enclace:

<?php
require_once('BigInteger.php');
$r = new Math_BigInteger(1);
for($i = 1; $i < 1000001; $i++)
{
    $startTime = round(microtime(true) * 1000);
    $r = $r->multiply(new Math_BigInteger($i));
    
    $fileName = 'D:\\fact\\' . $i . '.txt';
    if(!file_exists($fileName))
    {
        $file = fopen($fileName, 'x');
        fwrite($file, $r->toString());
        fclose($file);
    }
    echo $i, ' - ', round(microtime(true) * 1000) - $startTime, "ms\n";
}

Edición
Por curiosidad, pese a que no tenía esperanza de superar a C# o Scala, probé a generar números para la página web en PHP (mi lenguaje favorito), y me llevé una grata sorpresa, pues es prácticamente unas 300 veces más rápido para guardar los archivos en disco que los otros lenguajes compilados (con todas las variantes que ya probé).

En la comparativa de C# vs Scala de arriba, se ve que tardaba mucho menos de 3 segundos (o 3.000ms) en 500.000! pero se debe a que el número ha crecido exponencialmente ya que así son los factoriales.

Si bien Scala (y C#) era ligeramente más rápido calculando el número (hablamos de que los factoriales se calculan en una cantidad irrisoria de milisegundos, y PHP también lo consigue), en guardarlo en HDD tardaba unos 3 segundos, PHP en cambio es capaz de guardarlo en tan solo ~150 milisegundos (para 750.000!) sin despeinarse.

Este último el script que estoy utilizando actualmente y aquí tenéis la prueba de que así es:

Tiempo de cálculo + guardado de PHP (unos 160ms)

Con el fin de poder visualizar los factoriales ya calculados por mi programa (cuyo objetivo es llegar a 1.000.000! gradualmente), podéis acceder al siguiente enlace.