Qual è il modo più semplice di implementare bigint in C?

Sto cercando di calcolare 100!

Sto cercando il modo più semplice per realizzare questo utilizzando C. Ho letto in giro ma non ho trovato una risposta concreta.

Se devi sapere, programma in Xcode su Mac OS X.

Grazie!

    Se stai cercando una libreria semplice, libtommath (da libtomcrypt) è probabilmente quello che vuoi.

    Se stai cercando di scrivere una semplice implementazione tu stesso (o come esercizio di apprendimento o perché hai solo bisogno di un sottoinsieme molto limitato di funzionalità bigint e non vuoi fare affidamento su una dipendenza da una grande biblioteca, inquinamento da spazi dei nomi, ecc.) , quindi potrei suggerire quanto segue per il tuo problema:

    Poiché è ansible limitare la dimensione del risultato in base a n , è sufficiente pre-allocare un array di uint32_t della dimensione richiesta per contenere il risultato. Immagino che vorrai stampare il risultato, quindi ha senso usare una base che abbia una potenza di 10 (cioè di base 1000000000) piuttosto che una potenza di 2. Vale a dire che ogni elemento dell’array è permesso per mantenere un valore compreso tra 0 e 999999999.

    Per moltiplicare questo numero per un n (normale, non grande) intero, fai qualcosa come:

     uint32_t carry=0; for(i=0; i 

    Se sai che n non sarà mai più grande di 100 (o qualche altro piccolo numero) e vuoi evitare di entrare nella gamma a 64 bit (o se sei su una piattaforma a 64 bit e vuoi usare uint64_t per il tuo array bigint) , quindi rendere la base una potenza inferiore di 10 in modo che il risultato della moltiplicazione si adatti sempre al tipo.

    Ora, la stampa del risultato è qualcosa del tipo:

     printf("%lu", (long)big[len-1]); for(i=len-1; i; i--) printf("%.9lu", (long)big[i-1]); putchar('\n'); 

    Se vuoi usare una potenza di 2 come base, piuttosto che una potenza di 10, la moltiplicazione diventa molto più veloce:

     uint32_t carry=0; for(i=0; i> 32; } if (carry) big[len++] = carry; 

    Tuttavia, stampare i risultati in decimali non sarà così piacevole ... 🙂 Ovviamente se vuoi il risultato in hex, allora è facile:

     printf("%lx", (long)big[len-1]); for(i=len-1; i; i--) printf("%.8lx", (long)big[i-1]); putchar('\n'); 

    Spero che questo ti aiuti! Lascerò l'implementazione di altre cose (come aggiunta, moltiplicazione di 2 battute, ecc.) Come esercizio per te. Ripensa a come hai imparato a fare l'aggiunta, la moltiplicazione, la divisione, ecc. Di base 10 nella scuola elementare e insegnare al computer come farlo (ma in base 10 ^ 9 o base-2 ^ 32 invece) e dovresti non avere problemi

    Se sei disposto ad utilizzare un’implementazione di libreria, quella standard sembra essere GMP

     mpz_t out; mpz_init(out); mpz_fac_ui(out,100); mpz_out_str(stdout,10,out); 

    dovrebbe calcolare 100! dal guardare i documenti.

    Puoi anche usare OpenSSL bn ; è già installato in Mac OS X.

    Hai chiesto il modo più semplice per farlo. Quindi, ecco qui:

     #include  #include  int main(int argc, char** argv) { mpz_t mynum; mpz_init(mynum); mpz_add_ui(mynum, 100); int i; for (i = 99; i > 1; i--) { mpz_mul_si(mynum, mynum, (long)i); } mpz_out_str(stdout, 10, mynum); return 0; } 

    Ho provato questo codice e dà la risposta corretta.