Cómo codificar una solución para manejar números grandes?

Question

Estoy haciendo algunos problemas de Project Euler y la mayoría de las veces, los cálculos implican números mayores que int, flotante, doble, etc.

En primer lugar, sé que debería buscar formas más eficientes de cálculo para para evitar el gran problema numérico He oído hablar de las bibliotecas Bignum.

Pero, para los intereses académicos, me gustaría saber cómo codificar mi propia solución a este problema.

¿Puede algún experto ayudarme por favor? (Mi lenguaje es C)

Answer 1

Here's un módulo bignum agradable y simple para C. Puede aprender de él para obtener ideas. El código C no es de la más alta calidad, pero el algoritmo está bien implementado y es bastante común.

Para obtener información más avanzada, busque GMP.

Answer 2

Necesita almacenar los números grandes en una base que su computadora pueda manejar fácilmente con sus tipos nativos, y luego almacenar los dígitos en una matriz de longitud variable. Sugeriría que, para simplificar, empiece por almacenar los números en la base 10 solo para familiarizarse con la forma de hacerlo. Hará que la depuración sea mucho más fácil.

Una vez que tenga una clase que pueda almacenar los números de esta forma, es solo una cuestión de implementar las operaciones agregar, restar, multiplicar, etc. en esta clase. Cada operación tendrá que iterar sobre los dígitos de sus operandos y combinarlos, teniendo cuidado de transportarlos correctamente para que sus dígitos nunca sean más grandes que la base. La suma y la resta son simples. La multiplicación requiere un poco más de trabajo ya que el algoritmo ingenuo requiere bucles anidados. Luego, una vez que tenga ese funcionamiento, puede intentar implementar la exponenciación de una manera eficiente (por ejemplo, la cuadratura repetida).

Si está planeando escribir un serio implementación de bignum, base 10 no lo cortará. Es un desperdicio de memoria y será lento. Debe elegir una base que sea natural para la computadora, como 256 o el tamaño de la palabra (2 ** 32). Sin embargo, esto hará que las operaciones simples sean más difíciles, ya que obtendrá desbordamientos si agrega ingenuamente dos dígitos, por lo que tendrá que manejarlo con mucho cuidado.

Answer 3

Una manera simple es pensar en el número como su representación de cadena en la base b. Supongamos que b = 10, la operación aritmética simple como la suma en dos de tales cadenas se puede hacer usando el mismo método que usamos al agregar números con pluma y papel. Lo mismo ocurre con otras operaciones simples. Para obtener mejores resultados, puede tomar una base más grande.

Una simple implementación de bignum debería ser suficiente para la mayoría de los problemas de Project Euler (probablemente todo, pero no he resuelto demasiado en Euler, no estoy seguro), pero hay maneras de usar algoritmos mucho más rápidos para las operaciones como multiplicación y división/mod.

Aunque recomiendo escribir su propio bignum para la práctica, si está realmente atascado puede tomar ideas del código de bibliotecas bigint ya implementadas. Para una implementación seria, algo como gmp es la elección obvia. Pero también puede encontrar pequeños fragmentos codificados por otras personas cuando se resuelve un problema de práctica similar en línea (por ejemplo, el bigint.cpp de Abednego).

Answer 4

Si desea una versión nueva de C++ (lo sé, usted ha dicho C, pero esto es realmente código interesante), echar un vistazo a la parte interna de CGAL: http://www.cgal.org/

Answer 5

C no es una buena opción para el Proyecto Euler. Los beneficios de C son velocidad bruta, portabilidad de la máquina (hasta cierto punto, con C estándar), interoperabilidad del lenguaje (si algún idioma se comunica con otro, C es una primera opción popular), pegado a la API de una biblioteca o plataforma específica (porque C es común, por ejemplo, API de sistema operativo) y un lenguaje estable & stdlib. Ninguno de estos beneficios se aplica a resolver problemas de Project Euler. Ni siquiera la velocidad bruta, porque la mayoría de los problemas no se trata de cálculos crudos, sino de la comprensión del algoritmo requerido, y puede sentarse todo el día y esperar antes de la presentación.

Si está intentando problemas Proyecto Euler a ampliar su experiencia con C, que está perfectamente bien, sólo se dan cuenta de esta experiencia no se aplican necesariamente a proyectos del mundo real de larga duración y C puede trabajar.

Para este tipo de problema breve e irrepetible, los lenguajes comúnmente descritos como "lenguajes de scripting" funcionarán mejor, más rápido (en tiempo de desarrollo) y serán más fáciles. Pruebe Python, se mantiene cerca de C de muchas maneras, incluida una API C, y de entre los diversos "lenguajes de scripting" populares es posiblemente el que le resultará más útil junto con los proyectos C.

esto puede convertirse en una respuesta impopular, pero no es una queja — además me gusta mucho C y el uso de C/C++ menudo — y no hay una respuesta explícita aquí a su problema: "no utilice C", con su solución final de gran número dependiendo de la alternativa que elija. Nuevamente escogiendo Python, los enteros no tienen un límite superior (nota debajo), y yo uso esto para codificar de forma natural las respuestas a los problemas del Proyecto Euler, donde en otros idiomas tengo que usar una biblioteca de números alternativos dolorosos por comparación.

(enteros Python: Hay dos tipos de enteros en 2.x, 'int' y 'larga' (que han sido completamente unificado en 3.x) La conversión entre ellos es prácticamente sin fisuras, y 'de largo. 'permite valores arbitrariamente grandes, en lugar de simplemente ser un tipo' int 'más grande como C's long.)

Answer 6

Una popular biblioteca bignum para C/C++ es GNU MP Bignum Library. Lo he usado para varios problemas de Project Euler, pero sigue siendo cierto que C no es un lenguaje muy adecuado para los problemas de Euler. Si el rendimiento fuera más importante, C tendría más para ofrecer, pero ahora es mucho mejor que uses un lenguaje que incluye soporte para bignum, como Ruby (hay muchos otros).

Answer 7

Estoy totalmente de acuerdo con Roger Pate. He visto muchas veces que las personas corren un problema de límite entero con C/C++/Java, pero con Python, no es un problema. Para la mayoría de los problemas de Project Euler, es muy importante crear el algoritmo correcto y el rendimiento que obtiene de C no importará demasiado. Además, con los tipos de datos asociativos, el diccionario, el conjunto, etc. que están disponibles en Python y algunas de las bibliotecas incorporadas, itertools, solo para nombrar uno, es mucho más rápido resolver un problema con Python. Empecé a aprender Python en serio desde que salté al tren del Proyecto Euler y estoy contento con mi decisión (mi primer idioma es C++, el segundo idioma es Perl, pero quería aprender Python).