¿Cómo se almacena un valor entero arbitrariamente grande en la memoria?

Question

Tengo que almacenar un valor entero que sea mayor que el valor máximo para el tipo de datos largo. ¿Cómo almacenaría y manipularía este valor en la memoria?

Por favor, ejecútelo con un ejemplo, si es posible.

Answer 1

que no le dará el código, pero puedo hacer un par de sugerencias para acerca a:

1. intente volver a almacenar el valor como una cadena de caracteres y conversión para realizar cálculos de ruptura
2. Try el valor en múltiples enteros que representan una porción del valor
3. Mira bibliotecas existentes que puedan hacerse cargo de esto para usted

Buena suerte

Answer 2

Posibles soluciones:
1) Defina el tipo de entero personalizado que sea lo suficientemente grande para mantener ese valor. El número entero de 128 bits es lo suficientemente grande como para contener 98474737475747374739399.
2) Use cualquier biblioteca bignum disponible.

Answer 3

Esta es una pregunta común en las clases introductorias de informática en la universidad. Las principales áreas de enfoque son a) comprender cómo se almacenan los números enteros como dígitos binarios yb) los conceptos básicos de las estructuras de datos, donde si un lenguaje de programación no proporciona la estructura de datos deseada, puede usar meta o estructuras de recopilación, como struct en C, class en C++, o record en Pascal.

Entonces, ¿cómo se almacena un entero más pequeño en una computadora? En C, tiene los tipos de datos char, short, int, long que se pueden usar para almacenar enteros de varios tamaños. (Ignoraré long long para esta discusión.) Digamos por razones generales que en una plataforma dada de 32 bits los tamaños son 8 bits, 16 bits, 32 bits y 64 bits respectivamente. Considere los valores que se pueden representar (para simplificar considerados sin firmar).

Ahora, ¿cómo podría almacenar un número entero más grande, que no se puede almacenar en una longitud sin signo de 64 bits? Cree su propio tipo de datos enteros grandes, compuesto de múltiples enteros más pequeños (pero estándar) de modo que representen valores más grandes.

Creo que esto debería apuntar en la dirección correcta y permitirle escribir su propia respuesta a su tarea o pregunta del examen.

Answer 4

Piense en el almacenamiento de un número como secuencias de dígitos decimales usando una estructura como esta:

struct num { 
    int ndigits; 
    char d[MAXDIGITS]; 
}; 

Por ejemplo, el número 123 456 se pudo inicializar como

struct num n = { 6, { 6, 5, 4, 3, 2, 1 } }; 

El orden dígitos invertido resulta ser importante para un cálculo fácil. En particular, el valor de lugar de n.d[i] es n.d[i] * 10^i.

Ahora, algunas preguntas:

• ¿Cómo añadir una a una num?
• ¿Cómo agregaría un solo dígito arbitrario a num?
• ¿Cómo agregaría dos num juntos?
• ¿Cómo se multiplicaría un num por dos?
• ¿Cómo se multiplicaría un num por un solo dígito?
• ¿Cómo se multiplicaría un num por 10?
• ¿Cómo se multiplicarían dos num juntos? SUGERENCIA: Haga algunas multiplicaciones de lápiz y papel y vea cómo funcionan.

Si resuelve esta secuencia de preguntas, debería poder escribir una función para cada paso, y reutilizar esas funciones para responder a las preguntas posteriores, y terminar con una longitud muy simple y sin optimizar (bien, hasta MAXDIGIT dígitos) paquete entero para la suma y multiplicación de números positivos.

Otras preguntas:

• ¿Cómo se puede generalizar num para representar números negativos, así como positivo?
• ¿Cómo se divide un num por otro (ignorando los restos)? Esto es más complicado que la multiplicación, pero de nuevo, comienza haciendo algunas divisiones largas de lápiz y papel y piensa cuidadosamente sobre lo que haces.

Answer 5

Si es sólo para la exhibición, sugeriría una <stdio.h> (para el printf infame) de la biblioteca estándar de C o tal vez el <string.h> para hacer alguna modificación.

Answer 6

struct digitcontainer 
    { 
     struct digitcontainer* left; 
     struct digitcontainer* right; 
     unsigned char digit; 
    } 

    struct longinteger 
    { 
     char sign; 
     struct digitcontainer* firstdigit; 
    } 

    // positive number with 1000 digits 
    void test() 
    { 
     struct longinteger myNumber; 

     myNumber.sign = '+'; 
     myNumber.firstdigit = (struct digitcontainer*)malloc(sizeof(digitcontainer)); 
     myNumber.firstdigit->left = NULL; 
     myNumber.firstdigit->right = NULL; 
     myNumber.firstdigit->digit = 1; 

     struct digitcontainer* left = myNumber.firstdigit; 

     for(int i=1; i<1000; i++) 
     { 
     left->right = (struct digitcontainer*)malloc(sizeof(digitcontainer)); 
     left->right->left = left; 
     left->right->digit = (unsigned char)i; 
     left = left->right; 
     } 

     left->right = NULL; 

     // call free for each digitcontainer you are finished using the number 
    } 

Answer 7

LibTomMath proporciona una buena aplicación de precisión entero arbitrario en C, pude soltarlo en un proyecto de iPhone con casi ninguna modificación.

Answer 8

Robert Lafore - Programación orientada a objetos en C++, 4ª Edición:

// verylong.cpp 
// implements very long integer type 
#include "verylong.h"   //header file for verylong 
//-------------------------------------------------------------- 
void verylong::putvl() const   //display verylong 
    { 
    char temp[SZ]; 
    strcpy(temp,vlstr);     //make copy 
    cout << strrev(temp);    //reverse the copy 
    }         //and display it 
//-------------------------------------------------------------- 
void verylong::getvl()     //get verylong from user 
    { 
    cin >> vlstr;      //get string from user 
    vlen = strlen(vlstr);    //find its length 
    strrev(vlstr);      //reverse it 
    } 
//-------------------------------------------------------------- 
verylong verylong::operator + (const verylong v) //add verylongs 
    { 
    char temp[SZ]; 
    int j; 
         //find longest number 
    int maxlen = (vlen > v.vlen) ? vlen : v.vlen; 
    int carry = 0;      //set to 1 if sum >= 10 
    for(j = 0; j<maxlen; j++)   //for each position 
     { 
     int d1 = (j > vlen-1) ? 0 : vlstr[j]-'0'; //get digit 
     int d2 = (j > v.vlen-1) ? 0 : v.vlstr[j]-'0'; //get digit 
     int digitsum = d1 + d2 + carry;    //add digits 
     if(digitsum >= 10)    //if there's a carry, 
     { digitsum -= 10; carry=1; } //decrease sum by 10, 
     else        //set carry to 1 
     carry = 0;     //otherwise carry is 0 
     temp[j] = digitsum+'0';   //insert char in string 
     } 
    if(carry==1)      //if carry at end, 
     temp[j++] = '1';     //last digit is 1 
    temp[j] = '\0';      //terminate string 
    return verylong(temp);    //return temp verylong 
    } 
//-------------------------------------------------------------- 
verylong verylong::operator * (const verylong v) //multiply 
    {            //verylongs 
    verylong pprod;      //product of one digit 
    verylong tempsum;     //running total 
    for(int j=0; j<v.vlen; j++)   //for each digit in arg 
     { 
     int digit = v.vlstr[j]-'0';  //get the digit 
     pprod = multdigit(digit);  //multiply this by digit 
     for(int k=0; k<j; k++)   //multiply result by 
     pprod = mult10(pprod);  // power of 10 
     tempsum = tempsum + pprod;  //add product to total 
     } 
    return tempsum;      //return total of prods 
    } 
//-------------------------------------------------------------- 
verylong verylong::mult10(const verylong v) const //multiply 
    {            //arg by 10 
    char temp[SZ]; 
    for(int j=v.vlen-1; j>=0; j--)  //move digits one 
     temp[j+1] = v.vlstr[j];   // position higher 
    temp[0] = '0';      //put zero on low end 
    temp[v.vlen+1] = '\0';    //terminate string 
    return verylong(temp);    //return result 
    } 
//-------------------------------------------------------------- 
verylong verylong::multdigit(const int d2) const 
    {         //multiply this verylong 
    char temp[SZ];      //by digit in argument 
    int j, carry = 0; 
    for(j = 0; j<vlen; j++)    //for each position 
     {        // in this verylong 
     int d1 = vlstr[j]-'0';   //get digit from this 
     int digitprod = d1 * d2;   //multiply by that digit 
     digitprod += carry;    //add old carry 
     if(digitprod >= 10)   //if there's a new carry, 
     { 
     carry = digitprod/10;   //carry is high digit 
     digitprod -= carry*10;  //result is low digit 
     } 
     else 
     carry = 0;     //otherwise carry is 0 
     temp[j] = digitprod+'0';   //insert char in string 
     } 
    if(carry != 0)      //if carry at end, 
     temp[j++] = carry+'0';   //it's last digit 
    temp[j] = '\0';      //terminate string 
    return verylong(temp);    //return verylong 
    } 

cabecera de la clase Verylong

// verylong.h 
// class specifier for very long integer type 
#include <iostream> 
#include <string.h>   //for strlen(), etc. 
#include <stdlib.h>   //for ltoa() 
using namespace std; 

const int SZ = 1000; 
     //maximum digits in verylongs 

class verylong 
    { 
    private: 
     char vlstr[SZ];  //verylong number, as a string 
     int vlen;    //length of verylong string 
     verylong multdigit(const int) const; //prototypes for 
     verylong mult10(const verylong) const; //private functions 
    public: 
     verylong() : vlen(0)    //no-arg constructor 
     { vlstr[0]='\0'; } 
     verylong(const char s[SZ])  //one-arg constructor 
     { strcpy(vlstr, s); vlen=strlen(s); } //for string 
     verylong(const unsigned long n) //one-arg constructor 
     {          //for long int 
     ltoa(n, vlstr, 10);   //convert to string 
     strrev(vlstr);    //reverse it 
     vlen=strlen(vlstr);   //find length 
     } 
     void putvl() const;    //display verylong 
     void getvl();     //get verylong from user 
     verylong operator + (const verylong); //add verylongs 
     verylong operator * (const verylong); //multiply verylongs 
    };