algorithm - ¿Existen estrategias de implementación comunes para aritmética de precisión arbitraria que sean válidas independientemente de un lenguaje específico?

math language-agnostic

Question

Estoy pensando en diferentes maneras de implementar aritmética de precisión arbitraria (a veces llamada Bignum, Integer o BigInt).

Parece que el lenguaje común es usar una matriz para el almacenamiento del valor real y reasignarla según sea necesario si los requisitos de espacio aumentan o disminuyen.

Más precisamente, parece que el tamaño de bits de los elementos de la matriz suele ser el segundo tamaño más grande que se admite comúnmente (¿es probable que los cálculos con desbordamiento sean más fáciles de implementar?), Por ejemplo, el lenguaje / plataforma admite números de 128 bits -> matriz de números de 64 bits + Variable de 128 bits para manejar el desbordamiento.

¿Existen formas fundamentalmente diferentes de implementar aritmética de precisión arbitraria o es la forma "probada y verdadera" de implementarla sin grandes pérdidas de rendimiento?

Mi pregunta es sobre la estructura de datos subyacente, no sobre los algoritmos para operaciones. Conozco Karatsuba, Toom-Cook y otros.

Answer 1

Es posible usar el teorema del resto chino para representar enteros grandes de una manera fundamentalmente diferente del sistema base-2 ^ n habitual.

Creo que una representación basada en CRT seguirá utilizando una serie de elementos que, como la representación convencional, se basan en la aritmética nativa más conveniente disponible. Sin embargo, estos elementos contienen los restos del número cuando se dividen por una secuencia de números primos, no dígitos base-2 ^ n.

Al igual que con la representación convencional, el número de elementos utilizados determina el tamaño máximo del número representable. Desafortunadamente, no es fácil calcular si un número basado en CRT es mayor que otro, por lo que es difícil saber si su representación ha desbordado el tamaño máximo. Tenga en cuenta que la suma y la multiplicación son muy rápidas en la representación de CRT, lo que podría ser una ventaja si puede resolver el problema de desbordamiento.

Sin embargo, para responder a su pregunta: creo que es correcto decir que el sistema base-2 ^ n es de hecho la representación "probada y verdadera", que es utilizada por las bibliotecas bignum más populares. Creo que recuerdo que existen bibliotecas bignum basadas en CRT existentes, aunque no lo he comprobado últimamente para ver si todavía existen ...