Estoy buscando una buena biblioteca matemática de precisión arbitraria en C o C ++. ¿Podría darme algunos consejos o sugerencias?
Los requisitos principales:
Se debe manejar arbitrariamente grandes números enteros, mi interés principal está en números enteros. En caso de que no sepa qué significa la palabra arbitrariamente grande, ¡imagine algo como 100000! (el factorial de 100000).
No es necesario especificar la precisión durante la inicialización de la biblioteca o la creación del objeto. La precisión solo debe estar limitada por los recursos disponibles del sistema.
Se debe utilizar todo el poder de la plataforma, y debe manejar números “pequeñas” de forma nativa. Eso significa que en una plataforma de 64 bits, el cálculo (2 ^ 33 + 2 ^ 32) debería utilizar las instrucciones de CPU de 64 bits disponibles. La biblioteca no debería calcular esto de la misma manera que lo hace con (2 ^ 66 + 2 ^ 65) en la misma plataforma.
Se debe manejar de manera eficiente adición (
+), resta (-), multiplicación (*), la división de enteros (/), el resto (%), de potencia (**), incremento (++), decremento (--), GCD, factorial, y otra común número entero cálculos aritméticos. La capacidad de manejar funciones como la raíz cuadrada y el logaritmo que no producen resultados enteros es una ventaja. La capacidad de manejar cálculos simbólicos es aún mejor.
Esto es lo que encontré hasta ahora:
Java 's BigInteger y BigDecimal clase: He estado usando estos hasta el momento. He leído el código fuente, pero no entiendo las matemáticas subyacentes. Puede estar basado en teorías y algoritmos que nunca aprendí.
El tipo de entero integrado o en las bibliotecas centrales de bc , Python , Ruby , Haskell , Lisp , Erlang , OCaml , PHP , algunos otros lenguajes: he usado algunos de estos, pero no tengo idea de qué biblioteca están usando, o qué tipo de implementación están usando.
Lo que ya he sabido:
Use
charpara dígitos decimales ychar*para cadenas decimales, y realice cálculos en los dígitos usando unforbucle.Usar
int(olong int, olong long) como una "unidad" básica y una matriz de ese tipo como un entero largo arbitrario, y hacer cálculos sobre los elementos usando unfor-loop.Usar un tipo de entero para almacenar un dígito decimal (o algunos dígitos) como BCD (decimal codificado en binario) .
Lo que no se:
- Imprimir la matriz binaria mencionada anteriormente en decimal sin utilizar métodos ingenuos. Un ejemplo de un método ingenuo: (1) sume los bits del más bajo al más alto: 1, 2, 4, 8, 16, 32,… (2) use una
char*-string mencionada anteriormente para almacenar los resultados decimales intermedios).
Lo que aprecio:
Buenas comparaciones en GMP , MPFR , decNumber (u otras bibliotecas que son buenas en su opinión).
Buenas sugerencias sobre libros y artículos que debería leer. Por ejemplo, una ilustración con cifras sobre cómo funciona un algoritmo de conversión de binario a decimal no ingenuo sería bueno. El artículo " Conversión binaria a decimal con precisión limitada " de Douglas W. Jones es un ejemplo de un buen artículo.
Cualquier ayuda en general.
Por favor, no responder a esta pregunta si usted piensa que el uso double(o long double, u long long double) puede resolver este problema fácilmente. Si cree que sí, no comprende el problema en cuestión.
fuente
Respuestas:
GMP es la opción popular. Squeak Smalltalk tiene una biblioteca muy agradable, pero está escrito en Smalltalk.
Solicitó libros o artículos relevantes. La parte complicada de los bignums es la división larga. Recomiendo el artículo de Per Brinch Hansen, Multiple-Length Division Revisited: A Tour of the Minefield .
fuente
char *(cada unocharrepresenta un dígito decimal) o unaint *cadena BCD ( cada unointrepresenta 4/8/16 dígitos BCD). Sin embargo, me pregunto si las bibliotecas de nivel de producción del mundo real imitan el "método de papel y lápiz", ya que es demasiado lento.100,000,000,000,000,000 / 333,333,333,333: El primer paso es comparar100,000,000,000con333,333,333,333. Debido a que el primero es menor que el segundo, el cálculo simplemente pasa al siguiente dígito. El segundo paso es encontrar el cociente de1,000,000,000,000 / 333,333,333,333, esto implica una multiplicación de prueba y error de333,333,333,333 * 1(y* 2,* 3y* 4), o hacer restas sucesivas en un ciclo. ¿Ves lo lento que es? Creo que existen algoritmos más eficientes.En general, la biblioteca de precisión arbitraria de propósito general más rápida es GMP . Si desea trabajar con valores de punto flotante, consulte la biblioteca MPFR . MPFR se basa en GMP.
Con respecto al soporte nativo de precisión arbitraria en otros lenguajes, Python usa su propia implementación debido a razones de licencia, tamaño del código y portabilidad del código. El módulo GMPY permite a Python acceder a la biblioteca GMP.
fuente
Consulte TTMath , una pequeña biblioteca con plantilla que solo incluye encabezados y es gratuita para uso personal y comercial.
fuente
No he comparado bibliotecas aritméticas de precisión arbitraria entre sí, pero las personas que sí parecen haberse decidido de manera más o menos uniforme por las GMP. Por lo que vale, los números enteros de precisión arbitraria en GHC Haskell y GNU Guile Scheme se implementan utilizando GMP, y la implementación más rápida del punto de referencia pidigits en el tiroteo de idiomas se basa en GMP.
fuente
¿Y Pari ? Está construido sobre GMP superior y proporciona todas las demás ventajas sobre las operaciones de teoría de números que necesitará (y muchas cosas de cálculo simbólico).
fuente