Seguro que cuando has estudiado algo de programación, uno de los primeros ejemplos que te han mostrado para explicarte la recursividad, ha sido el cálculo de un factorial.
Si alguna vez hiciste pruebas, habrás podido comprobar que hay una diferencia de rendimiento entre la versión recursiva y la versión iterativa.
Si preguntas a ChatGPT sobre cómo optimizar el método del cálculo de un factorial, te expondrá diferentes formas:
- Usando programación dinámica.
- Usando paralelización, agrupando productos.
- Usando aproximaciones, como la Fórmula de Stirling.
Pero… ¿Hay alguna optimización posible para acelerar el cálculo de un factorial sin usar paralelización o aproximaciones?
¡La respuesta es sí!
Y es mediante el cálculo de diferencias de cuadrados desde el número central.
Tomando el siguiente ejemplo:
7! = 1 * 2 * 3 *4 * 5 * 6 * 7
Se pueden agrupar pares de productos desde el número central, que es 4, tal que:
Los pares de productos (4 * 4), (3 * 5), (2 * 6) y (1 * 7) son en realidad las diferencias de cuadrados (4² – 0²), (4² – 1²), (4² – 2²) y (4² – 3²).
Teniendo en cuenta la identidad (n + 1)² = n² + 2n + 1, la acumulación de los sucesivos cuadrados desde 1 en adelante, puede ser calculada mediante desplazamientos binarios a la izquierda y sumas de 1.
De esta forma, se pueden ir hallando cada uno de los términos a multiplicar, y así lograr reducir el número de multiplicaciones a prácticamente la mitad.
En el caso de que el factorial a calcular sea de un número par, se necesitará una multiplicación adicional, ya que en ese caso el número central no es entero.
Una implementación en código podría ser la siguiente:
using System.Numerics;
namespace UnravelEngineering;
public static class Optimizations
{
public static BigInteger SqDifferenceFactorial(BigInteger pNumber)
{
if (pNumber < BigInteger.Zero)
{
throw new InvalidOperationException();
}
BigInteger result = BigInteger.One;
if (pNumber > BigInteger.One)
{
result = (BigInteger.One + pNumber) >> 1;
BigInteger nextProductGroup = result * result;
BigInteger maxIndex = result - BigInteger.One;
for (BigInteger index = BigInteger.Zero; index < maxIndex; index++)
{
nextProductGroup -= ((index << 1) + BigInteger.One);
result *= nextProductGroup;
}
if (pNumber.IsEven)
{
result *= pNumber;
}
}
return result;
}
}
Tras realizar una comparativa del cálculo del factorial para el número 100.000 usando .NET 9, se han obtenido los siguientes resultados para el método iterativo clásico y este nuevo método optimizado:
- Método iterativo clásico: 8,1399627 segundos.
- Método optimizado: 4,0596316 segundos.
Esta diferencia de tiempo revela que el rendimiento del método optimizado es aproximadamente el doble frente al del método iterativo clásico.
Mediante esta optimización, se siguen manteniendo las ventajas del método iterativo:
- Es adaptable al uso de factoriales calculados.
- Es paralelizable.
Como siempre: nuestra misión es buscar la excelencia.