How can I add two arbitrarily large numbers using only stack allocated memory in C++?

Question

How can I write a program that adds two arbitrarily large numbers using stack allocated memory in C++? I am not allowed to use dynamic allocations on the heap such as malloc or new.

Answer 1

Edit: After the edits the joke answer didn't make much sense anymore, so I wrote a serious one.

I would suggest checking out the GNU MP (GMP) library for working with big numbers. You can either use this library or see how it's implemented for ideas. It may use the heap though.

If you need to do this manually yourself however, you can consider to break apart your number in groups of powers of 10's.

For example try storing an array for each power 10 of your digit. The size of the array will be the number of digits you support with your big number implementation. The type of the array can be just char instead of int because a char is just a number. You only need to store for each digit a number from 0-9 but the smallest data type you can get char will hold between 0-255. Which is fine you will only use the numbers 0-9.

You will probably want to wrap this array in a class that holds that array and override your own operators for adding, etc.

Basically your class would manage internally an array which is all initialized to 0 in the constructor.

Here is an example of breaking apart 2 numbers for addition:

123 + 123
= 1*10^2 + 2*10^1 + 3*10^0 + 1*10^2 + 2*10^1 + 3*10^0
= (1*10^2 + 1*10^2) + (2*10^1 + 2*10^1) + (3*10^0 + 3*10^0)
= (1*10^2 + 1*10^2) + (2*10^1 + 2*10^1 + (position 0's carry over which is 0)) + 6*10^0
= (1*10^2 + 1*10^2 + (position 1's carry over which is 0)) + 4*10^1 + 6*10^0
= 2*10^2 + 4*10^1 + 6*10^0
= 246

In this case your 3 would be stored in each of your arrays at position 0.
Your 2 would be stored in position 1.
Your 1 would be stored in position 2.

The reason you want to store the smallest at the start is in case when you add 2 numbers your number may grow by a digit so you need room for it.

You would add those 3's in position 0 and if the result is greater than 10 you would put the remainder inside position 0 and add what's in position 1 along with the remainder.

To get the remainder of an addition you would do (num1 + num2) %10. To get the carry over you would do (num1 + num2) / 10.