¿Cómo se pueden escribir algoritmos de cálculo de precisión arbitraria para aplicaciones de teoría de números?

Answer 1

Las siguientes bibliotecas son de interés para el cálculo de multiprecisión:

• La biblioteca C La biblioteca GNU MPFR. Es de alta calidad y tiene redondeo exacto, es decir, encuentra el decimal correcto. Tiene una serie de encapsulaciones C ++.
• La biblioteca C La biblioteca GNU MP Bignum tiene un módulo de multiprecisión original, pero creo que es reemplazado por otras versiones.
• La biblioteca C Arb 2.3.0 con funciones elementales más rápidas ofrece cálculo de multiprecisión que es más rápido que MPFR.
• Los principales sistemas de álgebra computacional, es decir, Maple, Mathematica, Magma, Pari, tienen su propia biblioteca multiprecisión de calidad variable.
• El C GCC libquadmath ofrece un cálculo de precisión cuádruple que puede ser interesante cuando la doble precisión no es suficiente pero una precisión mayor es exagerada.

Matlab podría ser la peor opción posible porque solo tiene aritmética de doble precisión.

Answer 2

¿Qué tan pequeña tolerancia tendría sentido para un solucionador de doble precisión?

Está buscando específicamente cadenas de herramientas que admitan cálculos de precisión arbitrarios, el ARPREC de Bailey es uno para C ++.

Necesita tipos, estructuras y clases que puedan manejar aritmética prec variable y necesita escribir algos solucionadores originales para manejar esos tipos.

Mire aquí para ver ejemplos y una caja de herramientas de matlab comercial: Advanpix – Referencia de funciones

Implementación ARPREC en matlab: Krougly, Jeffrey-Implementación y aplicación de prec extendido en matlab. El artículo no es muy útil, pero las referencias sí.

Caja de herramientas ARPREC original de Bailey para C ++ – Directorio de software de alta precisión

Y los estándares de precisión IEEE: punto flotante IEEE. Esto no es solo un problema con Matlab.

También es interesante el artículo muy agradable de Bruce Dawson: Comparación de números de coma flotante

Y, por supuesto, esto: Goldberg: lo que todo científico de la computación debe saber sobre la aritmética de flotador-1991

Answer 3

Puede usar estos lenguajes de programación:
pitón- 9.4. decimal – Aritmética decimal de punto fijo y coma flotante – Documentación de Python 2.7.8
Java: clase Java.math.BigDecimal

Estas bibliotecas se instalan de forma predeterminada en la instalación del SDK de sus respectivos idiomas. Casi todos los lenguajes tienen múltiples bibliotecas de precisión arbitraria, como c ++ tiene The GNU MP Bignum Library.
Apfloat es una biblioteca simple disponible para c ++ y Java. (Aunque es un poco viejo pero funciona de maravilla) Página de inicio de Apfloat

Puede usar Google para encontrar una biblioteca para una biblioteca de precisión arbitraria en casi cualquier idioma que desee.

Answer 4

Estoy seguro de que tendrá muchas respuestas prácticas a su pregunta.
Pero quizás te interese más cómo funciona detrás de la pantalla.

Bueno, en los viejos tiempos (el tiempo pre-C), estábamos acostumbrados a hacerlo manualmente, reemplazando un real por una matriz [matemáticas] x = (x_1, x_2, …, x_n) [/ matemáticas] y escribiendo piezas de algoritmos como los que aprendiste en la escuela. Para calcular z = x + y, por ejemplo, codificaría algo como

llevar = 0
para k = n hacia abajo 0
z [k] = x [k] + y [k] + llevar
llevar = 0
si z [k]> = 1000 entonces
z [z] = z [k] -1000
llevar = 1
terminara si
siguiente k

Por supuesto, esto se habría escrito con goto lugar de for loops y, de if then else . Además, los índices pueden ser algo difíciles de programar, pero algunos de mis amigos obtuvieron una reputación respetuosa por su habilidad para elegir y mover conjuntos de tarjetas perforadas de forma rápida y segura con una experiencia impresionante.

Es un ejercicio instructivo escribir los mismos algoritmos para multiplicación (fácil con un doble bucle) y división (trabajo cerebral garantizado).

No creo que CAS (Mapple, matematica), ni las bibliotecas BigNumber (C ++, java, Python, …) funcionen mucho mejor. De hecho, después de un rápido vistazo en el código, puedo decirte que BigDecimal de Java no. Excepto que la n es variable y puede ser controlada por una precisión en lugar de por el número de dígitos.

Entonces, sea cual sea el paquete que elija, encontrará un ejemplo del tipo [matemáticas] 1/9 = 0.1111111 … [/ matemáticas], por lo tanto, [matemáticas] 9 * (1/9) = 0.999999 \ neq 1 [/ matemáticas]. Es suficiente reemplazar 9 por uno menos que el número base ([matemática] 2 ^ n [/ matemática] para la n apropiada). Los sistemas CAS son más difíciles de engañar porque se simplifican antes para realizar la aproximación, pero siempre se encuentra una fórmula para la cual la aproximación está más allá de su capacidad.

En el aspecto práctico, nunca, nunca termine un algoritmo en una condición como [matemática] x = 0 [/ matemática] o [matemática] x = y [/ matemática] a menos que las variables estén definidas estáticamente como enteros. Siempre use algo como [matemáticas] \ left | xy \ right | <\ epsilon [/ math].

Answer 5

Como Mathieu Dutour sugirió, GNU MPFR hace aritmética de precisión arbitraria.

Si desea escribir el suyo propio, represente el número como una matriz de enteros de precisión fija, y sume / reste / multiplique / divida como aprendió en la escuela primaria, llevándolo y reduciéndolo a una serie de operaciones en un solo fijo entero de precisión

Sin embargo, GNU MPFR agrega otras optimizaciones que importan cuando obtienes MUCHOS bits, agregando FFT (transformación rápida de Fourier) y otros trucos para acelerarlo. GNU MPFR utiliza diferentes métodos basados ​​en el número de bits en su número. Probablemente no podrá escribir una biblioteca mejor que GNU MPFR. Si desea usar un lenguaje que no sea C, probablemente sea mejor usar llamadas C externas a MPFR (por ejemplo, PHP hace esto).

Answer 6

Advanpix toolbox (Multiprecision Computing Toolbox for MATLAB) es la respuesta si está utilizando Matlab.

Es rápido (órdenes de magnitud más rápido que Matlab y Maple) y proporciona una funcionalidad avanzada (por ejemplo, eigenporoblems, matrices dispersas, etc.), inexistente en otras bibliotecas.

En cuanto a la teoría de números, proporcionamos las siguientes funciones con precisión arbitraria: factor, mcd, isprime, mcm, primos, nextprime y prevprime.

Descargo de responsabilidad. Soy autor de la caja de herramientas :).