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

Question

I have to store an integer value that is larger than the maximum value for the long datatype. How would I store and manipulate this value in memory?

Please illustrate it through an example, if possible.

Caitiff

gmplib.org – Adeliaadelice

Answer 1

Think about storing a numbers as sequences of decimal digits using a struct like this:

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

For example, the number 123456 could be initialized as

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

The reversed digit order turns out to be important for easy calculation. In particular, the place value of n.d[i] is n.d[i] * 10^i.

Now, a few questions:

• How would you add one to a num?
• How would you add an arbitrary single digit to a num?
• How would you add two nums together?
• How would you multiply a num by two?
• How would you multiply a num by a single digit?
• How would you multiply a num by 10?
• How would you multiply two nums together? HINT: Do some pencil and paper multiplications and see how they work.

If you work through this sequence of questions, you should be able to write a function for each step, and re-use those functions to answer the later questions, and end up with a very simple and unoptimized long (well, up to MAXDIGIT digits) integer package for addition and multiplication of positive numbers.

Other questions:

• How do you generalize num to represent negative numbers as well as positive?
• How do you divide one num by another (ignoring remainders)? This is trickier than multiplication, but again, start by doing a few pencil and paper long divisions and think carefully about what you do.

Goa

A good description. And after that: Use base-256 instead of base-10 on that array. :) – Grouch

@Grouch using base 2^32 (or 2^64 if on 64-bit systems) is much better – Moll

@LưuVĩnhPhúc, working with the base 2^32 (or base 2^64) can be awkward in C, because there's no efficient way to detect the carry bit being set after adding two "digits". In raw assembler, this check would be easy, of course, or with in-line assembler in your C program. However, I suspect it's a bit beyond where the OP would be comfortable, at least at this point in time. – Goa

@DaleHagglund It's not much that difficult. There are lots of arbitrary precision library written in C. For unsigned addition it's a simple comparison, you can find numerous examples of that on this site. For signed addition it's a bit more tricky but can still achived within 1 line using bitwise operations. If you need speed, that's another matter. – Moll

however, in 2's complement you can use the same procedure for both signed and unsigned addition/subtraction so it's actually very easy. You can find the solutions here https://mcmap.net/q/19960/-multiword-addition-in-c – Moll

some examples to get carry flag efficiently in C https://mcmap.net/q/507384/-big-integer-addition-without-carry-flag/995714 https://mcmap.net/q/14652/-efficient-128-bit-addition-using-carry-flag/995714 – Moll

Answer 2

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

Provost

Answer 3

I won't give you the code, but I can make a couple of suggestions for approaches to take:

1. Try storing the value as a character string and converting to perform calculations
2. Try breaking the value up into multiple integers representing a portion of the value
3. Look up existing libraries that may take care of this for you

Good luck

Polynesian

Particularly if this is for an exam, I would recommend you think about how you performed math in primary school. You know, add, carry the 1, subtract, take away 10, etc. If you can't do these operations on a character string, you failed primary school, and consequently failed computer science at university. – Prestidigitation

Answer 4

Robert Lafore - 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'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 class header

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

Evitaevitable

Storing decimal digits like this may be enough for an exam but in real computations it'll be inefficient. Bigint libraries use digits in base 2^64 (or base 2^32 in a 32-bit computer) instead – Moll

Answer 5

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

So how is a smaller integer stored in a computer? In C, you have data types char, short, int, long that can all be used to store integers of various sizes. (I'll ignore long long for this discussion.) Let's say for sake of generality that on a given 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 considered unsigned).

Now, how could you store a larger integer, that cannot be stored in an unsigned 64-bit long? Make your own large integer data type, comprised of multiple smaller (but standard) integers such that they represent larger values.

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

Manna

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
    }

Microbicide

Answer 7

If it's only for display, I would suggest a <stdio.h> (for the infamous printf) from the c standard library or maybe the <string.h> to make some modification.

Peele

Sorry, but until you fix this it is a candidate for the most confusing answer ever. – Noonberg

Thanks for pointing that out, I should always re-read. However the question is rather confusing too. – Peele

Answer 8

C is an amazing language ,from last few days i was searching for the answer to store large values in C .then i finally got a answer. use unsigned long .it can typically store value up to 18446744073709551615. It's up to 20 digit number.

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

Avert

From the question I have to store an integer value that is larger than the maximum value for the long datatype ... your answer at best wins a single bit. – Raposa