¿Cuál es la forma más simple de implementar bigint en C?

¡Estoy tratando de calcular 100!

Estoy buscando la forma más sencilla de lograr esto con C. He leído pero no he encontrado una respuesta concreta.

Si debe saberlo, programo en Xcode en Mac os X.

¡Gracias!

Si está buscando una biblioteca simple, libtommath (de libtomcrypt) es probablemente lo que quiere.

Si está buscando escribir una implementación simple usted mismo (ya sea como un ejercicio de aprendizaje o porque solo necesita un subconjunto muy limitado de la funcionalidad de Bigint y no desea agregar una dependencia a una biblioteca grande, contaminación del espacio de nombres, etc.) , entonces podría sugerirle lo siguiente para su problema:

Como puede vincular el tamaño del resultado en función de n , simplemente asigne previamente una matriz de uint32_t del tamaño requerido para contener el resultado. Supongo que querrá imprimir el resultado, por lo que tiene sentido usar una base con una potencia de 10 (es decir, base 1000000000) en lugar de una potencia de 2. Es decir, cada elemento de su matriz está permitido para mantener un valor entre 0 y 999999999.

Para multiplicar este número por un entero n (normal, no grande), haga algo como:

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

Si sabes que n nunca será mayor que 100 (o algún otro número pequeño) y quieres evitar entrar en el rango de 64 bits (o si estás en una plataforma de 64 bits y quieres usar uint64_t para tu matriz bigint) , luego haga que la base tenga una potencia menor de 10 para que el resultado de la multiplicación siempre encaje en el tipo.

Ahora, imprimir el resultado es algo así como:

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

Si desea utilizar una potencia de 2 como base, en lugar de una potencia de 10, la multiplicación es mucho más rápida:

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

Sin embargo, imprimir el resultado en decimal no será tan agradable ... 🙂 Por supuesto, si quieres el resultado en hexadecimal, entonces es fácil:

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

¡Espero que esto ayude! Dejaré implementar otras cosas (como la sum, la multiplicación de 2 bigints, etc.) como ejercicio para ti. Solo piense en cómo aprendió a hacer la adición de base 10, la multiplicación, la división, etc. en la escuela primaria y enséñele a la computadora cómo hacerlo (pero en su lugar es base-10 ^ 9 o base-2 ^ 32) y debería no tienes problema

Si está dispuesto a usar una implementación de biblioteca, la estándar parece ser GMP

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

debería calcular 100! de mirar los documentos.

También puede usar OpenSSL bn ; ya está instalado en Mac OS X.

Usted pidió la forma más sencilla de hacer esto. Entonces, aquí tienes:

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

Probé este código y me da la respuesta correcta.

    Intereting Posts