2013-04-08 9 views
5

Locandina prima volta qui, spero che questa domanda sia accettabile.Risposte diverse durante il calcolo fattoriale utilizzando l'iterazione e la ricorsione

Come piccolo test ho scritto un'applicazione che calcola il fattoriale di un numero utilizzando sia l'iterazione che la ricorsione. Questo sembrava funzionare bene, tranne quando si cerca di calcolare il fattoriale per i numeri maggiore di 24.

Per esempio, nel calcolo del fattoriale di 24 entrambi i metodi danno la risposta corretta di 62044840173323941.

Quando si calcola il fattoriale di 25 tuttavia, le risposte differiscono. Il metodo ricorsivo fornisce la risposta come 1.5511210043330986e + 025 mentre il metodo iterativo fornisce la risposta come 1.5511210043330984e + 025.

Secondo Wolfram Alpha la risposta corretta dovrebbe essere la stessa del metodo iterativo, quindi perché la discrepanza tra le funzioni? Ho chiesto ai miei colleghi e anche loro non sono in grado di spiegare il comportamento.

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

}

Grazie per la vostra considerazione.

+3

L'ho provato io stesso. Stesso risultato, anche notevole che i due numeri differiscono solo di un bit: 'Ricorsione: 15511210043330986055303168 [4529a940c33f6121]' e 'Iterazione: 15511210043330983907819520 [4529a940c33f6120]' – benzado

risposta

9

La versione ricorsiva calcola 5 * (4 * (3 * (2 * 1)))

La versione iterativa calcola 1 * (2 * (3 * (4 * 5)))

La differenza nell'ordine delle operazioni cambia il modo in cui i round aritmetici in virgola mobile generano un risultato diverso.

+2

Il motivo per cui il punto mobile è arrotondato in questo caso è perché il tipo 'double' può contenere solo fino a 15-17 cifre significative e 'n!'tendono ad avere molto più di 15-17 cifre in loro anche per valori relativamente piccoli di' n'. Wolfram | Alpha usa invece un metodo completamente diverso da 'double' quando si gestiscono questi tipi di quantità. –

2

L'ordine delle moltiplicazioni è diverso, dando risultati diversi a causa dell'arrotondamento in virgola mobile.

Se si cambia il ciclo for di andare 1-i (piuttosto che i-1), si dovrebbe ottenere lo stesso risultato dalla versione ricorsiva.

+0

Come sottolineato da Drew Dormann, in realtà non lo si potrebbe fare a meno che la transizione di memoria del registro <-> sia esattamente la stessa dopo la generazione del codice poiché i registri tendono (su architetture x86) ad avere una precisione migliore ... –

4

Il tipo double è not an exact type. Promette di essere un'approssimazione del valore corretto.

Quindi entrambe le implementazioni non sono garantite per essere esatte.

Man mano che le implementazioni sono interessati ci sono due fattori che potrebbero causare risposte diverse.

  1. si ordina la moltiplicazione in modo diverso.
  2. La versione iterativa esegue tutti i calcoli nella stessa variabile. Le architetture compatibili con Intel (x86 e x86-64) usano 80 bit di accuratezza nei loro registri a virgola mobile e tale accuratezza viene mantenuta fino a quando il registro non viene memorizzato.
+0

+1 per indicare il problema del registro , è un PITA che un'ottimizzazione (mantenendo la variabile in registro invece di rimetterla in memoria) può effettivamente cambiare il comportamento osservabile del programma :( –