10000 silni w 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; 
    } 
} 

To jest moja funkcja do obliczania 10000 silni i obliczyłem poprawną odpowiedź w porównaniu do danych online. Ale kiedy ograniczę zakres n do [0,999], nie mogę nawet obliczyć 2000 silnia. Dlaczego, gdy przekształcam zakres n na [0, 9999], to można obliczyć 2000! nawet 10000 !?

Answer 1

Problem z ograniczeniem klastra cyfr do trzech cyfr polega na tym, że pomnożenie trzycyfrowej liczby przez wartość powyżej 1000 może spowodować przeniesienie na cyfrę czwartą.

Mimo że nie powoduje to natychmiastowego problemu, błąd będzie kumulowany w miarę przenoszenia wartości w łańcuchu obliczeń. Z ponad 2000 cyfr w wyniku 2000! przepełnienie przeniesienia z pewnością spowoduje widoczny błąd w wyniku. Dzieje się to około 1258-tego kroku obliczeń 2000 !.

Nie dzieje się tak z czterocyfrowymi klastrami i 10 000, ponieważ jedynym miejscem, w którym przeniesienie może "rozlać się" na następną cyfrę, jest obliczenie ostatniego klastra, a long long ma dużo miejsca, aby pomieścić to bez przelewowy.