High-precision program that calculates 2^n

[Icekilla]

Hey guys, 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

#include <stdio.h>

double power(int n)
{
      int q;
      double c=2;
      for (q=n; q>1; q--) {c=2*c;}
      return c;
}

int main()
{
    int n;
    double output;
    scanf("%i",&n);
    output=power(n);
    printf("%.0lf",output);
    return 0;
}

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

I've tried to modify the program, but so far, no luck...

It has to be coded entirely in ANSI C. Any ideas on how to increase the precision?

[sfuo]

You would have to use a custom data type. A double can only hold so much precision.

[Icekilla]

I forgot to mention: The maximum value of N is 256.

A friend told me to use arrays for this problem, but I have no idea how to implement them in this case. Any hints?

[Adak]

You could extend your current program by changing int q to unsigned long (or unsigned long long if your compiler supports it).

The goal of course, is that you will have to work out a way to multiply using int arrays, however. (you could use char arrays for the digits, but I prefer using int arrays)

Do you remember how to multiply by hand? You know, what school kids learned in the 4th or 5th grade, back when dinosaur's walked the earth? ;)

Take out a paper and pen, and see how you could mimic that school kid arithmetic, using arrays. I used 4: one for the multiplicand (bet you haven't heard THAT word since forever, that's the top number's digits), one for the multiplier digits, one for the carry, and one for the answer.

They make libraries (bignum from GNU is well known), but it's a great exercise to build your own little function.

In 10 minutes, you'll see the multiplying pattern you need to follow, using the arrays, while you work at it with paper and pen. That's the pattern your program's logic will use, as well.

Give that a shot!