:::: 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.