c algorithm - question

Question

What kind of algorithm should i use to calculate 2^n . . Where n is always greater than 100 . . Suggest a good algorithm using c :)

Answer 1

To calculate 2^n with log(n) complexity you can do the following (assuming type can store the result we get):

type result = 1;
type temp = 2;

while (n){
   if (n%2)
     result *= temp;
   temp *= temp;
   n/=2;
}

Answer 2

Note that if you want to print the result in base 2, or base 16 - the solution is strightforward. The real problem is converting the result to base 10 representation.

Since n>100 and you probably want an exact answer, and maby you would also like to manipulate the answer, you should consider using an Arbitrary-precision arithmetic library.

GMP is a good implementation for such library. According to GMP documentation, GMP implements several multiplication algrorithms according to operand size (see section 16.1 for a nice overview of those algorithms).

Answer 3

Start by figuring out what format your output needs to be in. Then figure out what kind of data structure you can store information in, which you could also use to generate that kind of output. I'm guessing you will need an array of some sort in order to store numbers that large. Then you need to figure out how to convert the contents of that array to the output format you need. And, of course, you need to figure out how to perform the math itself 2^n. figure out what 2^n means in terms of its representation in binary. Of course if your output is in binary, octal or Hex, the solution is quite simple. If it's in decimal, you'll probably want your array to be a representation of decimal digits and implement some code that can multiple a decimal digits number by 2 kind of the same way humans do (if you ca't think of a better answer).

Answer 4

Probably you should search for algorithm for conversion from binary to decimal in bigint format. Note that your number in binary system will be represented as

100...00 // n - 1 zeros 

Doing one conversion between binary to decimal will be much faster then performing log(n) multiplications of bigint.

If you really want to use many multiplications read about Karatsuba Multiplication

EDIT: This blog post presents a way to calculate 2^1023 using one double-precision floating-point variable

Answer 5

mhmh - how about leftShift(2, n-1) using some bignum package ?

Answer 6

If n has a reasonable upper bound and speed is a critical factor, precalculate the values and store them in a lookup table.

Answer 7

If n is an integer, simply left shift 1 n times. For large n, ordinary shift operations will not suffice.

If n is a double, use exp2(n) from math.h.