Obliczanie silni małej liczby całkowitej w czasie kompilacji

Question

Właśnie zaimplementowałem (jeszcze raz) szablon rekurencyjny do obliczania silni liczby całkowitej w czasie kompilacji (kto by pomyślał, że pewnego dnia będę go potrzebować!). Jednak zamiast przetaczać własne, poszedłem do Boost szukając odpowiedzi. Jednak funkcja silni w specjalnej matematyce wyraźnie zabrania jej używania z typami całkowitymi, więc napisałem własną.

Nadal czy jest jeszcze inna funkcja w Boost, której powinienem użyć? Czy powinienem rzucić moją liczbę całkowitą na double i użyć funkcji boost::factorial? Czy obliczenia wykonywane są w czasie kompilacji?

Answer 1

Nie trzeba Boost to tylko 1-liner, jeśli masz C++ 11:

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

i będzie działać, nawet jeśli arg nie jest zbyt stały czas kompilacji. uint64_t będzie działał z n < 21.

Jeśli robisz to w czasie kompilacji i mnożysz z wartością zmiennoprzecinkową - nie będzie żadnych kosztów konwersji (konwersja będzie również w czasie kompilacji).

Answer 2

Ponieważ istnieje ograniczona liczba silni, które mieszczą się wewnątrz liczby całkowitej, można wstępnie wstępnie obliczyć pierwsze 20 wartości ręcznie i zapisać je w globalnej lub statycznej tablicy. Następnie za pomocą funkcji globalnego lub statyczne do wyszukiwania silni w tablicy:

#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"; 
} 

Jeśli używasz dosłownym jako argument do factorial, to kompilator powinien po prostu zastąpić wywołanie funkcji z wynikiem (po optymalizacji jest włączona). Próbowałem powyższy przykład w Xcode 4.4 (na komputerze Mac) i widzę w zespole, który inicjuje fourFactorial ze stałą 24:

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

Metoda ta może skutkować szybszym kompilacji niż za pomocą rekurencyjnego kompilacji wydziwianie.