Aritmética de precisión arbitraria

Este artículo necesita citas adicionales para su verificación . Por favor, ayude a mejorar este artículo añadiendo citas de fuentes fiables . El material sin fuentes puede ser cuestionado y eliminado. Buscar fuentes:  «Aritmética de precisión arbitraria» – noticias  · periódicos  · libros  · académico  · JSTOR ( julio de 2007 ) ( Aprenda cómo y cuándo eliminar este mensaje )

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

Varios lenguajes de programación modernos tienen soporte integrado para números grandes, ^{[1] [2] [3] [4] y otros tienen bibliotecas disponibles para operaciones matemáticas} con números enteros y de punto flotante de precisión arbitraria . En lugar de almacenar valores como una cantidad fija de bits relacionada 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 en las que la velocidad de la aritmética no es un factor limitante o en las que se requieren resultados precisos con números muy grandes. No debe confundirse con el cálculo simbólico que proporcionan muchos sistemas de álgebra computacional , que representan números mediante expresiones como π ·sin(2) y, por lo tanto, pueden representar cualquier número computable con precisión infinita.

Una aplicación común es la criptografía de clave pública , cuyos algoritmos emplean comúnmente aritmética con números enteros que tienen cientos de dígitos. ^{[5] [6]} Otra es en situaciones en las que los límites artificiales y los desbordamientos 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 fórmulas, por ejemplo, el que aparece en la integración gaussiana . ^[7]${\textstyle {\sqrt {\frac {1}{3}}}}$

La aritmética de precisión arbitraria también se utiliza para calcular constantes matemáticas fundamentales como π hasta millones o más dígitos y para analizar las propiedades de las cadenas de dígitos ^[8] o, de manera más general, para investigar el comportamiento preciso de funciones como la función zeta de Riemann , donde ciertas cuestiones 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 forma similar a la pantalla del odómetro de un automóvil , que puede cambiar de 99999 a 00000, un entero de precisión fija puede presentar un error de retorno si los números se vuelven demasiado grandes para ser representados en el nivel fijo de precisión. Algunos procesadores pueden, en cambio, lidiar con el desbordamiento mediante la saturación , lo que significa que si un resultado no se puede representar, se reemplaza con el valor representable más cercano. (Con la saturación sin signo de 16 bits, agregar cualquier cantidad positiva a 65535 daría como resultado 65535). Algunos procesadores pueden generar una excepción si 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 se puede reiniciar en el software utilizando aritmética de precisión arbitraria.

En muchos casos, la tarea o el programador pueden garantizar que los valores enteros de una aplicación específica no crecerán 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 4000 estudiantes. Un programador puede diseñar el cálculo de modo que los resultados intermedios se mantengan dentro de límites de precisión específicos.

Algunos lenguajes de programación como Lisp , Python , Perl , Haskell , Ruby y Raku usan, o tienen una opción para usar, números de precisión arbitraria para toda la aritmética de números 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 hay necesidad de múltiples tipos para representar diferentes niveles de precisión.

La aritmética de precisión arbitraria es considerablemente más lenta que la aritmética que utiliza números que caben completamente en los registros del procesador, ya que estos últimos suelen implementarse 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, utilizará tamaños de números estrechamente relacionados con los registros de hardware disponibles: solo una o dos palabras. Hay excepciones, ya que ciertas máquinas de longitud de palabra variable de los años 1950 y 1960, en particular la IBM 1620 , la IBM 1401 y la serie Honeywell 200 , podían manipular números limitados solo por el almacenamiento disponible, con un bit adicional que delimitaba el valor.

Los números se pueden almacenar en formato de punto fijo o en formato de punto flotante como un mantisa 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 se utilizarían números racionales: 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.

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

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

Los algoritmos más simples son los de suma y resta , donde uno simplemente suma o resta los dígitos en secuencia, llevando el número según sea necesario, lo que produce un algoritmo O( N ) (ver 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 o palabras. El peor caso es ( N ) , pero puede completarse mucho más rápido con operandos de magnitud similar.${\displaystyle \Theta }$

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 ( N ² ) operaciones, pero se han ideado algoritmos de multiplicación que logran una complejidad de O( N  log( N ) log(log( N ))) , 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.${\displaystyle \Theta }$

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

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

Para ver ejemplos en ensamblaje x86 , consulte los enlaces externos.

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 , extienden la precisión automáticamente para evitar el desbordamiento.

El cálculo de los 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, si se presta 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 utilizando aritmética de punto flotante. El valor representable más grande para una variable entera de tamaño fijo puede superarse incluso para argumentos relativamente pequeños, como se muestra en la tabla siguiente. Incluso los números de punto flotante se superan rápidamente, por lo que puede resultar ú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 números factoriales sucesivos.

constantes: Límite = 1000 % Dígitos suficientes. Base = 10 % La base de la operación aritmética simulada. FactorialLimit = 365 % Número objetivo a resolver, ¡365! tdigit: Matriz[0:9] de caracteres = ["0", "1", "2", "3", "4", "5", "6", "7", "8", "9"]variables: dígito: Matriz[1:Límite] de 0..9 % El número grande. acarreo, d: Entero % Asistentes durante la multiplicación. último: Entero % Índice en los dígitos del número grande. texto: Matriz[1:Límite] de caracteres % Bloc de notas para la salida.digit[*] := 0 % Limpia toda la matriz.
last := 1 % El número grande comienza como un solo dígito,
digit[1] := 1 % su único dígito es 1.para n := 1 a FactorialLimit: % Paso a paso para producir 1!, 2!, 3!, 4!, etc. carry := 0 % Iniciar una multiplicación por n.  para i := 1 hasta el último: % Recorrer cada dígito. d := dígito[i] * n + carry % Multiplicar un solo dígito. dígito[i] := d mod Base % Mantener el dígito de orden inferior del resultado. carry := d div Base % Trasladar al siguiente dígito. mientras carry > 0: % Almacena el carry restante en el número grande.  si last >= Límite: error("overflow") último := último + 1 % Un dígito más. dígito[último] := acarreo mod Base carry := carry div Base % Quita el último dígito del carry. text[*] := " " % Ahora prepara la salida.  for i := 1 to last: % Traduce de binario a texto. text[Limit - i + 1] := tdigit[digit[i]] % Invierte el orden.  print text[Limit - last + 1:Limit], " = ", n, "!"

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

La segunda decisión más importante es la elección de la base de la aritmética, en este caso diez. Hay muchas consideraciones a tener en cuenta. La variable d del bloc de notas debe ser capaz de 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 está limitado a un solo dígito. Esto tiene la consecuencia de que el método fallará para n > 3200 o algo así. En una implementación más general, n también utilizaría una representación de varios dígitos. Una segunda consecuencia del atajo es que después de que se haya completado la multiplicación de varios dígitos, es posible que el último valor del acarreo deba ser acarreado 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 diez, el resultado podría mostrarse simplemente imprimiendo los dígitos sucesivos de la matriz digit , pero aparecerían con el dígito de orden más alto al final (de modo que 123 aparecería como "321"). Se podría imprimir toda la matriz en orden inverso, pero eso presentaría el número con ceros a la izquierda ("00000...000123"), lo que puede no ser apreciado, por lo que esta implementación crea la representación en una variable de texto rellena con espacios y luego la imprime. 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 números 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 números enteros incorporadas 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 sumas y multiplicaciones toman un tiempo constante independiente de los valores de los operandos (siempre que los operandos quepan en palabras de máquina individuales), por lo que hay grandes ganancias al empacar la mayor cantidad posible de un número grande 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 acarrear sin requerir las dos operaciones de mod y div como en el ejemplo, y casi todas las unidades aritméticas proporcionan un indicador de acarreo que se puede explotar en sumas y restas de precisión múltiple. Este tipo de detalles son el objetivo de los programadores de código máquina, y una rutina bignumber adecuada en lenguaje ensamblador puede ejecutarse más rápido que el resultado de la compilación de un lenguaje de alto nivel, que no proporciona acceso directo a tales facilidades sino que mapea las declaraciones de alto nivel a su modelo de la máquina de destino usando un compilador optimizador.

Para una multiplicación de un solo dígito, las variables de trabajo deben poder contener el valor (base−1) ² + acarreo, donde el valor máximo del acarreo es (base−1). De manera similar, las variables utilizadas para indexar la matriz de dígitos están limitadas en ancho. Una forma sencilla de extender los índices sería tratar los dígitos del número grande en bloques de un tamaño conveniente para que el direccionamiento se realice mediante (bloque i , dígito j ), donde i y j serían enteros pequeños, o se podría escalar al empleo de técnicas de números grandes 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.

El primer ordenador empresarial de IBM, el IBM 702 (una máquina de tubos de vacío ) de mediados de los años 50, implementaba la aritmética de números enteros completamente en hardware sobre cadenas de dígitos de cualquier longitud entre 1 y 511 dígitos. La primera implementación generalizada en 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 ofrecían funciones 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 temprana y generalizada 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 estaba restringida a cien dígitos o menos, y el exponente estaba restringido a solo dos dígitos. La memoria más grande suministrada ofrecía 60 000 dígitos, sin embargo, los compiladores Fortran para el 1620 se decidieron por tamaños fijos como 10, aunque se podía especificar en una tarjeta de control si el valor predeterminado no era satisfactorio.

La aritmética de precisión arbitraria en la mayoría del software informático 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 distintas bibliotecas tienen distintas formas de representar números de precisión arbitraria; algunas 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, algunas almacenan números como un par numerador/denominador ( racionales ) y algunas pueden representar completamente números computables , aunque solo hasta cierto límite de almacenamiento. Básicamente, las máquinas de Turing no pueden representar todos los números reales , ya que la cardinalidad de excede la cardinalidad de .${\displaystyle \mathbb {R} }$${\displaystyle \mathbb {Z} }$

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

• Knuth, Donald (2008). Algoritmos seminuméricos . El arte de la programación informática . Vol. 2 (3.ª ed.). Addison-Wesley. ISBN 978-0-201-89684-8.Sección 4.3.1: Los algoritmos clásicos
• Derick Wood (1984). Paradigmas y programación con Pascal . Computer Science Press. ISBN 0-914894-45-5.
• Richard Crandall, Carl Pomerance (2005). Números primos . Springer-Verlag. ISBN 9780387252827.Capítulo 9: Algoritmos rápidos para aritmética de números enteros grandes

• El capítulo 9.3 de El arte del ensamblaje de Randall Hyde analiza la aritmética de multiprecisión, con ejemplos en ensamblaje x86 .
• Tarea del código Rosetta Números enteros de precisión arbitraria Estudios de caso en el estilo en el que más de 95 lenguajes de programación calculan el valor de 5**4**3**2 utilizando aritmética de precisión arbitraria.