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

yatin picture yatin · Feb 12, 2010 · Viewed 53k times · Source

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.

Answer

Dale Hagglund picture Dale Hagglund · Feb 13, 2010

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.