Estoy pensando en diferentes formas de implementar la aritmética de precisión arbitraria (a veces llamada Bignum, Integer o BigInt).¿Existen estrategias de implementación comunes para la aritmética de precisión arbitraria que son válidas independientemente de un idioma específico?
Parece que el idioma común es utilizar una matriz para el almacenamiento del valor real y reasignarlo según sea necesario si los requisitos de espacio aumentan o disminuyen.
Más precisamente, parece que el tamaño de bit de los elementos de la matriz es a menudo el segundo tamaño más grande comúnmente soportado (¿para hacer cálculos con overflow más fáciles de implementar, probablemente?), E. gramo. idioma/plataforma admite números de 128 bits -> matriz de números de 64 bits + variable de 128 bits para controlar el desbordamiento.
¿Existen formas fundamentalmente diferentes de implementar la aritmética de precisión arbitraria o es la manera "probada y verdadera" de implementarla sin grandes pérdidas de rendimiento?
Mi pregunta es sobre la estructura de datos subyacente, no los algoritmos para las operaciones. Sé que Karatsuba, Toom-Cook et alii.
Para enteros grandes, se usan FFT y DFT, creo. –
Para la eficiencia (propagación de acarreo) un bignum se almacena comúnmente como una matriz binaria en forma de little-endian. El tamaño de los elementos de la matriz de hecho tiene que ver con la capacidad de una computadora para procesar los números para obtener un acarreo (para adiciones) o pedir prestado (para restar). El lenguaje de programación específico, la matriz que contiene el bignum puede ser una matriz de bytes, ya que los bytes se pueden convertir fácilmente en el tipo de datos más eficiente disponible. 4 bytes a un int, 8 bytes a un largo, etc. –
En realidad, para sumar y restar, puede usar la longitud de bit nativa. Si hay un acarreo, 'a + b a' para enteros positivos. Pero es bastante complicado manejar el desbordamiento en la multiplicación. Puede hacerlo, pero es mejor dejarlo en la CPU. :) –
vhallac