aritmética de precisión arbitraria

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, a veces, aritmética de precisión infinita , indica que los cálculos se realizan sobre números cuya precisión está potencialmente limitada únicamente por la memoria disponible del sistema. Esto contrasta con la aritmética de precisión fija, más rápida , que se encuentra en la mayoría de las unidades aritmético-lógicas (ALU), las cuales suelen ofrecer 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 aritmética de enteros y punto flotante de precisión arbitraria . En lugar de almacenar valores como un número fijo de bits relacionado con el tamaño del registro del procesador , estas implementaciones suelen usar matrices de dígitos de longitud variable .

La precisión arbitraria se utiliza en aplicaciones donde la velocidad de cálculo 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 que ofrecen muchos sistemas de álgebra computacional , que representan números mediante expresiones como π ·sin(2) , y que, 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 suelen emplear aritmética con enteros de cientos de dígitos. ^{[ 5 ] [ 6 ]} Otra aplicación se da en situaciones donde los límites artificiales y los desbordamientos serían inapropiados. También es útil para comprobar 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,${\textstyle {\sqrt {\frac {1}{3}}}}$que aparece en la integración gaussiana . ^{[ 7 ]}

La aritmética de precisión arbitraria también se utiliza para calcular constantes matemáticas fundamentales como π con millones o más dígitos y para analizar las propiedades de las cadenas de dígitos ^{[ 8 ]} o, más generalmente, 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 una magnificación extremadamente alta, como las que se encuentran en el conjunto de Mandelbrot .

La aritmética de precisión arbitraria también puede utilizarse para evitar el desbordamiento , una limitación inherente de la aritmética de precisión fija. De forma similar a como el odómetro de un automóvil puede mostrar valores entre 99999 y 00000, un entero de precisión fija puede presentar un desbordamiento si los números se vuelven demasiado grandes para representarlos con el nivel de precisión fijo. Algunos procesadores pueden gestionar el desbordamiento mediante saturación , lo que significa que si un resultado no se puede representar, se reemplaza por el valor representable más cercano. (Con saturación sin signo de 16 bits, sumar 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. En caso necesario, la excepción se puede capturar y recuperar; por ejemplo, la operación podría reiniciarse mediante 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 crecerán lo suficiente como para provocar un desbordamiento. Dichas garantías pueden basarse en límites pragmáticos: un programa de control de asistencia escolar puede tener un límite de 4000 estudiantes. Un programador puede diseñar el cálculo de manera 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 , Ruby y Raku , utilizan, o permiten utilizar, números de precisión arbitraria para todas las operaciones aritméticas con enteros. Esto permite que los enteros alcancen cualquier tamaño, limitado únicamente por la memoria disponible del sistema. Si bien esto reduce el rendimiento, elimina la preocupación por resultados incorrectos (o excepciones) debido a un simple desbordamiento. Además, permite prácticamente garantizar que los resultados aritméticos sean los mismos en todas las máquinas, independientemente del tamaño de palabra de cada una . El uso exclusivo de números de precisión arbitraria en un lenguaje de programación también lo simplifica, ya que un número es simplemente un número y no es necesario utilizar 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 mediante hardware , mientras que la primera debe implementarse mediante software. Incluso si el ordenador carece de hardware para ciertas operaciones (como la división entera o todas las operaciones de coma 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. Existen excepciones, ya que ciertas máquinas de longitud de palabra variable de las décadas de 1950 y 1960, en particular la IBM 1620 , la IBM 1401 y la serie Honeywell 200 , podían manipular números limitados únicamente por el almacenamiento disponible, con un bit adicional que delimitaba el valor.

En algunos lenguajes, como REXX y ooRexx , la precisión de todos los cálculos debe configurarse antes de realizarlos. Otros lenguajes, como Python y Ruby , amplían la precisión automáticamente para evitar desbordamientos.

El cálculo de factoriales puede producir fácilmente números muy grandes. Esto no supone un problema para su uso en muchas fórmulas (como las series de Taylor ), ya que aparecen junto con otros términos, de modo que, prestando atención al orden de evaluación, los valores intermedios del cálculo no resultan problemáticos. Si se desean valores aproximados de los factoriales, la aproximación de Stirling ofrece buenos resultados utilizando aritmética de punto flotante. El valor máximo representable 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 pronto quedan fuera de rango, 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 ,...: los números factoriales sucesivos.

constantes: Límite = 1000 % Dígitos suficientes. Base = 10 % La base de la aritmética simulada. FactorialLimit = 365 % Número objetivo a resolver, ¡365! tdigit: Array[0:9] de carácter = ["0","1","2","3","4","5","6","7","8","9"] variables: dígito: Array[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: Array[1:Límite] de carácter % Espacio para la salida. digit[*] := 0 % Borra todo el array. last := 1 % El número grande comienza como un solo dígito, digit[1] := 1 % su único dígito es 1.para n := 1 hasta FactorialLimit: % Paso a paso produciendo 1!, 2!, 3!, 4!, etc. carry := 0 % Comienza una multiplicación por n. for i := 1 to last: % Avanza por cada dígito. d := digit[i] * n + carry % Multiplica un solo dígito. digit[i] := d mod Base % Conserva el dígito de menor orden del resultado. carry := d div Base % Lleva al siguiente dígito.mientras carry > 0: % Almacenar el acarreo restante en el número grande. if last >= Limit: error("desbordamiento") último := último + 1 % Un dígito más. dígito[último] := llevar mod Base carry := carry div Base % Elimina el último dígito del carry. texto[*] := " " % Ahora preparamos la salida. para i := 1 hasta último: % Traducir de binario a texto. texto[Límite - i + 1] := tdígito[dígito[i ] ] % Invirtiendo el orden. imprimir texto[Límite - último + 1:Límite], " = ", n, "!"

Con este ejemplo en mente, se pueden analizar 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 enteros de ancho fijo es suficiente. Es conveniente que los elementos sucesivos de la matriz representen potencias superiores de la base.

La segunda decisión más importante es la elección de la base aritmética, en este caso diez. Hay muchas consideraciones. La variable de memoria temporal d debe poder almacenar 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 como consecuencia 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 de este atajo es que, después de que se haya completado la multiplicación de varios dígitos, el último valor del acarreo puede necesitar ser llevado a varios dígitos de orden superior, no solo a uno.

También está el problema de imprimir el resultado en base diez, para que sea legible. Dado que la base ya es diez, el resultado podría mostrarse simplemente imprimiendo los dígitos sucesivos del array , pero aparecerían con el dígito de mayor orden al final (de modo que 123 aparecería como "321"). El array completo podría imprimirse en orden inverso, pero eso presentaría el número con ceros iniciales ("00000...000123"), lo cual podría no ser agradable, por lo que esta implementación construye la representación en una variable de texto con espacios y luego la imprime. Los primeros resultados (con espaciado cada cinco dígitos y anotaciones añadidas aquí) son:

Esta implementación podría aprovechar mejor la aritmética integrada del ordenador. Una simple mejora sería usar la base 100 (con los cambios correspondientes en el proceso de conversión para la salida), o, con variables de ordenador suficientemente amplias (como enteros de 32 bits), podríamos usar bases mayores, como 10000. Trabajar con una base potencia de 2, más cercana a las operaciones con enteros integradas del ordenador, ofrece ventajas, aunque la conversión a una base decimal para la salida se vuelve más difícil. En los ordenadores modernos típicos, las sumas y multiplicaciones requieren un tiempo constante, independientemente de los valores de los operandos (siempre que los operandos quepan en una sola palabra de máquina), por lo que se obtienen grandes ventajas al empaquetar la mayor parte posible de un número grande en cada elemento del array de dígitos. El ordenador también puede ofrecer funciones para dividir un producto en un dígito y un acarreo sin necesidad de las dos operaciones de módulo y división , como en el ejemplo, y casi todas las unidades aritméticas proporcionan un indicador de acarreo que se puede aprovechar en la suma y resta de precisión múltiple. Este tipo de detalles son la materia prima de los programadores de código máquina, y una rutina adecuada de números grandes 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 dichas funcionalidades, sino que asigna las instrucciones de alto nivel a su modelo de la máquina de destino mediante un compilador optimizador.

Para una multiplicación de un solo dígito, las variables de trabajo deben poder almacenar el valor (base − 1) ² + acarreo , donde el valor máximo del acarreo es (base – 1) . De manera similar, las variables utilizadas para indexar el arreglo de dígitos tienen un ancho limitado. Una forma sencilla de extender los índices sería tratar los dígitos del número grande en bloques de un tamaño conveniente, de modo que el direccionamiento se realizaría mediante (bloque i , dígito j ), donde i y j serían enteros pequeños, o bien, se podría recurrir a 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.

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 completamente en hardware sobre cadenas de dígitos de cualquier longitud, desde 1 hasta 511 dígitos. La primera implementación de software generalizada de 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 funcionalidades para números grandes como un conjunto 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 de la IBM 1620 de 1959-1970. La 1620 era una máquina de dígitos decimales que utilizaba transistores discretos, pero contaba con hardware (que utilizaba tablas de búsqueda ) para realizar aritmética de enteros en cadenas de dígitos de una longitud que podía variar desde dos hasta la memoria disponible. Para la aritmética de punto flotante, la mantisa estaba restringida a cien dígitos o menos, y el exponente a solo dos dígitos. La memoria máxima suministrada ofrecía 60 000 dígitos; sin embargo, los compiladores Fortran para la 1620 se conformaron con tamaños fijos como 10, aunque se podía especificar en una tarjeta de control si el valor predeterminado no era satisfactorio.

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

Las distintas bibliotecas tienen diferentes formas de representar números de precisión arbitraria; algunas solo trabajan con números enteros, otras almacenan números de punto flotante en diversas bases (potencias decimales o binarias). En lugar de representar un número como un único valor, algunas almacenan números como un par numerador-denominador ( racionales ) y otras pueden representar completamente números computables , 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${\displaystyle \mathbb {R} }$excede la cardinalidad de${\displaystyle \mathbb {Z} }$.

• El algoritmo de Fürer
• Algoritmo de 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 trata sobre la aritmética de precisión múltiple, con ejemplos en lenguaje ensamblador x86 .
• Tarea de Rosetta Code: 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.