Calcolo fattoriale di grandi numeri in C

Nel mio codice C, voglio calcolare il fattoriale per i numeri compresi tra 1 e 100. Per i numeri piccoli, la funzione funziona, ma per numeri più grandi, ad esempio 100! restituisce risultati errati. Qualsiasi modo per gestire fattoriali di grandi numeri in C ?. L’im del compilatore che usa è gcc v4.3.3. Il mio codice è il seguente:

#include  #include  double print_solution(int); int main(void) { int no_of_inputs,n ; int ctr = 1; scanf("%d",&no_of_inputs); //Read no of inputs do { scanf("%d",&n); //Read the input printf("%.0f\n",print_solution(n)); ctr++; }while(ctr <= no_of_inputs); return 0; } double print_solution(int n) { if(n == 0 || n == 1) return 1; else return n*print_solution(n-1); } 

Nessun tipo di dati C standard gestirà con precisione numeri pari a 100 !. La tua unica opzione se usare aritmetica di interi arbitrari di precisione , sia attraverso una libreria che da te stesso.

Se questo è solo un progetto per hobby, ti suggerisco di provarlo tu stesso. È una specie di esercizio divertente. Se questo è legato al lavoro, usa una libreria preesistente.

Il più grande tipo di dati C che si ottiene normalmente è un numero intero a 64 bit. 100! è nell’ordine di 10 157 , che prende la parte migliore di 500 bit da memorizzare con precisione come numero intero.

100 fattoriale è enorme, per essere precisi è 93326215443944152681699238856266700490715968264381621468592963895217 59999322991560894146397615651828625369792082722375825118521091686400 00000000000000000000.

Forse dovresti usare una libreria di bignum come GMP . Ha dei bei documenti, un’interfaccia abbastanza coerente, velocità e se sei su Linux, la tua distribuzione probabilmente ha un pacchetto (penso che il mio lo installa di default)

Per calcolare approssimativamente i fattoriali di grandi numeri puoi procedere in questo modo:

 n!  = n * (n-1)!
 quindi log (n!) = log (n) + log (n-1!)

Ora puoi usare la programmazione dynamic per calcolare log (n!) E calcolare
n! come (base) ^ (valore di registro)

Se non vuoi usare una libreria bigint, il meglio che puoi fare con stdlib è usare long double e tgammal() da math.h :

 long double fact(unsigned n) { return tgammal(n + 1); } 

Questo ti porterà a 100! con una precisione di 18 decimali su x86 (cioè long double 80 bit).

Un’implementazione esatta non è poi così complicata:

 #include  #include  #include  void multd(char * s, size_t len, unsigned n) { unsigned values[len]; memset(values, 0, sizeof(unsigned) * len); for(size_t i = len; i--; ) { unsigned x = values[i] + (s[i] - '0') * n; s[i] = '0' + x % 10; if(i) values[i - 1] += x / 10; } } void factd(char * s, size_t len, unsigned n) { memset(s, '0', len - 1); s[len - 1] = '1'; for(; n > 1; --n) multd(s, len, n); } int main(void) { unsigned n = 100; size_t len = ceill(log10l(tgammal(n + 1))); char dstr[len + 1]; dstr[len] = 0; factd(dstr, len, n); puts(dstr); } 

Tutti ti stanno dicendo la risposta corretta, ma un paio di altri punti.

  1. L’idea iniziale di utilizzare una doppia per ottenere una gamma più ampia non funziona perché una doppia non può memorizzare questi dati con precisione. Può fare i calcoli ma con un sacco di arrotondamenti. Questo è il motivo per cui esistono librerie di bigint.

  2. So che questo è probabilmente un esempio di un tutorial o di un sito di esempi, ma fare una ricorsione illimitata ti morderà a un certo punto. Hai una soluzione ricorsiva per ciò che è essenzialmente un processo iterativo. Capirai perché questo sito è chiamato così com’è quando provi ad eseguire il tuo programma con valori più grandi (Prova 10000).

Un semplice approccio iterativo è il seguente

  int answer, idx; for (answer = 1, idx = 1; idx < = no_of_inputs; idx++ ) { answer = answer * idx; } printf("Factorial of %3d = %d\n", no_of_inputs, answer); 

questo è quello che ho fatto per risolvere un indovinello di google alcuni anni fa, usa la libreria GMP http://gmplib.org/ :

 #include  #include "gmp.h" void fact(mpz_t r,int n){ unsigned int i; mpz_t temp; mpz_init(temp); mpz_set_ui(r,1); for(i=1;i< =n;i++){ mpz_set_ui(temp,i); mpz_mul(r,r,temp); } mpz_clear(temp); } int main(void) { mpz_t r; mpz_init(r); fact(r,188315); /* fact(r,100); */ gmp_printf("%Zd\n",r); mpz_clear(r); return(0); } 

gcc -lgmp -o fact fact.c

./fatto

potresti provare ad andare per il tipo “unsigned long long”, ma questo è il massimo che puoi ottenere con i tipi integrati. Suggerirei (come già detto da Cletus) di procedere con un’implementazione nota di grandi numeri o di scriverne uno da soli. “è un bel esercizio” x 2.

Se si desidera utilizzare solo i tipi di dati standard e non è necessaria la risposta esatta, calcolare il logaritmo di n! invece di n! si. Il logaritmo di n! si adatta facilmente in un double (a meno che n sia enorme).

Qualche modo di gestire fattoriali di grandi numeri in C?

Poiché i fattoriali possono superare rapidamente il range degli interi standard a larghezza fissa e persino dei tipi a virgola mobile come il double , Code dovrebbe considerare un tipo di utente che consente una precisione esatta illimitata per una risposta esatta .

Esistono varie librerie di precisione a interi interi, ma se il codice richiede una soluzione semplice, prendere in considerazione l’uso di una stringa .

Il sotto non è veloce, né memore dei limiti delle matrici, eppure è un esempio dell’idea. La conversione di '0'-'9' in / da 0-9 così dispendiosa, tuttavia ciò consente un facile debug passo dopo passo.

 #include  #include  #include  static char *strfact_mult(char *s, unsigned x) { unsigned sum = 0; size_t len = strlen(s); size_t i = len; while (i > 0) { sum += (s[--i] - '0') * x; s[i] = sum % 10 + '0'; sum /= 10; } while (sum) { len++; memmove(&s[1], s, len); s[i] = sum % 10 + '0'; sum /= 10; } return s; } char *str_fact(char *dest, unsigned n) { strcpy(dest, "1"); while (n > 1) { strfact_mult(dest, n--); } return dest; } void test_fact(unsigned n) { char s[1000]; printf("%3u %s\n", n, str_fact(s, n)); } int main(void) { test_fact(0); test_fact(4); test_fact(54); test_fact(100); } 

Produzione

  0 1 4 24 54 230843697339241380472092742683027581083278564571807941132288000000000000 100 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000 

Immagino che sia perché si sta traboccando il range int, che è fino a ca. 2 miliardi. È ansible ottenere fino a 4 miliardi se si utilizza unsigned int, ma oltre a questo è necessario utilizzare la libreria bigint .

100! = 933262154439441526816992388562667004907159682643816214685929 6389521759999322991560894146397156518286253697920827223758251185210 916864000000000000000000000000

Non puoi rappresentare un numero così grande con un int o un lungo.

Questo è certamente dovuto al trabocco. Hai bisogno di un modo per rappresentare grandi numeri ( unsigned long long . Non unsigned long long nemmeno coprirai fino a 25!).

Oltre al consiglio degli altri, suggerirei di familiarizzare con i limiti di archiviazione dei tipi di base (int, long, long long, …) per qualsiasi computer / piattaforma in uso. (“In caso di dubbio, stampa di più!”)

Un poster precedente faceva riferimento a un limite di precisione di 80 bit, ma questo è tipico di una CPU x86.

Un’altra persona ha citato più volte ISO C90, sebbene C99 sia l’ultimo standard; anche se molti compilatori non hanno completamente implementato C99, probabilmente scoprirai che molto probabilmente hanno almeno un supporto per molto tempo, che dovrebbe corrispondere a> = precisione a 64 bit.

Calcola i grandi fattori senza alcuna libreria esterna

È davvero un vecchio problema. Vedo la maggior parte delle risposte che suggeriscono una libreria esterna o un risultato approssimativo , mostrando limiti di memoria. Ma, pensate in modo leggermente diverso: non è sempre necessario usare integer o double o unsigned long long in programmazione per fare matematica!


Ho usato int[] per calcolare i Big Factorials . Questo piccolo codice Java può (teoricamente) scoprire fattoriale di qualsiasi numero

 public class BigFactorial { public static int[] calculateFactorial(int inputNumber) { int[] factorial = initializeFactorial(inputNumber); for(int i=inputNumber-1, j, k; i>0; i--){ for(j=factorial.length-1, k=0; factorial[j] >= 0; j--){ k += i*factorial[j]; factorial[j] = k%10; k /= 10; } factorial[j] = k%10; k /= 10; factorial[j-1] = k; for(j=0; factorial[j]<1; j++){ factorial[j] = -1; } } return factorial; } private static int[] initializeFactorial(int inputNumber){ int digits = (int) Math.ceil(inputNumber*Math.log10(inputNumber/2))+2; int[] factorial = new int[digits+1]; for(int i=0; i0; j--){ factorial[j] = i%10; i /= 10; } return factorial; } public static void showOutput(int[] factorial){ int i=0; while(factorial[i]<1){ i++; } for(; i 

Non utilizzare l’algoritmo ricorsivo, penso, è super lento, anche se è memorizzato nella cache sarà lento. Questo è solo qualcosa che dovresti prendere in considerazione.

La ragione di ciò è quando chiamate fact (100) in realtà non lo eseguite 100 volte, effettivamente eseguite quella funzione 5050 volte. Il che è male, se è memorizzato nella cache, potrebbe essere 100 volte, tuttavia è ancora più lento eseguire una chiamata di funzione con istruzioni if ​​per eseguire un ciclo.

 double print_solution(int n) { double rval = 1; unsigned int i; for( i = 1; i < = n; i++ ) { rval *= i; } return rval; } 

Usando l'aritmetica con precisione in arbitario potresti farlo andare molto in alto, tuttavia, devi usare una libreria per farlo, oppure puoi creare la tua libreria, ma ci vorrebbe molto tempo per farlo.