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.

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.