Różne odpowiedzi podczas obliczania silni za pomocą iteracji i rekurencji

Question

Po raz pierwszy tutaj, mam nadzieję, że to pytanie jest do przyjęcia.

Jako mały test napisałem aplikację, która oblicza silnię liczby używając zarówno iteracji, jak i rekursji. To wydawało się działać dobrze z wyjątkiem, gdy próbuje obliczyć silnię dla numerów większy niż 24.

Na przykład podczas obliczania silni 24 obie metody dają właściwą odpowiedź 62044840173323941.

Podczas obliczania silni 25 jednak odpowiedzi różnią się. Metoda rekurencyjna podaje odpowiedź jako 1,5511210043330986e + 025, podczas gdy metoda iteracyjna daje odpowiedź jako 1,5511210043330984e + 025.

Zgodnie z Wolfram Alpha poprawna odpowiedź powinna być taka sama, jak metoda iteracyjna, więc dlaczego rozbieżności między funkcjami? Poprosiłem moich kolegów i oni również nie są w stanie wyjaśnić tego zachowania.

#define TEST_CASE 25 

double GetFactorialRecursive(double i) 
{ 
    if (i == 1) 
    return i; 
    else 
    return i * GetFactorialRecursive(i - 1); 
} 

double GetFactorialIterative(double i) 
{ 
    double result = 1.0; 
    for (; i > 0; --i) 
     result *= i; 
    return result; 
} 

int main() 
{ 
double recres = 0, itrres = 0; 
recres = GetFactorialRecursive(TEST_CASE); 
itrres = GetFactorialIterative(TEST_CASE); 

if (recres != itrres) 
    std::cout << "Error" << "\n"; 
std::cout << std::setprecision(25) << "Recursion: " << recres << ", Iteration: " << itrres << "\n"; 
return 0; 

}

Dziękuję za uwagę.

Answer 1

Wersja rekurencyjne oblicza 5 * (4 * (3 * (2 * 1)))

Wersja iteracyjnego obliczania 1 * (2 * (3 * (4 * 5)))

Różnica w kolejności operacji zmienia sposób arytmetyki ruchem zmiennoprzecinkowym, powodując inny wynik.

Answer 2

Kolejność mnożenia jest różna, dając różne wyniki z powodu zaokrąglania zmiennoprzecinkowego.

Jeżeli zmienisz pętlę for jechać z 1 do i (zamiast od i do 1), należy uzyskać taki sam wynik jak z wersji rekurencyjnej.

Answer 3

Typ double to not an exact type. Zapowiada się przybliżenie prawidłowej wartości.

Tak więc obie implementacje nie są gwarantowane.

W zależności od implementacji istnieją dwa czynniki, które mogą powodować różne odpowiedzi .

1. zamawiasz mnożenie w inny sposób.
2. Twoja wersja iteracyjna wykonuje całą matematykę w tej samej zmiennej. Architektury zgodne z architekturą Intel (x86 i x86-64) używają 80 bitów dokładności w swoich rejestrach zmiennoprzecinkowych, a dokładność ta jest zachowywana, dopóki rejestr nie zostanie zapisany w pamięci.