fattoriale 10000 in C

Question

#include <stdlib.h> 
#include <stdio.h> 

struct node; 
typedef struct node* PtrToNode; 

struct node { 
    long long n; 
    PtrToNode next; 
}; 

PtrToNode factorial(int n, PtrToNode init); 
void multiply(long long n, PtrToNode init, long long carry); 

int main() { 
    int n; 
    while (1) { 
    scanf("%d", &n); 
    if (n > 0) { 
     break; 
    } else if (n == 0){ 
     printf("1\n"); 
     return 0; 
    } else { 
     printf("Retry.\n"); 
    } 
    } 
    PtrToNode init = malloc(sizeof(struct node)); 
    init->n = 1; 
    init->next = NULL; 
    PtrToNode head = factorial(n, init); 
    PtrToNode tail = reverse(head); 
    PtrToNode backup = tail; 
    printf("%lld", tail->n); 
    tail = tail->next; 
    while(tail != NULL) { 
    printf("%04lld", tail->n); 
    tail = tail->next; 
    } 
    PtrToNode t; 
    while (backup != NULL) { 
    t = backup; 
    backup = backup->next; 
    free(t); 
    } 
} 


PtrToNode factorial(int n, PtrToNode init) { 
    for (int i = 1; i <= n; i++) 
    multiply(i, init, 0); 
    return init; 
} 

void multiply(long long n, PtrToNode init, long long carry) { 
    long long temp = n * init->n + carry; 
    init->n = temp % 10000; 
    carry = temp/10000; 
    if (init->next != NULL) { 
    multiply(n, init->next, carry); 
    } else if (carry > 0) { 
    init->next = malloc(sizeof(struct node)); 
    init->next->n = carry; 
    init->next->next = NULL; 
    } else { 
    return; 
    } 
} 

Questa è la mia funzione per calcolare 10000 fattoriale e ho calcolato la risposta corretta rispetto ai dati online. Ma, quando limito l'intervallo di n a [0.999], non riesco nemmeno a calcolare il fattoriale del 2000. Perché quando trasformo l'intervallo n per [0, 9999], allora può calcolare 2000! anche 10000 !?

Answer 1

Il problema con la limitazione del cluster di cifre a tre cifre è che la moltiplicazione di un numero a tre cifre di un valore superiore a 1.000 può produrre un carry in cifra numero quattro.

Sebbene questo non crei un problema immediato, l'errore si accumula man mano che si porta il valore nella catena di calcolo. Con oltre 5.000 cifre nel risultato del 2000! l'overflow del carry produrrebbe certamente un errore visibile nel risultato. Questo succede intorno al 1258 ° passo del calcolo del 2000 !.

Questo non accade con i cluster a quattro cifre e 10.000 perché l'unico posto in cui il carry potrebbe "riversarsi" nella cifra successiva è il calcolo dell'ultimo cluster, e long long ha molto spazio per ospitare questo senza un troppo pieno.