Aritmética de precisión arbitraria


De Wikipedia, la enciclopedia libre
Saltar a navegación Saltar a búsqueda

En informática , la aritmética de precisión arbitraria , también llamada aritmética bignum , aritmética de precisión múltiple o, a veces, aritmética de precisión infinita , indica que los cálculos se realizan en números cuyos dígitos de precisión están limitados solo por la memoria disponible del sistema host. Esto contrasta con la aritmética de precisión fija más rápida que se encuentra en la mayoría del hardware de unidades lógicas aritméticas (ALU), que generalmente ofrece entre 8 y 64 bits de precisión.

Varios lenguajes de programación modernos tienen soporte integrado para bignums, y otros tienen bibliotecas disponibles para matemáticas de punto flotante y enteros de precisión arbitraria . En lugar de almacenar valores como un número fijo de bits relacionados con el tamaño del registro del procesador , estas implementaciones suelen utilizar matrices de dígitos de longitud variable .

La precisión arbitraria se utiliza en aplicaciones donde la velocidad de la aritmética no es un factor limitante, o donde se requieren resultados precisos con números muy grandes. No debe confundirse con el cálculo simbólico proporcionado por muchos sistemas de álgebra computarizada , que representan números mediante expresiones como π · sin (2) y, por lo tanto, pueden representar cualquier número computable con precisión infinita.

Aplicaciones

Una aplicación común es la criptografía de clave pública , cuyos algoritmos comúnmente emplean aritmética con números enteros que tienen cientos de dígitos. [1] [2] Otro es en situaciones en las que los límites y desbordes artificiales serían inapropiados. También es útil para verificar los resultados de cálculos de precisión fija y para determinar valores óptimos o casi óptimos para los coeficientes necesarios en las fórmulas, por ejemplo, el que aparece en la integración gaussiana . [3]

La aritmética de precisión arbitraria también se utiliza para calcular constantes matemáticas fundamentales como π a millones o más dígitos y para analizar las propiedades de las cadenas de dígitos [4] o más en general para investigar el comportamiento preciso de funciones como la función zeta de Riemann donde ciertas preguntas son difíciles de explorar mediante métodos analíticos. Otro ejemplo es la representación de imágenes fractales con un aumento extremadamente alto, como las que se encuentran en el conjunto de Mandelbrot .

La aritmética de precisión arbitraria también se puede utilizar para evitar el desbordamiento , que es una limitación inherente de la aritmética de precisión fija. De manera similar a la pantalla de un odómetro de 5 dígitos que cambia de 99999 a 00000, un número entero de precisión fija puede exhibirse envolvente si los números crecen demasiado para representar al nivel fijo de precisión. En cambio, algunos procesadores pueden lidiar con el desbordamiento por saturación , lo que significa que si un resultado no fuera representable, se reemplaza con el valor representable más cercano. (Con saturación sin firmar de 16 bits, agregar cualquier cantidad positiva a 65535 produciría 65535). Algunos procesadores pueden generar una excepciónsi un resultado aritmético excede la precisión disponible. Cuando sea necesario, la excepción se puede capturar y recuperar; por ejemplo, la operación podría reiniciarse en el software utilizando aritmética de precisión arbitraria.

En muchos casos, la tarea o el programador pueden garantizar que los valores enteros en una aplicación específica no crezcan lo suficiente como para causar un desbordamiento. Dichas garantías pueden basarse en límites pragmáticos: un programa de asistencia escolar puede tener un límite de tareas de 4.000 estudiantes. Un programador puede diseñar el cálculo de modo que los resultados intermedios se mantengan dentro de los límites de precisión especificados.

Algunos lenguajes de programación como Lisp , Python , Perl , Haskell y Ruby usan, o tienen la opción de usar, números de precisión arbitraria para toda la aritmética de enteros. Aunque esto reduce el rendimiento, elimina la posibilidad de resultados incorrectos (o excepciones) debido a un simple desbordamiento. También permite garantizar que los resultados aritméticos serán los mismos en todas las máquinas, independientemente del tamaño de palabra de cualquier máquina en particular . El uso exclusivo de números de precisión arbitraria en un lenguaje de programación también simplifica el lenguaje, porque un número es un número y no es necesario que varios tipos representen diferentes niveles de precisión.

Problemas de implementación

La aritmética de precisión arbitraria es considerablemente más lenta que la aritmética utilizando números que encajan completamente dentro de los registros del procesador, ya que los últimos generalmente se implementan en aritmética de hardware mientras que los primeros deben implementarse en software. Incluso si la computadora carece de hardware para ciertas operaciones (como la división de enteros o todas las operaciones de punto flotante) y se proporciona software en su lugar, usará tamaños de números estrechamente relacionados con los registros de hardware disponibles: una o dos palabras solamente y definitivamente no N palabras. Hay excepciones, como ciertas máquinas de longitud de palabra variable de las décadas de 1950 y 1960, en particular IBM 1620 , IBM 1401 y Honeywell Liberatorseries, podía manipular números limitados solo por el almacenamiento disponible, con un bit extra que delimitaba el valor.

Los números se pueden almacenar en un formato de punto fijo o en un formato de punto flotante como un significado multiplicado por un exponente arbitrario. Sin embargo, dado que la división introduce casi inmediatamente secuencias de dígitos que se repiten infinitamente (como 4/7 en decimal o 1/10 en binario), si surgiera esta posibilidad, la representación se truncaría en un tamaño satisfactorio o los números racionales serían utilizado: un entero grande para el numerador y para el denominador . Pero incluso con el máximo común divisor dividido, la aritmética con números racionales puede volverse difícil de manejar muy rápidamente: 1/99 - 1/100 = 1/9900, y si luego se suma 1/101, el resultado es 10001/999900.

El tamaño de los números de precisión arbitraria está limitado en la práctica por el almacenamiento total disponible y el tiempo de cálculo.

Se han desarrollado numerosos algoritmos para realizar de manera eficiente operaciones aritméticas en números almacenados con precisión arbitraria. En particular, suponiendo que se empleen N dígitos, se han diseñado algoritmos para minimizar la complejidad asintótica para N grandes .

Los algoritmos más simples son para la suma y la resta , donde uno simplemente suma o resta los dígitos en secuencia, llevando según sea necesario, lo que produce un algoritmo O ( N ) (vea la notación O grande ).

La comparación también es muy sencilla. Compare los dígitos de orden superior (o palabras de máquina) hasta encontrar una diferencia. No es necesario comparar el resto de dígitos / palabras. El peor de los casos es ( N ) , pero normalmente irá mucho más rápido.

Para la multiplicación , los algoritmos más sencillos utilizados para multiplicar números a mano (como se enseña en la escuela primaria) requieren operaciones ( N 2 ) , pero los algoritmos de multiplicación que logran una complejidad O ( N  log ( N ) log (log ( N ))) ideados, como el algoritmo de Schönhage-Strassen , basado en transformadas rápidas de Fourier , y también hay algoritmos con una complejidad ligeramente peor pero con un rendimiento a veces superior en el mundo real para N más pequeños . La multiplicación de Karatsuba es un algoritmo de este tipo.

Para la división , consulte el algoritmo de división .

Para obtener una lista de algoritmos junto con estimaciones de complejidad, consulte la complejidad computacional de las operaciones matemáticas .

Para ver ejemplos en ensamblado x86 , consulte enlaces externos .

Precisión preestablecida

En algunos lenguajes como REXX , la precisión de todos los cálculos debe establecerse antes de realizar un cálculo. Otros lenguajes, como Python y Ruby, amplían la precisión automáticamente para evitar el desbordamiento.

Ejemplo

El cálculo de factoriales puede producir fácilmente números muy grandes. Esto no es un problema para su uso en muchas fórmulas (como la serie de Taylor ) porque aparecen junto con otros términos, de modo que, prestando especial atención al orden de evaluación, los valores de cálculo intermedios no son problemáticos. Si se desean valores aproximados de números factoriales, la aproximación de Stirling da buenos resultados usando aritmética de punto flotante. El valor representable más grande para una variable entera de tamaño fijo puede excederse incluso para argumentos relativamente pequeños, como se muestra en la siguiente tabla. Incluso los números de punto flotante pronto se ven superados, por lo que puede ser útil reformular los cálculos en términos del logaritmo del número.

Pero si se desean valores exactos para factoriales grandes, entonces se requiere un software especial, como en el pseudocódigo que sigue, que implementa el algoritmo clásico para calcular 1, 1 × 2, 1 × 2 × 3, 1 × 2 × 3 × 4, etc. los sucesivos números factoriales.

Límite constante = 1000; % Dígitos suficientes. Base constante = 10; % La base de la aritmética simulada. FactorialLimit constante = 365; % Número objetivo a resolver, ¡365! Dígito de matriz [1: Límite] de entero; % El gran número. Llevar enteros, d; % Asistentes durante la multiplicación. Entero último, i; % Índices a los dígitos del número grande. Texto de matriz [1: Límite] de carácter; % Bloc de notas para la salida.Tdígito constante [0: 9] de carácter = ["0", "1", "2", "3", "4", "5", "6", "7", "8", "9" ]; Dígito de COMIENZO : = 0; % Limpiar toda la matriz. dígito [1]: = 1; % El número grande comienza con 1, último: = 1; % Su dígito de orden más alto es el número 1.  para n: = 1 a FactorialLimit do  % Paso a través de la producción de 1 !, 2 !, 3 !, 4 !, etc. carry: = 0; % Iniciar una multiplicación por n.  para i: = 1 para el último, haga  % Paso a lo largo de cada dígito. d: = dígito [i] * n + acarreo; % El clásico multiplicar. dígito [i]: = d mod Base; % El dígito de orden inferior del resultado. llevar: = d div Base; % El acarreo al siguiente dígito.  siguiente i; while carry> 0 % Guarde el carry en el número grande.  si último> = Limitar entonces croak ("¡Desbordamiento!"); % ¡Si es posible! último: = último + 1; % Un dígito más. dígito [último]: = llevar mod Base; % Colocado. llevar: = llevar div Base; % El acarreo reducido.  Wend  % Con n> Base, tal vez> 1 dígito extra. texto: = ""; % Ahora prepare la salida.  para i: = 1 al último ,  % Traducir de binario a texto. texto [Límite - i + 1]: = tdigit [dígito [i]]; % Invertir el orden.  siguiente i; % Los números arábigos ponen el orden inferior al final.  Imprimir texto, "=", n, "!"; % Imprime el resultado!  siguiente n; % Pasamos al siguiente factorial. FIN ;

Con el ejemplo a la vista, se pueden discutir varios detalles. Lo más importante es la elección de la representación del gran número. En este caso, solo se requieren valores enteros para los dígitos, por lo que una matriz de enteros de ancho fijo es adecuada. Es conveniente que los elementos sucesivos de la matriz representen potencias superiores de la base.

La segunda decisión más importante está en la elección de la base aritmética, aquí diez. Hay muchas consideraciones. La variable del bloc de notas d debe poder contener el resultado de una multiplicación de un solo dígito más el acarreo de la multiplicación del dígito anterior. En base diez, un entero de dieciséis bits es ciertamente adecuado, ya que permite hasta 32767. Sin embargo, este ejemplo hace trampa, ya que el valor de n no se limita a un solo dígito. Esto tiene la consecuencia de que el método fallará para n > 3200 aproximadamente. En una implementación más general, n también usaría una representación de varios dígitos. Una segunda consecuencia del atajo es que después de completar la multiplicación de varios dígitos, el último valor deEs posible que el acarreo deba llevarse a varios dígitos de orden superior, no solo a uno.

También está el problema de imprimir el resultado en base diez, para consideración humana. Debido a que la base ya es de diez, el resultado podría ser mostrado simplemente mediante la impresión de los dígitos sucesivos de matriz de dígitos , pero aparecería con el dígito de orden más alto última (de modo que 123 aparecería como "321"). La matriz completa podría imprimirse en orden inverso, pero eso presentaría el número con ceros a la izquierda ("00000 ... 000123") que pueden no ser apreciados, por lo que esta implementación construye la representación en una variable de texto con espacio y luego imprime ese. Los primeros resultados (con espaciado cada quinto dígito y anotación agregada aquí) son:

Esta implementación podría hacer un uso más efectivo de la aritmética incorporada en la computadora. Una escalada simple sería usar la base 100 (con los cambios correspondientes en el proceso de traducción para la salida) o, con variables de computadora suficientemente amplias (como enteros de 32 bits), podríamos usar bases más grandes, como 10,000. Trabajar en una base de potencia de 2 más cercana a las operaciones de enteros integradas de la computadora ofrece ventajas, aunque la conversión a una base decimal para la salida se vuelve más difícil. En las computadoras modernas típicas, las adiciones y multiplicaciones toman un tiempo constante independientemente de los valores de los operandos (siempre que los operandos quepan en palabras de una sola máquina), por lo que hay grandes ganancias al empaquetar la mayor cantidad posible de un bignumber en cada elemento de la matriz de dígitos.La computadora también puede ofrecer facilidades para dividir un producto en un dígito y llevarlo sin requerir las dos operaciones demod y div como en el ejemplo, y casi todas las unidades aritméticas proporcionan una bandera de acarreo que se puede explotar en la suma y resta de precisión múltiple. Este tipo de detalle es la esencia de los programadores de código máquina, y una rutina adecuada en lenguaje ensamblador bignumber puede ejecutarse mucho más rápido que el resultado de la compilación de un lenguaje de alto nivel, que no proporciona acceso a tales facilidades.

Para una multiplicación de un solo dígito, las variables de trabajo deben poder contener el valor (base-1) 2 + acarreo, donde el valor máximo del acarreo es (base-1). De manera similar, las variables utilizadas para indexar la matriz de dígitos tienen un ancho limitado. Una forma sencilla de extender los índices sería tratar con los dígitos del bignumber en bloques de algún tamaño conveniente de modo que el direccionamiento sea a través de (bloque i , dígito j ) donde i y j serían números enteros pequeños, o bien, se podría escalar a empleando técnicas de bignumber para las variables de indexación. En última instancia, la capacidad de almacenamiento de la máquina y el tiempo de ejecución imponen límites al tamaño del problema.

Historia

La primera computadora comercial de IBM , la IBM 702 (una máquina de tubos de vacío ) de mediados de la década de 1950, implementó la aritmética de enteros por completo en hardware en cadenas de dígitos de cualquier longitud de 1 a 511 dígitos. La primera implementación generalizada de software de la aritmética de precisión arbitraria fue probablemente la de Maclisp . Más tarde, alrededor de 1980, los sistemas operativos VAX / VMS y VM / CMS ofrecieron facilidades de bignum como una colección de funciones de cadena en un caso y en los lenguajes EXEC 2 y REXX en el otro.

Una implementación generalizada temprana estuvo disponible a través del IBM 1620 de 1959-1970. El 1620 era una máquina de dígitos decimales que usaba transistores discretos, pero tenía hardware (que usaba tablas de búsqueda ) para realizar aritmética de números enteros en cadenas de dígitos de una longitud que podía ser de dos a cualquier memoria disponible. Para la aritmética de punto flotante, la mantisa se restringió a cien dígitos o menos, y el exponente se restringió a solo dos dígitos. La memoria más grande suministrada ofrecía 60 000 dígitos, sin embargo, los compiladores de Fortran para 1620 se decidieron por tamaños fijos como 10, aunque podría especificarse en una tarjeta de control si el valor predeterminado no era satisfactorio.

Bibliotecas de software

La aritmética de precisión arbitraria en la mayoría de los programas informáticos se implementa llamando a una biblioteca externa que proporciona tipos de datos y subrutinas para almacenar números con la precisión solicitada y realizar cálculos.

Las diferentes bibliotecas tienen diferentes formas de representar números de precisión arbitraria, algunas bibliotecas funcionan solo con números enteros, otras almacenan números de punto flotante en una variedad de bases (potencias decimales o binarias). En lugar de representar un número como un valor único, algunos números almacenan como un par numerador / denominador ( racionales ) y algunos pueden representar números computables por completo , aunque solo hasta cierto límite de almacenamiento. Fundamentalmente, las máquinas de Turing no pueden representar todos los números reales , ya que la cardinalidad de excede la cardinalidad de .

Ver también

  • Algoritmo de Karatsuba
  • Multiplicación de Toom-Cook
  • Algoritmo de Schönhage-Strassen
  • Algoritmo de Fürer
  • Aritmética de precisión mixta

Referencias

  1. ^ Jacqui Cheng (23 de mayo de 2007). "Investigadores: crack de clave de 307 dígitos pone en peligro RSA de 1024 bits" .
  2. ^ "Copia archivada" . Archivado desde el original el 1 de abril de 2012 . Consultado el 31 de marzo de 2012 .CS1 maint: la copia archivada como título ( enlace ) recomienda que las claves RSA importantes sean de 2048 bits (aproximadamente 600 dígitos).
  3. ^ Laurent Fousse (2006). Intégration numérique avec erreur bornée en précision arbitraire. Modélisation et simulation (Informe) (en francés). Universidad Henri Poincaré - Nancy I.
  4. ^ RK Pathria (1962). "Un estudio estadístico de la aleatoriedad entre los primeros 10.000 dígitos de Pi" . Matemáticas de la Computación . 16 (78): 188-197. doi : 10.1090 / s0025-5718-1962-0144443-7 . Consultado el 10 de enero de 2014 .Un ejemplo de cita de este artículo: "Un patrón tan extremo es peligroso incluso si se diluye con uno de sus bloques vecinos"; esta fue la ocurrencia de la secuencia 77 veintiocho veces en un bloque de mil dígitos.
  • Knuth, Donald (2008). Algoritmos seminuméricos . El arte de la programación informática . 2 (3ª ed.). Addison-Wesley. ISBN 978-0-201-89684-8{{citas inconsistentes}}CS1 maint: postscript ( enlace ) , Sección 4.3.1: Los algoritmos clásicos

enlaces externos

  • El capítulo 9.3 de El arte del ensamblaje de Randall Hyde analiza la aritmética de precisión múltiple , con ejemplos en ensamblaje x86 .
  • Tarea de código Rosetta Enteros de precisión arbitraria Estudios de casos en el estilo en el que más de 47 lenguajes de programación calculan el valor de 5 ** 4 ** 3 ** 2 utilizando aritmética de precisión arbitraria.
Obtenido de " https://en.wikipedia.org/w/index.php?title=Arbitrary-precision_arithmetic&oldid=1031585603 "