How do you store an arbitrarily large integer value in your memory?

Question

I need to save an integer value that is greater than the maximum value for a long data type. How to save and change this value in memory?

Please illustrate this, if possible, with an example.

Answer 1

Consider saving numbers as sequences of decimal digits using the following structure:

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

For example, number 123456 can be initialized as

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

The reverse order of numbers is important for easy calculation. In particular, the value of the place nd[i] is nd[i] * 10 ^ i.

Now a few questions:

• How would you add it to num ?
• How would you add an arbitrary digit to num ?
• How would you add two num together?
• How would you multiply num by two?
• How would you multiply num by one digit?
• How would you multiply num by 10?
• How would you multiply two num together? TIP: Make a few copies of the pencil and paper and see how they work.

If you work with this sequence of questions, you should be able to write a function for each step and reuse these functions to answer later questions and end up with a very simple and unoptimized long (well, to MAXDIGIT ) integer package to add and multiply positive numbers.

Other questions:

• How do you generalize num both negative and positive numbers?
• How do you divide one num into another (ignoring leftovers)? This is more complicated than multiplication, but then again, start with a few pencil and paper divisions and think carefully about what you are doing.

Answer 2

Possible solutions:
1) Define a custom integer type that is large enough to contain this value. The 128-bit integer is large enough to accommodate 98474737475747374739399.
2) Use any available bignum library.

Answer 3

I will not give you the code, but I can make a couple of suggestions for the approaches:

• Try to save the value as a character string and convert to perform calculations
• Try splitting the value into multiple integers representing part of the value
• Check out existing libraries that can take care of this for you.

Good luck.

Answer 4

Robert Lafo - Object Oriented Programming in C ++, 4th Edition:

 // 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 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 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 last digit temp[j] = '\0'; //terminate string return verylong(temp); //return verylong } 

Very long class title

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

Answer 5

This is a common question in introductory computer science classes at the university. The main areas of focus are: a) understanding how (integer) numbers are stored as binary digits, and b) the basics of data structures, where if the programming language does not provide the desired data structure, you can use meta or collection structures, such as struct in C, class in C ++ or record in Pascal.

So, how less is an integer stored on a computer? In C, you have char, short, int, long data types that can be used to store integers of different sizes. (I will ignore the long long for this discussion.) Let's say, for the sake of generality, that on this 32-bit platform, the sizes are 8-bit, 16-bit, 32-bit, and 64-bit, respectively. Consider the values ​​that can be represented (to simplify those considered unsigned).

Now, how could you store a larger integer that cannot be stored in unsigned 64-bit format? Create your own large integer data type consisting of several smaller (but standard) integers so that they represent large values.

I think this should point you in the right direction and allow you to write your own answer to your homework or exam question.

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 provides an excellent implementation of integer precision in C, I was able to transfer it to the iPhone project with virtually no changes.

Answer 8

C is an amazing language, in the last few days I have been looking for an answer to store large values ​​in C. Then I finally got the answer. use unsigned long.it can store a value up to 18446744073709551615. This is up to 20 digits.

  #include <stdio.h> int main() { unsigned long x=18446744073709551615; printf("%lu",x); return 0; } 

Answer 9

If this is just for display, I would suggest <stdio.h> (for the infamous printf) from the c standard library or maybe <string.h> to make some changes.