En informática , la aritmética de precisión arbitraria , también llamada aritmética de bignum , 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 cuyos dígitos de precisión están limitados únicamente 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 unidades lógicas aritméticas (ALU), que normalmente ofrece entre 8 y 64 bits de precisión.
Varios lenguajes de programación modernos tienen soporte integrado para bignums, [1] [2] [3] [4] 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 informática , 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 suelen emplear aritmética con números enteros que tienen cientos de dígitos. [5] [6] Otro es en situaciones donde los límites y desbordamientos 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 fórmulas, por ejemplo, el 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 π a 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 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 cinco dígitos que cambia de 99999 a 00000, un número entero de precisión fija puede mostrar una variación si los números crecen demasiado para representar el 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 es representable, se reemplaza con el valor representable más cercano. (Con una saturación sin signo de 16 bits, agregar cualquier cantidad positiva a 65535 produciría 65535). Algunos procesadores pueden generar una excepción si un resultado aritmético excede la precisión disponible. Cuando sea necesario, se puede detectar y recuperar la excepción; 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 crecerán lo suficiente como para causar un desbordamiento. Tales 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 permanezcan dentro de los límites de precisión especificados.
Algunos lenguajes de programación como Lisp , Python , Perl , Haskell , Ruby y Raku 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 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 encajan completamente dentro de los registros del procesador, ya que estos ú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 números enteros o todas las operaciones de punto flotante) y en su lugar se proporciona software, utilizará tamaños de números estrechamente relacionados con los registros de hardware disponibles: una o dos palabras solamente. Hay excepciones, ya que ciertas máquinas de longitud de palabras variables de las décadas de 1950 y 1960, en particular la IBM 1620 , la IBM 1401 y la serie Honeywell Liberator , podían manipular números vinculados únicamente al 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 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, entonces la representación se truncaría en un tamaño satisfactorio o, de lo contrario, los números racionales se convertirían en números racionales. utilizado: un número 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 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 grandes .
Los algoritmos más simples son para suma y resta , donde uno simplemente suma o resta los dígitos en secuencia, llevando 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/palabras. El peor caso 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 ( N 2 ) operaciones, pero los algoritmos de multiplicación que logran una complejidad O( N log( N ) log(log( N ))) han sido ideado, 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 a veces con un rendimiento superior en el mundo real para N más pequeños . La multiplicación de Karatsuba es uno de esos algoritmos.
Para división , consulte algoritmo de división .
Para obtener una lista de algoritmos junto con estimaciones de complejidad, consulte complejidad computacional de las 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 se debe establecer antes de realizar un cálculo. Otros lenguajes, como Python y Ruby , amplían la precisión automáticamente para evitar el desbordamiento.
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 las series 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 más grande representable para una variable entera de tamaño fijo se puede exceder incluso para argumentos relativamente pequeños, como se muestra en la siguiente tabla. Incluso los números de coma flotante pronto quedan 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 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: Matriz[0:9] de carácter = ["0","1","2","3","4","5","6","7","8","9 "]variables: dígito: Matriz[1:Límite] de 0..9 % El número grande. carry, d: % entero Asistentes durante la multiplicación. último: % entero Índice de los dígitos del número grande. texto: Matriz[1:Límite] del carácter % Bloc de notas para la salida.dígito[*] := 0 % Borra toda la matriz.
último := 1 % El número grande comienza como un solo dígito,
dígito[1] := 1 % su único dígito es 1.para n := 1 a FactorialLimit: % Paso a través de la producción de 1!, 2!, 3!, 4!, etc. llevar := 0 % Iniciar una multiplicación por n. para i := 1 para durar: % Avanza a lo largo de cada dígito. d := dígito[i] * n + carry % Multiplica un solo dígito. dígito[i] := d mod Base % Mantenga el dígito de orden inferior del resultado. llevar := d div Base % Pasar al siguiente dígito. while carry > 0: % Almacena el carry restante en el número grande. si es el último >= Límite: 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. text[*] := " " % Ahora prepare la salida. para i := 1 al último: % Traducir de binario a texto. text[Limit - i + 1] := tdigit[digit[i]] % Invirtiendo el orden. imprimir texto[Límite - último + 1:Límite], " = ", n, "!"Teniendo en cuenta el ejemplo, se pueden discutir varios detalles. Lo más importante es la elección de la representación del gran número. En este caso, sólo 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 superiores de la base.
La segunda decisión más importante está en la elección de la base de la 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 está limitado 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 una vez completada la multiplicación de varios dígitos, es posible que sea necesario trasladar el último valor del acarreo a varios dígitos de orden superior, no solo a uno.
También está el tema 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 mayor orden al final (de modo que 123 aparecería como "321"). Toda la matriz podría imprimirse en orden inverso, pero eso presentaría el número con ceros a la izquierda ("00000...000123") que pueden no apreciarse, por lo que esta implementación construye la representación en una variable de texto con espacios y luego imprime eso. 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 eficaz de la aritmética integrada 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 enteras integradas en 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, independientemente de los valores de los operandos (siempre que los operandos quepan en palabras de máquina individuales), por lo que se obtienen grandes beneficios al incluir la mayor cantidad posible de un número grande en cada elemento de la ecuación. matriz de dígitos. La computadora también puede ofrecer funciones para dividir un producto en un dígito y acarrear sin requerir las dos operaciones mod y div como en el ejemplo, y casi todas las unidades aritméticas proporcionan un indicador de acarreo que puede explotarse en sumas y restas de precisión múltiple. Este tipo de detalle es el grano de arena de los programadores de código de 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 dichas funciones sino que mapea el declaraciones de alto nivel a su modelo de la máquina de destino utilizando un compilador de optimización.
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 los dígitos del número grande en bloques de algún tamaño conveniente de modo que el direccionamiento se realice a través de (bloque i , dígito j ) donde i y j serían números enteros pequeños, o se podría escalar a empleando 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 en cadenas de dígitos de cualquier longitud de 1 a 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 funciones 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 de las primeras implementaciones generalizadas 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 enteros en cadenas de dígitos de una longitud que podía ser desde dos hasta 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 dos dígitos únicamente. La memoria más grande suministrada ofrecía 60.000 dígitos, sin embargo, los compiladores de 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 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.
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 coma flotante en una variedad de bases (potencias decimales o binarias). En lugar de representar un número como un valor único, algunos almacenan números como un par numerador/denominador ( racionales ) y algunos 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 excede la cardinalidad de .
