Calculando el factorial de un entero pequeño en tiempo de compilación

Question

Acabo de implementar (una vez más) una plantilla recursiva para calcular el factorial de un entero en tiempo de compilación (¿quién hubiera pensado que algún día realmente lo necesitaría). Aún así, en lugar de lanzar el mío, fui a Boost en busca de una respuesta. Sin embargo, la función factorial en matemáticas especiales específicamente prohíbe su uso con tipos enteros, así que solo escribí la mía.

Aún así, ¿hay alguna otra función en Boost que deba usar? ¿Debería convertir mi número entero al double y usar la función boost::factorial? ¿El cálculo se realiza en tiempo de compilación?

Answer 1

No es necesario Boost, esto es sólo 1-liner si tiene C++ 11:

constexpr uint64_t factorial(uint64_t n) { 
    return n == 0 ? 1 : n * factorial(n-1); 
} 

y funcionará incluso si su arg no es compilar constante de tiempo también. uint64_t funcionará con n < 21.

Si lo hace en tiempo de compilación y se multiplica con un valor de coma flotante, no habrá gastos generales de conversión (la conversión también será en tiempo de compilación).

Answer 2

Dado que hay un número limitado de factoriales que pueden caber dentro de un número entero, puede precalcular los primeros 20 valores a mano y almacenarlos en una matriz global o estática. A continuación, utilizar una función global o estática para buscar el factorial de la matriz:

#include <iostream> 

const int factorials[] = 
{ 
    1, 
    1, 
    2, 
    6, 
    24, 
    // etc... 
}; 

inline const int factorial(int n) {return factorials[n];} 

int main() 
{ 
    static const int fourFactorial = factorial(4); 
    std::cout << "4! = " << fourFactorial << "\n"; 
} 

Si utiliza un literal como argumento para factorial, entonces el compilador simplemente debe sustituir la llamada de función con el resultado (cuando está habilitada la optimización) He intentado el ejemplo anterior en XCode 4.4 (en una Mac) y I ver en el conjunto que inicializa fourFactorial con la constante 24:

.loc 1 20 38 ## /Users/emile/Dev/sandbox/sandbox/main.cpp:20:38 
movl $24, __ZZ4mainE13fourFactorial(%rip) 

Este método puede resultar en la compilación más rápido que mediante el uso recursivo tiempo de compilación trucos.