# Seeking for better algo

• December 2nd, 2013, 11:46 PM
dicdic
Seeking for better algo
hi everyone :)

i'm writing a program that generates 2 to the power of 7830457.
well, i'm not sure if BigInteger class can support this,
here is my code using BigInteger
Code java:

```BigInteger base = new BigInteger("2"), two = new BigInteger("2"); int expo = 2; base = base.pow(7830457); System.out.println(base);```
but that code takes too much time to execute.

here my code using simple mathematics algorithm.
Code java:

``` char[] digits = new char[2357207]; digits[0] = '2'; int carryOver = 0, i, num; for (int expo = 2; expo <= 100; expo++) { i = 0; while (digits[i] != 0 || carryOver != 0) { num = digits[i] - 48; if(num < 0) { num = 0; } num *= 2; num += carryOver; carryOver = num / 10; num = num % 10; num += 48; digits[i++] = (char) num; } } StringBuilder sb = new StringBuilder(); i = 0; while(digits[i] != 0) { sb.append(Integer.toString(digits[i++] - 48)); } sb.reverse(); System.out.println(sb);```

i'm pretty much sure with my algorithm, because i've tested it with different exponents.
but the problem is when the exponent is consist of 6 digits and above, it took too much time
to execute. And according to the guidelines, all problem can be executed within a minute.

I'm asking if there's a better algorithm that can do the same thing in less than a minute?
Thank you so much..

Note: The goal of this exercise is not to get the exact value of 2 to the power
of 7830457 but to get the last 10 digits of that value.
• December 3rd, 2013, 02:21 AM
CampwideGames
Kind of a math problem, more than a programming one. I'll do the math and let you figure out the programming part if you don't want spoilers.

Think about it this way: If you're only trying to find the last ten digits, then mathematically any digits after the tenth will have no impact on the digits before them if you're only doubling. So don't worry about them.

Start with 2, 4, 8, 16, and so on, then when your number gets above ten digits just subtract off 10000000000, then double what you have left. The remaining ten digit number will be equal to the last ten digits of your final number. Program-wise you should be able to do it in a minute, no sweat.
• December 3rd, 2013, 07:09 AM
ChristopherLowe
Re: Seeking for better algo
I was about to suggest something crude that abuses the 2^n bitshift relationship of 1 << n:

Code Java:

```int n = 7830457; BigInteger base = new BigInteger( "1" ); BigInteger result = base.shiftLeft(n);```

and warn you it will take a long time to compute no matter how you optimize it. Then I read this:
Quote:

... get the last 10 digits of that value
Take a look at the modPow() function of BigInteger and consider how it can be used to take the modulo and compute the power together instead of doing them separately.
• December 3rd, 2013, 06:13 PM
dicdic
Re: Seeking for better algo
Quote:

CampwideGames wrote
Start with 2, 4, 8, 16, and so on, then when your number gets above ten digits just subtract off 10000000000, then double what you have left. The remaining ten digit number will be equal to the last ten digits of your final number. Program-wise you should be able to do it in a minute, no sweat.
thank you sir :) it worked. but i did not check if the number exceeds 10 digits, i just mod it to 1000000000 everytime i double it, because i think checking the number using if-else statement will cost time. it execute less than a SECOND now, thank you for your help.
• December 7th, 2013, 03:07 AM
CampwideGames