High-precision program that calculates 2^n

Question

I'm building a program in C that can get powers of 2. The user inputs the value of n, and the program calculates 2^n.

Here's the code.

The problem comes when I input 100

What I am getting:

1,267,650,600,228,229,400,000,000,000,000

What I should get

1,267,650,600,228,229,401,496,703,205,376

It has to be coded entirely in ANSI C. Any ideas on how to increase the precision? The maximum value of N has to be 256 (256 bits, I imagine, which means the maximum output should be 2^256).

What I'm lacking here is precision, and I don't know how to fix that. Any ideas?

Answer 1

I think it's easiest if you work in base 10 from the start. This is because while calculating powers of 2 in binary is trivial, the conversion back to base 10 is a lot harder.

If you have an array of base 10 digits¹, you only need to implement base 10 addition with carry to be able to multiply by 2 (by adding the number to itself). Do that n times in a loop and you have your answer.

If you wish to support higher exponents, you can also look into implementing exponentiation by squaring, but that's harder, since you'll need general multiplication, not just by 2 for that.

_{¹ Tip: It's more convenient if you store the digits in reverse order.}