Thread: 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

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.

        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?
just the IDEA please
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.

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.

I was about to suggest something crude that abuses the 2^n bitshift relationship of 1 << n:

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:

... 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.

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.

Glad to be of help!