c++ - Cómo manejar enteros arbitrariamente grandes

integer overflow

Question

Estoy trabajando en un lenguaje de programación, y hoy llegué al punto en el que podía compilar la función factorial (recursiva); sin embargo, debido al tamaño máximo de un entero, lo más grande que puedo obtener es factorial (12). Cuáles son algunas técnicas para manejar enteros de un tamaño máximo arbitrario. El lenguaje actualmente funciona traduciendo el código a C ++.

Answer 1

Mi enfoque preferido sería usar mi tipo int actual para las entradas de 32 bits (o tal vez cambiarlo internamente para que sea de larga duración o algo así, siempre que pueda continuar usando los mismos algoritmos), y luego cuando se desborde, hacer que cambie para almacenar como un bignum, ya sea de mi propia creación, o utilizando una biblioteca externa. Sin embargo, siento que debería estar revisando el desbordamiento en cada operación aritmética, aproximadamente 2 veces por encima de las operaciones aritméticas. ¿Cómo podría resolver eso?

Answer 2

No hay una manera fácil de hacerlo en C ++. Tendrá que usar una biblioteca externa como Multiprecision de GNU , o usar un idioma diferente que soporte nativamente enteros arbitrariamente grandes como Python.

Answer 3

Otros carteles han dado enlaces a bibliotecas que lo harán por usted, pero parece que está intentando construir esto en su idioma. Mi primer pensamiento es: ¿estás seguro de que tienes que hacer eso? La mayoría de los idiomas usarían una biblioteca adicional como otros han sugerido.

Suponiendo que está escribiendo un compilador y necesita esta característica, podría implementar funciones aritméticas enteras para valores arbitrariamente grandes en el ensamblaje.

Por ejemplo, una implementación simple (pero no óptima) representaría los números como decimal codificado en binario. Las funciones aritméticas podrían usar los mismos algoritmos que utilizarías si estuvieras haciendo los cálculos con lápiz y papel.

Además, considere usar un tipo de datos especializado para estos enteros grandes. De esta manera, los enteros "normales" pueden usar la aritmética estándar de 32 bits.

Answer 4

Si desea desplegar su propia biblioteca de precisión arbitraria, consulte los algoritmos seminumericales de Knuth, volumen 2 de su obra maestra.

Answer 5

Si estás construyendo esto en un lenguaje (para fines de aprendizaje, supongo), creo que probablemente escribiría una pequeña biblioteca de BCD. Simplemente almacene sus números BCD dentro de las matrices de bytes.

De hecho, con las capacidades de almacenamiento gigantescas de hoy en día, puede usar una matriz de bytes donde cada byte solo contiene un dígito (0-9). Luego, escribe tu propia rutina para sumar, restar multiplicar y dividir tus matrices de bytes.

(La división es la más difícil, pero apuesto a que puedes encontrar algún código en alguna parte).

Puedo darte un código psuedocode tipo Java, pero realmente no puedo hacer C ++ desde cero en este punto:

class BigAssNumber {
private byte[] value;
// This constructor can handle numbers where overflows have occurred.
public BigAssNumber(byte[] value) {
this.value=normalize(value);
}
// Adds two numbers and returns the sum. Originals not changed.
public BigAssNumber add(BigAssNumber other) {
// This needs to be a byte by byte copy in newly allocated space, not pointer copy!
byte[] dest = value.length > other.length ? value : other.value;
// Just add each pair of numbers, like in a pencil and paper addition problem.
for(int i=0; i<min(value.length, other.value.length); i++)
dest[i]=value[i]+other.value[i];
// constructor will fix overflows.
return new BigAssNumber(dest);
}
// Fix things that might have overflowed 0,17,22 will turn into 1,9,2
private byte[] normalize(byte [] value) {
if (most significant digit of value is not zero)
extend the byte array by a few zero bytes in the front (MSB) position.
// Simple cheap adjust. Could lose inner loop easily if It mattered.
for(int i=0;i<value.length;i++)
while(value[i] > 9) {
value[i] -=10;
value[i+1] +=1;
}
}
}
}

Uso el hecho de que tenemos mucho espacio adicional en un byte para ayudar a manejar los desbordamientos de suma de una manera genérica. También puede trabajar para la resta y ayudar en algunas multiplicaciones.

Answer 6

Si necesita más de 32 bits, podría considerar el uso de enteros de 64 bits (larga duración), o usar o escribir una biblioteca matemática de precisión arbitraria, por ejemplo, GNU MP .

Answer 7

Si implementé mi propio idioma y deseo admitir números de longitud arbitrarios, utilizaré un idioma de destino con el concepto de acarreo / préstamo. Pero dado que no hay HLL que implemente esto sin implicaciones de rendimiento severas (como excepciones), ciertamente implementaré el ensamblado. Probablemente tomará una sola instrucción (como en JC en x86) para verificar el desbordamiento y manejarlo (como en ADC en x86), que es un compromiso aceptable para un lenguaje que implementa una precisión arbitraria. Luego usaré algunas funciones escritas en ensamble en lugar de operadores regulares, si puede utilizar la sobrecarga para una salida más elegante, incluso mejor. Pero no espero que C ++ generado sea mantenible (o que deba mantenerse) como idioma de destino.

O bien, simplemente use una biblioteca que tenga más características y funciones de las que necesita y úsela para todos sus números.

Como enfoque híbrido, detecte el desbordamiento en el ensamblaje y llame a la función de biblioteca si se produce un desbordamiento en lugar de hacer rodar su propia mini biblioteca.