faster way of computing large numbers java

Question

I was looking at the wikipedia page on primes and of course, I came across the largest known prime which is 2^43,112,609 − 1. This number is exceptionally large. So for fun, I decided to put this into BigInteger. To calculate this, it would take a very long time (I gave up after a while).

Is there any faster of computing a very large number like this? Or is BigInteger and a better computer the only way? Any reduction of time would be great.

*Note that my question has nothing to do with finding prime numbers. I'm asking if there is a better way to compute the number 2^43,112,609 − 1.

how about using logarithm tables? so something like `Math.exp(n * Math.log(2)) -1`. that should be faster. — aishwarya, Dec 08 '11 at 03:17
please provide examples, I am not aware of logarithm tables but I will "google it". — Jeel Shah, Dec 08 '11 at 03:18
you can consider the ideas in http://stackoverflow.com/questions/453793/which-is-the-fastest-algorithm-to-find-prime-numbers — prusswan, Dec 08 '11 at 03:22
nope, but didnt you put it in BigInteger as an attempt to solve the problem? anyways, you could still get integer from bigint and use that with Math functions. — aishwarya, Dec 08 '11 at 03:22
I didn't what you just recommended into the BIgInteger (yet). — Jeel Shah, Dec 08 '11 at 03:24
@prusswan I am not interested in finding the largest prime, but just computing that specific one. — Jeel Shah, Dec 08 '11 at 03:25
so are you referring to a primality test of a particular number? — prusswan, Dec 08 '11 at 03:27
@prusswan no, I am just interesting in computing that large number. I know I can use BigInteger, I am looking for a more efficent way to reduce time. — Jeel Shah, Dec 08 '11 at 03:29
I've clarified your question. Feel free to revert it if you don't like my changes. — Mysticial, Dec 08 '11 at 04:04

Mysticial · Accepted Answer · 2011-12-08T09:29:38.447

The problem with BigInteger is that it isn't meant for such large numbers. Last time I checked, it was still using quadratic run-time algorithms for both its multiplication and it's base conversion.

So the reason why computing 2^43,112,609 − 1 takes so long is that it's just huge - and you're trying to put that through a quadratic run-time algorithm.

Unfortunately, if you want something faster you will need to use a better bignum library. In C/C++ you have GMP. There are Java wrappers for it if you google around.

*Note that computing 2^43,112,609 − 1 itself is fast since you can do it with just a shift. The slow part is printing out as a string in base 10. Java still uses an O(n^2) algorithm for this conversion.

Efficient programs will be able do this conversion in roughly O(n * log(n)^2) time - which will be under a minute using the latest version of GMP on most up-to-date machines today.

score 1 · Answer 2 · answered Dec 08 '11 at 04:05

1

As noted above by Mysticial, BigInteger isn't really meant to handle such large numbers. Here's a link to a Java wrapper of GMP. I haven't used it, but I've heard a few positive things, so it may be worth giving it a try:

Java wrapper for GMP

answered Dec 08 '11 at 04:05

Shaun

2,446
19
33

score 0 · Answer 3 · answered Dec 08 '11 at 03:54

0

BigInteger has a pow method, which is likely the best for handling large numbers. Check the Javadoc for more.

Also, as explained in the linked question @prusswan brought up, many of those answers also show primegen algorithms which would help.

answered Dec 08 '11 at 03:54

Jon Egeland

12,470
8
47
62

Actually, In case of OP's case, using a `shiftLeft` will be more efficient than `pow`, since it's `2` – st0le Dec 08 '11 at 06:01

faster way of computing large numbers java

3 Answers3