Aritmética de precisión arbitraria

En informática, 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 múltiple. aritmética de precisión, 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, 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 puede 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 emplean comúnmente aritmética con números enteros que tienen cientos de dígitos. Otro es en situaciones en que los límites artificiales y los desbordamientos serían inapropiados. También es útil para comprobar los resultados de los cálculos de precisión fija, y para determinar valores óptimos o casi óptimos para los coeficientes necesarios en las fórmulas, por ejemplo los ${fnMicroc} {1}{3}}}$ que aparece en la integración gausiana.

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 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 cinco dígitos que cambia de 99999 a 00000, un número entero de precisión fija puede mostrar una envoltura si los números crecen demasiado para representar el nivel fijo de precisión. En cambio, algunos procesadores pueden lidiar con el desbordamiento mediante 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 la aritmética toda 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.

Problemas de implementació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 palabra variable de las décadas de 1950 y 1960, en particular las series IBM 1620, IBM 1401 y Honeywell Liberator, podían manipular números limitados únicamente por los disponibles. almacenamiento, con un bit extra 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, la representación se truncaría hasta alcanzar 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.

Los algoritmos más simples son para suma y resta, donde uno simplemente suma o resta los dígitos en secuencia, llevándolos según sea necesario, lo que produce un O(N)< Algoritmo /span> (ver notación O grande).

La comparación también es muy simple. Compare los dígitos de alto orden (o palabras de máquina) hasta que se encuentre una diferencia. No es necesario comparar el resto de los dígitos/palabras. El peor caso es ${displaystyle Theta }$()N), pero generalmente va a ir mucho más rápido.

Para la multiplicación, los algoritmos más sencillos utilizados para multiplicar los números a mano (como se enseña en la escuela primaria) requieren ${displaystyle Theta }$()N²) operaciones, pero algoritmos de multiplicación que logran O...Nlog(N) log(log(N)) La complejidad ha sido ideada, como el algoritmo Schönhage-Strassen, basado en rápidos transformaciones de Fourier, y también hay algoritmos con una complejidad ligeramente peor pero con un rendimiento de mundo real a veces superior para pequeños N. La multiplicación de Karatsuba es un algoritmo así.

Para la división, consulte el 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.

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 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 de objetivo a resolver, 365!tdigit: Array[0:9] of character = ["0","1","2","3","4","5","6","7","8","9"

variables:
dígito: Array[1:Limit] de 0,9 % El gran número.d: Integer % Asistentes durante la multiplicación.último: Integer % Índice en los dígitos del gran número.texto: Array[1:Limit] of character % Scratchpad para la salida.digit[*]:= 0 % Despejen toda la matriz.último:= 1 % El gran número comienza como un dígito único,dígito[1]:= 1 % su único dígito es 1.para n:= 1 a FactorialLimit: % Paso a través de la producción 1!, 2!, 3!, 4!, etc. port:= 0 % Comience una multiplicación por n. para i:= 1 a último: % Paso a lo largo de cada dígito.d:= digit[i] * n + port % Multiply un solo dígito.digit[i]:= d mod Base % Mantenga el dígito bajo pedido del resultado.port:= d div Base % Lleve al siguiente dígito. mientras port 0: % Guarda el resto de carga en el gran número. si último >= Límite: error("sobreflujo")
último:= último + 1 % Un dígito más.digit[last]:= transporte mod Base
port:= transporte div Base % Quita el último dígito de la carga.texto [*]:= " % Ahora prepara la salida. para i:= 1 a último: % Traducir de binario a texto.texto[Limit - i + 1]:= tdigit[digit[i] % Revertir la orden. impresión text[Limit - last + 1:Limit], " = ", n, "!"

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, 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 es 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 como consecuencia que el método fallará para n > 3200 más o menos. 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 de carry a varios dígitos de orden superior, no solo a uno.

También está la cuestión 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 un formato con espacios variable de texto 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 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 transportarlo sin requerir las dos operaciones de mod y div como en el ejemplo, y casi todas las unidades aritméticas proporcionan una carry flag 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)² + 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 ampliar los índices sería tratar los dígitos del número grande en bloques de algún tamaño conveniente para que el direccionamiento se realice mediante (bloque i, dígito j) donde i y j serían números enteros pequeños, o se podría pasar a emplear 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.

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 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 números 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.

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.

Diferentes bibliotecas tienen diferentes formas de representar números arbitrarios de precisión, algunas bibliotecas trabajan sólo con números enteros, otros almacenan números de puntos flotantes en una variedad de bases (poderes decimales o binarios). En lugar de representar un número como valor único, algunos números de la tienda como un par numerador/denominador (racionales) y algunos pueden representar completamente números computables, aunque sólo hasta cierto límite de almacenamiento. Fundamentalmente, las máquinas Turing no pueden representar a todos los números reales, como la cardinalidad de ${displaystyle mathbb {R}$ supera el cardenalismo ${displaystyle mathbb {Z}$.