Как вы храните в памяти сколь угодно большое целочисленное значение?

Question

Мне нужно сохранить целочисленное значение, которое больше максимального значения для длинного типа данных. Как я могу хранить и манипулировать этим значением в памяти?

Просьба проиллюстрировать это на примере, если это возможно.

Answer 1

Я не дам вам код, но я могу сделать несколько предложений для подходов принять:

1. Попробуйте хранить значение в виде строки символов и преобразование для выполнения вычислений
2. Try нарушения значение на несколько целых чисел, представляющих собой часть стоимости
3. Посмотрите на существующие библиотеки, которые могут позаботиться об этом за вас

Успехов

Answer 2

Возможные решения:
1) Определите собственный целочисленный тип, который является достаточно большим, чтобы удерживать это значение. 128-битное целое достаточно велико, чтобы держать 98474737475747374739399.
2) Используйте любую доступную библиотеку bignum.

Answer 3

Это распространенный вопрос в вводных классах компьютерной науки в университете. Основными областями фокуса являются: a) понимание того, как (целочисленные) числа хранятся в виде двоичных цифр, и b) основы структур данных, где, если язык программирования не предоставляет желаемую структуру данных, вы можете использовать meta или таких как struct в C, class в C++ или record в Паскале.

Так как же меньше целых чисел хранится на компьютере? В C у вас есть типы данных char, short, int, long, которые могут быть использованы для хранения целых чисел различных размеров. (Я проигнорирую long long для этого обсуждения.) Скажем, ради общей общности, что на данной 32-битной платформе размеры равны соответственно 8-битным, 16-битным, 32-битным и 64-битным. Рассмотрим значения, которые могут быть представлены (для упрощения рассмотренных без знака).

Теперь, как вы могли бы хранить большее целое число, которое невозможно сохранить в 64-битном формате без знака? Создайте свой собственный большой целочисленный тип данных, состоящий из нескольких меньших (но стандартных) целых чисел, чтобы они представляли большие значения.

Я думаю, что это должно указывать на вас в правильном направлении и позволить вам написать свой собственный ответ на домашнюю работу или вопрос экзамена.

Answer 4

Подумайте о сохранении номера в виде последовательности десятичных цифр, используя-структуру, как это:

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

Например, число 123456 может быть инициализирована как

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

Перевернутая цифра порядка оказывается чтобы быть важным для легкого расчета. В частности, значение места n.d[i] составляет n.d[i] * 10^i.

Теперь несколько вопросов:

• Как бы вы добавить один к num?
• Как бы вы добавили произвольную цифру в num?
• Как вы бы добавили: 2 num s вместе?
• Как бы Вы умножали num на два?
• Как бы Вы умножали num на одну цифру?
• Как вы бы умножить num на 10?
• Как бы вы умножали следующие две цифры: num s? СОВЕТ: Сделайте несколько копий карандаша и бумаги и посмотрите, как они работают.

Если вы работаете с этой последовательностью вопросов, вы должны иметь возможность написать функцию для каждого шага и повторно использовать эти функции для ответа на более поздние вопросы и в итоге получить очень простой и неоптимизированный длинный (ну, до MAXDIGIT цифр) целочисленный пакет для сложения и умножения положительных чисел.

Другие вопросы:

• Как вы обобщающие num представлять отрицательные числа, а также положительным?
• Как вы делите одного num на другого пользователя (игнорируя остатки)? Это сложнее, чем умножение, но опять же, начните с нескольких карандашных и бумажных делений и тщательно подумайте о том, что вы делаете.

Answer 5

Если это только для показа, я хотел бы предложить <stdio.h> (для пресловутого Printf) из библиотеки с стандартной или может быть <string.h> сделать некоторые изменения.

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 обеспечивает хорошую произвольную реализацию точности целое число в C, я был в состоянии бросить его в проект iPhone практически без изменений.

Answer 8

Роберт Лафоре - Объектно-ориентированное программирование на C++, 4-е издание:

// 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 
    } 

заголовка класса сверхдлинными

// 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 
    };