CODEWITHSUNDEEP
javaalgorithm
user502187
user502187

Reputation:

Fastest way to compute 9^(9^9) exactly all digits?

Is there a way to exactly compute all of the ca. 370 million decimal digits of 9^(9^9) very fast? I used an out of the box bignumber algorithms library(*) which took 16 minutes.

(*) I used Java BigInteger the pow() method:

?- time((_ is 9^(9^9))).
% Up 974,318 ms, GC 9,302 ms, Thread Cpu 962,688 ms (Current 06/01/18
19:54:01)
Yes

?- statistics.
Max Memory           7,635,730,432 Bytes
Used Memory           765,913,440 Bytes
Free Memory          2,891,739,304 Bytes
Uptime                 2,466,670 Millis
GC Time                    9,315 Millis
Thread Cpu Time          963,812 Millis
Current Time          06/01/18 20:18:37

The Java BigInteger implementation uses Karatsuba and Toom Cook:
http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/tip/src/share/classes/java/math/BigInteger.java

P.S.: To additionally output the ca. 370 million decimal digits, if it would use 1 ms per digit, would only need 370'000 ms. Thats a third of the time I needed to compute the exact digits in the above, i.e. 974,318 ms without displaying.

Upvotes: 3

Views: 131

Answers (1)

btilly
btilly

Reputation: 46399

Try https://raw.githubusercontent.com/tbuktu/bigint/master/src/main/java/java/math/BigInteger.java for an improved BigInteger that switches to Schoenhage-Strassen once integers get past 74,000 digits. My back of the envelope says that that should be an order of magnitude faster after you get to hundreds of millions of digits.

Upvotes: 1

Related Questions