Quel est le moyen le plus simple d’implémenter bigint en C?

J’essaie de calculer 100!

Je cherche le moyen le plus simple d’accomplir cela avec C. J’ai lu mais je n’ai pas trouvé de réponse concrète.

Si vous devez savoir, je programme en Xcode sous Mac OS X.

Merci!

    Si vous cherchez une bibliothèque simple, libtommath (de libtomcrypt) est probablement ce que vous voulez.

    Si vous souhaitez écrire vous-même une implémentation simple (soit comme exercice d’apprentissage, soit parce que vous n’avez besoin que d’un sous-ensemble très limité de fonctionnalités bigint et que vous ne voulez pas vous baser sur une dépendance à une grande bibliothèque, la pollution de l’espace de noms, etc.) , alors je pourrais suggérer ce qui suit pour votre problème:

    Comme vous pouvez lier la taille du résultat en fonction de n , pré- uint32_t simplement un tableau de uint32_t de la taille requirejse pour contenir le résultat. J’imagine que vous voudrez imprimer le résultat. Il est donc logique d’utiliser une base d’une puissance de 10 (c’est-à-dire une base de 1 000 000) plutôt que d’une puissance de 2. Autrement dit, chaque élément de votre tableau est autorisé. contenir une valeur comprise entre 0 et 999999999.

    Pour multiplier ce nombre par un entier n (normal, non grand), procédez comme suit:

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

    Si vous savez que n ne sera jamais supérieur à 100 (ou à un autre nombre petit) et que vous souhaitez éviter d'entrer dans la plage 64 bits (ou si vous êtes sur une plate-forme 64 bits et souhaitez utiliser uint64_t pour votre tableau bigint) , faites alors à la base une puissance inférieure à 10 pour que le résultat de la multiplication tienne toujours dans le type.

    Maintenant, imprimer le résultat est juste quelque chose comme:

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

    Si vous voulez utiliser une puissance de 2 comme base, plutôt qu'une puissance de 10, la multiplication devient beaucoup plus rapide:

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

    Cependant, imprimer votre résultat en décimal ne sera pas si agréable ... 🙂 Bien sûr, si vous voulez le résultat en hexadécimal, alors c'est facile:

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

    J'espère que cela t'aides! Je vais laisser d'autres choses (comme l'addition, la multiplication de 2 bigints, etc.) comme exercice pour vous. Réfléchissez simplement à la façon dont vous avez appris à faire l'addition, la multiplication, la division, etc. en base 10 à l'école primaire et enseignez à l'ordinateur comment faire cela (mais en base 10 ^ 9 ou base-2 ^ 32 à la place) et vous devriez pas de problème.

    Si vous êtes prêt à utiliser une bibliothèque, la norme semble être GMP.

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

    devrait calculer 100! de regarder les docs.

    Vous pouvez également utiliser OpenSSL bn ; il est déjà installé sous Mac OS X.

    Vous avez demandé le moyen le plus simple de procéder. Alors, voilà:

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

    J’ai testé ce code et il donne la bonne réponse.