calculate very large powers of 2

[gourav1]

actually, i want to calculate 2^60000 in 1 second. i have tried a way but it is giving output in specified time for 1000 power only.(i have used arrays to store a one integer).
will you please give me a hint only how to do that ?
"I AM NOT ASKING FOR THE CODE TO YOU, JUST A ALGORITHM OR A START UP TO DO THAT"

[asrockw7]

You could try a sort of divide-and-conquer approach and exploit the properties of multiplication.

Think about this:

2^16
         2^8  *  2^8
     2^4  *  2^4
 2^2  *  2^2

Where you divide the problem into something that is more manageable. Due to the symmetry of the products, solving 2^2, for example, already gives you 2^4 and so don't have to compute for the other 2^4, which is what would have happened if you looped through and multiplied by 2 nth times. I'm not quite sure if this would be computed in a second or if it's a more efficient algorithm at all.

It is more convenient if the initial exponent could be made into a multiple of 2 so that you won't encounter any odds and would make the branching a lot simpler. The 'odd' exponent out can just be multiplied after all has been said and done.

Of course, all assuming you could represent 2^60000 in C. lol

[Adak]

First off, I'm not sure, OK?

For smaller numbers, I'd suggest looking into bit shifting, and how each shift leftward, multiplies by 2. Bit shifting is among the fastest operations on a computer, in C.

00000001 = 1
00000010 = 2
00000100 = 4
etc.

But your number far exceeds the capacity of any integral data type in C, so:

Plan B: <light bulb!> ;)

The key point, the final number [in binary], can be calculated directly because the base of the number is 2, and the computer represents numbers in base 2. That means NO multiplication of shifting, is necessary, whatsoever.) print the final number, as a string of digits, from the calculation.

00001000 = 8,

etc.

Convert the binary to a string of single digits, and print them. Don't try to represent 2^60, unless you see in limits.h that it's within the range of an integral data type on your system (perhaps unsigned long long?).

[gourav1]

First off, I'm not sure, OK?

For smaller numbers, I'd suggest looking into bit shifting, and how each shift leftward, multiplies by 2. Bit shifting is among the fastest operations on a computer, in C.

00000001 = 1
00000010 = 2
00000100 = 4
etc.

But your number far exceeds the capacity of any integral data type in C, so:

Plan B: <light bulb!> ;)

The key point, the final number [in binary], can be calculated directly because the base of the number is 2, and the computer represents numbers in base 2. That means NO multiplication of shifting, is necessary, whatsoever.) print the final number, as a string of digits, from the calculation.

00001000 = 8,

etc.

Convert the binary to a string of single digits, and print them. Don't try to represent 2^60, unless you see in limits.h that it's within the range of an integral data type on your system (perhaps unsigned long long?).

any thing else if u can help ? these all are not making my work

[Adak]

Well, I wasn't sure when I first read your initial post, but now, I'm pretty sure. See if this example doesn't stir up some zing for you:

I want to find 2^2. (It is frequently best to tackle a big thing, by first studying a smaller example of it).

2^2 = 4, and what is 4 in binary? 000 001 00 (spaces for emphasis only).

Note the 1 is followed by two zero's. And this is for 2 to the second power.

2 zeroes, and two the the 2nd power. 2 and 2, see how they match up?

Let's test it: 2^5 = 2*2*2*2*2 = 32 and 32 in binary is 001 00000 (spaces for emphasis).

So 2^2 is 1 followed by two 0's, in the byte and 2^5 is 1 followed by 5 0's in the byte.

So what is 2^10 and 2^20, and 2^60, in binary? Righto: 1 followed by 10 zeroes, 1 followed by 20 zeroes and 1 followed by 60 zeroes.

Now there are two ways I see to finish this:

1) If 2^60 is smaller than an unsigned long long int on your system, then you can handle it directly

if not:
2) you have to translate the binary number you have, into decimal

So there you are. I can't do any more without just doing it for you. Read Wikipedia on binary numbers, and if you're still stuck, refer to Google "binary numbers to decimal numbers", and read up.

[gourav1]

Well, I wasn't sure when I first read your initial post, but now, I'm pretty sure. See if this example doesn't stir up some zing for you:

I want to find 2^2. (It is frequently best to tackle a big thing, by first studying a smaller example of it).

2^2 = 4, and what is 4 in binary? 000 001 00 (spaces for emphasis only).

Note the 1 is followed by two zero's. And this is for 2 to the second power.

2 zeroes, and two the the 2nd power. 2 and 2, see how they match up?

Let's test it: 2^5 = 2*2*2*2*2 = 32 and 32 in binary is 001 00000 (spaces for emphasis).

So 2^2 is 1 followed by two 0's, in the byte and 2^5 is 1 followed by 5 0's in the byte.

So what is 2^10 and 2^20, and 2^60, in binary? Righto: 1 followed by 10 zeroes, 1 followed by 20 zeroes and 1 followed by 60 zeroes.

Now there are two ways I see to finish this:

1) If 2^60 is smaller than an unsigned long long int on your system, then you can handle it directly

if not:
2) you have to translate the binary number you have, into decimal

So there you are. I can't do any more without just doing it for you. Read Wikipedia on binary numbers, and if you're still stuck, refer to Google "binary numbers to decimal numbers", and read up.

ya! i understood what you are trying to say... but i have only 1 question. in the last line, how will i convert the binary into decimal as when i need to print decimal number, then first of all i have store it somewhere, so how will i manage it ?

[Adak]

If 2^60th is less than your maximum unsigned long long int, then you can display it the exact same way you display any other unsigned long long int. Use printf's format display flags.

If it's larger than any integral data type, then you need to either print it out as a string of digits (type char array[]), or array of int's (type int array[]), but before you can do that, you need to translate a binary number into a decimal number.

You didn't read the Wikipedia page I suggested yet, did you? Tut tut, old boy! ;) If you intend to do some programming, you have to show some initiative, what?

[histrungalot]

Take a look at http://www.daniweb.com/software-development/c/threads/417121/calculating-powers-of-2, I got his program to calculate 2^50000 in 1.5 seconds.

[gourav1]

ok. any other method ?

[TrustyTony]

As printed binary number it is one and 60000 zeroes.