CODEWITHSUNDEEP
javamath
PeakGen
PeakGen

Reputation: 22995

Finding really big power of a number

I am creating a small game for students, and in a place, it has to display the value of 27830457+1

I can call BigInteger's pow() method if the number is not this much big. Since the number is very big, that method is useless. How can I find the HUGE power of this kind of numbers? Please help!

Upvotes: 3

Views: 8107

Answers (4)

tskuzzy
tskuzzy

Reputation: 36446

Well in binary it's just 10000...01 with 7830456 zeros.

In decimal, there will be approximately two million digits, which is about 2 megabytes of storage. This is well within the feasibility of BigInteger with a default heap size.

In practice, it even uses exponentiation by squaring to compute it quickly (though not guaranteed by the specifications). However the conversion to a String will take some time since it's a linear time operation.

import java.math.BigInteger;

public class BigPow {
    public static void main(String[] args) {
        BigInteger result = (new BigInteger("2")).pow(27830457).add(BigInteger.ONE);
        System.out.println(result);
    }
}

Here's a version which will print out the digits slowly:

import java.math.BigInteger;

public class BigPow {
    public static void main(String[] args) {
        BigInteger result = (new BigInteger("2")).pow(27830457).add(BigInteger.ONE);
        BigInteger powten = BigInteger.TEN.pow(2357202);

        while(powten.compareTo(BigInteger.TEN) > 0) {
            BigInteger digit = result.divide(powten).mod(BigInteger.TEN);
            System.out.print(digit);
            powten = powten.divide(BigInteger.TEN);
        }
    }
}

The first digits are:

27337386390628313557307248857732033008168556429738078791761607160549944954510637855005417718646965163546351365984857761796847950377880836291434244529029919271706271982523405687134334692691344477538489450971091437463160940371624647030064741968436401566711255284353690448270545402444641547030399228243743315193608710148721648879085592699913299745785392609301774185427367430782834290629265859073814466687714408436025809860462926275610087354595992436000187216152954542774991509992374985538879880897902639600451627914923043483436514419544413306391278529303650112773297502090619459167888563274071587848623085880067091968911236296732119252937497152769541579516150659424997041968213122450568364121976474269097910635641227922923398092242409755554115985855831015459204780391470591543281267373716556272259386683864538263922398723602210173800151405332100275913619559563575829498369806957031526077258236305186254269056811134135133350936924294101345294335698866339561918857584229744277901180792029180156485000086528174400878657004645726892816943589969701053158760210512171516969813345080894134663207988962182426459128577282934948790911691329475034324656384238413230485050607666988301932660490870167246016897007835866691705399794247746213819662270451531049826029606671683482160663572103374

Confirmed by WolframAlpha.

Upvotes: 8

Jon Skeet
Jon Skeet

Reputation: 1499770

I don't know why you think BigInteger isn't up to this:

import java.math.BigInteger;

public class Test {
    public static void main(String[] args) throws Exception {
        BigInteger big = BigInteger.valueOf(2)
            .pow(7830457)
            .add(BigInteger.ONE);
        System.out.println(big);
    }
}

It takes a little while (particularly the string conversion at the end), but it's perfectly reasonable.

As Peter noted, shifting ONE left 7830457 is much neater, mind you. I'd argue it's a bit less clear - and of course it doesn't help in the string conversion part.

EDIT: Almost all of the time is spent in the string conversion. It finished in the end on my box though. I can't see the start of it any more, but it ends with...

08570502260645006898157834607641626568029302766491883299164453304032280181734737
79366998940913082443120328458954436211937775477966920836932628607888755839700303
873

Upvotes: 5

marktani
marktani

Reputation: 7808

Try something like this:

BigInteger mant = new BigInteger("2");
BigInteger result = mant.pow(7830457).add(BigInteger.ONE);

Upvotes: 1

Peter Lawrey
Peter Lawrey

Reputation: 533432

You should be able to calculate this with BigInteger.

 System.out.println(BigInteger.ONE.shiftLeft(7830457).add(BigInteger.ONE));

Upvotes: 4

Related Questions