¿Cuál es la forma más sencilla de implementar Bigint en C?

Question

Estoy tratando de calcular 100!

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

Si debes saberlo, yo programo en Xcode en Mac OS X.

¡Gracias!

Answer 1

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

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

Ya que puede limitar el tamaño del resultado basado en n , simplemente preasigne una matriz de uint32_t del tamaño requerido para mantener el resultado. Supongo que querrá imprimir el resultado, así que tiene sentido usar una base con una potencia de 10 (es decir, una base de 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<len; i++) {
    uint64_t tmp = n*(uint64_t)big[i] + carry;
    big[i] = tmp % 1000000000;
    carry = tmp / 1000000000;
}
if (carry) big[len++] = carry;

Si sabe que n nunca será mayor que 100 (o algún otro número pequeño) y desea evitar ir al rango de 64 bits (o si está en una plataforma de 64 bits y desea utilizar uint64_t para su matriz de uint64_t ) , luego haga que la base tenga una potencia menor de 10 para que el resultado de la multiplicación siempre se ajuste al tipo.

Ahora, imprimir el resultado es algo como:

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

Si quieres usar una potencia de 2 como base, en lugar de una potencia de 10, la multiplicación se vuelve mucho más rápida:

uint32_t carry=0;
for(i=0; i<len; i++) {
    uint64_t tmp = n*(uint64_t)big[i] + carry;
    big[i] = tmp;
    carry = tmp >> 32;
}
if (carry) big[len++] = carry;

Sin embargo, imprimir tu 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é la implementación de otras cosas (como la suma, la multiplicación de 2 bigints, etc.) como un ejercicio para usted. Simplemente recuerde cómo aprendió a hacer la suma, la multiplicación, la división, etc. de base-10 en la escuela primaria y enseñe a la computadora cómo hacerlo (pero en cambio, en base-10 ^ 9 o base-2 ^ 32) y debería no tengo problema

Answer 2

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

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

debe calcular 100! De mirar los documentos.

Answer 3

También puede utilizar OpenSSL bn ; Ya está instalado en Mac OS X.

Answer 4

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

#include <gmp.h>
#include <stdio.h>

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

He probado este código y da la respuesta correcta.