Cómo manejar enteros arbitrariamente grandes

Question

Estoy trabajando en un lenguaje de programación, y hoy llegué al punto en que podía compilar la función factorial (recursiva), sin embargo, debido al tamaño máximo de un entero, el 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

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, p. GNU MP.

Answer 2

No hay una manera fácil de hacerlo en C++. Tendrá que usar una biblioteca externa como GNU Multiprecision, o usar un idioma diferente que admita 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, puede 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 el uso de 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

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 seguir usando los mismos algoritmos), luego cuando se desborda, haga que cambie a 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 5

Si está creando 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 tiene un dígito (0-9). Luego, escribe tu propia rutina para sumar, restar multiplicar y dividir tus matrices de bytes.

(Dividir es el disco uno, pero apuesto a que puede encontrar algo de código en alguna parte.)

Te puedo dar algunos psuedocode similar a Java, pero 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; 
      } 
     } 
    } 
} 

Puedo usar el hecho de que tenemos un montón de espacio extra en un byte para ayudar a lidiar con los desbordamientos de adición en forma genérica. También puede trabajar para la resta y ayudar en algunas multiplicaciones.

Answer 6

Si desea pasar su propia biblioteca de precisión arbitraria, consulte Knuth's Seminumerical Algorithms, volumen 2 de su magnum opus.

Answer 7

Si implementé mi propio idioma y deseo admitir números de longitud arbitrarios, utilizaré un idioma de destino con el concepto carry/borrow.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, simplemente use una biblioteca que tenga más características 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.