Skip to main content

Fibonacci (1000000000) Challenge

Posted by kabutz on February 24, 2012 at 11:44 AM PST

We all know the standard Fibonacci recursive algorithm:

  public BigInteger f(int n) {
    if (n == 0) return BigInteger.ZERO;
    if (n == 1) return BigInteger.ONE;
    return f(n - 1).add(f(n - 2));
  }

Your challenge is to find the first 10 bytes and the last 10 bytes of f(1_000_000_000). That's right, fibonacci of one billion. Please post the answer here, in hexadecimal.

My solution took 2500 seconds on an 8-core machine, utilizing all the cores.

Winner will get a special mention in my next Java Specialists' Newsletter (http://www.javaspecialists.eu).

One last hint. Fork/Join is very useful to speed up your calculation.

Comments

"Your challenge is to find the first 10 bytes and the last ...

"Your challenge is to find the first 10 bytes and the last 10 bytes of f(1_000_000_000)." - given this way, You do not have to calculate the whole number at all. Both lower and upper 10 bytes can be calculated in 1 milisecond on single core using Dijkstra on upper/lower few bytes (10 bytes for lower, cca 15 bytes for upper).

New champion is here ...

New champion is here :)

d:\puzzles\.fibonacci>c:\Programme\Java\jdk1.7.0_04\bin\java -Xms512m -Xmx4096m -server Fibonacci 1000000000
Searching for Fibonacci(1.000.000.000)
Number of bits: 694241913
First 10 bytes: 01 62 80 b8 2d 8c be 0e dc 1b
Last 10 bytes : a9 53 2d f4 d2 d2 5b 5d b6 3b
Time (ms): 170944

The source:

    // See http://www.ii.uni.wroc.pl/~lorys/IPL/article75-6-1.pdf
    public static BigInteger fib(int n){

        BigInteger F = BigInteger.ONE;
        BigInteger L = BigInteger.ONE;

        int sign = -2;
        int exp  = (int)Math.floor((Math.log(n)/Math.log(2)));
        int mask = (int)Math.pow(2, exp);
        for(int i = 0; i < exp-1; i++){
            mask = mask >> 1;
            BigInteger F2   = F.pow(2);
            BigInteger FL2  = F.add(L).pow(2);
            F = FL2.subtract(F2.multiply(6)).shiftRight(1).add(-sign);

            if ((n & mask) != 0){
                BigInteger temp = FL2.shiftRight(2).add(F2);
                L = temp.add(F.shiftLeft(1));
                F     = temp;
            }
            else
                L    = F2.multiply(5).add(sign);

            sign = (n & mask) != 0 ? -2: 2;
        }
        if ((n & (mask >> 1)) == 0)
            return F.multiply(L);
        else
            return F.add(L).shiftRight(1).multiply(L).subtract(BigInteger.valueOf(sign >> 1));
    }

The complete version is here: https://www.dropbox.com/s/16fgiibn5po750l/fib_src.zip

:) Here is my new one-thread java solution :) ...

:) Here is my new one-thread java solution :)

d:\puzzles\.fibonacci>c:\Programme\Java\jdk1.7.0_04\bin\java -Xms512m -Xmx4096m -server Fibonacci 1000000000
Searching for Fibonacci(1.000.000.000)
Number of bits: 694241913
First 10 bytes: 01 62 80 b8 2d 8c be 0e dc 1b
Last 10 bytes: a9 53 2d f4 d2 d2 5b 5d b6 3b
Time to calculate 270842 ms

and yours:

d:\puzzles\.fibonacci>c:\Programme\Java\jdk1.7.0_04\bin\java -Xms512m -Xmx4096m -server -cp javaspecialists\src\main\java eu.javaspecialists.tjsn.examples.issue201.FibonacciGeneratorExample
Searching for Fibonacci(1.000.000.000)
Number of bits: 694241913
First 10 bytes: 01 62 80 b8 2d 8c be 0e dc 1b
Last 10 bytes: a9 53 2d f4 d2 d2 5b 5d b6 3b
Adler32 Checksum: 0x000000004dce91bc
Time to calculate 929714 ms

java.util.concurrent.ForkJoinPool@2f9329a3[Running, parallelism = 32, size = 32, active = 0, running = 0, steals = 8060, tasks = 0, submissions = 0]

The hardware is the same: Intel Core i7-3770K, 4x 3.50GHz, 8GB, Windows7 64.

How did you solve that, Alexey? An iterative solution with ...

How did you solve that, Alexey? An iterative solution with a mutable BigInteger perhaps?

Heinz

It's pretty funny - but I've just recompiled the old sources ...

It's pretty funny - but I've just recompiled the old sources :) Trivial Dijkstra's recurrence and BigInteger from Master Tim Buktu https://raw.github.com/tbuktu/bigint/master/src/main/java/java/math/BigI...
give such great performance ever using only one core! Working on more interesting algorithm, going to test it today evening...

The current java source code: http://pastebin.com/ab8jUyQS

Alexey.

PS. This drupal blog is a little bit better than before, but still far away from wordpress for example :) Do you think to move out there?

When is the Fibonacci (1000000000000) challenge coming? ...

When is the Fibonacci (1000000000000) challenge coming? :)

You wouldn't be able to do it in one line with GMP anymore, but it wouldn't be hard to implement a GMP-based solution.

Wes

Current results: 1000000 fibonacci ...

Current results:

1000000 fibonacci numbers
-------------------------
gcc 4.5.2 + gmp                         :   0.01 sec
ruby 1.9.3                              :   0.17 sec
java 1.6 -client (jscience LargeInteger):   0.18 sec
python 2.5                              :   0.22 sec

1000000000 fibonacci numbers
----------------------------
gcc 4.5.2 + gmp                         :    36  sec. (1 core E7200@3GHz)
gcc 4.5.2 + gmp                         :    55  sec. (1 core )
ruby 1.9.3                              :  3108  sec. (1 core )
java 1.6 -server (jscience LargeInteger):  8980  sec. (3 cores )
python 2.5                              : 11910 sec.  (1 core )

PS. I love this drupal blog :) the worst thing that I've ever seen...

I&nbsp;switched to &quot;the well-known formulas&quot; ...

I switched to "the well-known formulas" mentioned by Prof. Edsger W. Dijkstra and reduced almost 2/3 of time on the same machine.

This time it took 3308 seconds on the same 4 core i5-2520m@2.5GHz.  This is using Java 6 with JScience LargeInteger without any other concurrent handlings.  I am posting Java code here so that you can compare apple to apples.

private int[] KNOWN_FIBS = new int[] { 0, 0, 1 };

public LargeInteger F (int n) {

    if (n &lt; KNOWN_FIBS.length) {
        return LargeInteger.valueOf (KNOWN_FIBS[n]);
    }

    LargeInteger[] j0j1 = F2 (n &gt;&gt; 1);
    LargeInteger j0 = j0j1[0];
    LargeInteger j1 = j0j1[1];
    LargeInteger fn;

    if ((n &amp; 1) == 0) {
        fn = j0.times (j0).plus (j1.times (j1));
    } else {
        fn = j0.shiftLeft (1).plus (j1).times (j1);
    }

    return fn;
}

private LargeInteger[] F2 (int n) {

    if (n &lt; KNOWN_FIBS.length - 1) {
        return new LargeInteger[] { LargeInteger.valueOf (KNOWN_FIBS[n]), LargeInteger.valueOf (KNOWN_FIBS[n + 1]) };
    }

    LargeInteger[] j0j1 = F2 (n &gt;&gt; 1);
    LargeInteger j0 = j0j1[0];
    LargeInteger j1 = j0j1[1];

    LargeInteger fn0 = j0.times (j0).plus (j1.times (j1));
    LargeInteger fn1 = j0.shiftLeft (1).plus (j1).times (j1);

    if ((n &amp; 1) == 1) {
        LargeInteger fn2 = fn1.plus (fn0);
        fn0 = fn1;
        fn1 = fn2;
    }

    return new LargeInteger[] { fn0, fn1 };
}

&nbsp; &nbsp;rexyoung, could you please test the following ...

rexyoung, could you please test the following code on your PC (my is pretty old :)?

 *  Compilation:  javac FibonacciJ.java
*  Execution:    java -server FibonacciJ N
*
*  Compute Fibonacci number using Dijkstra's recurrence:
*    F(2N-1)  = F(N-1)^2 + F(N)^2
*    F(2N)    = (2 F(N-1) + F(N)) F(N)
*
*  Reference: http://www.cs.utexas.edu/users/EWD/ewd06xx/EWD654.PDF
*  Reference: http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibFormula.... *
*************************************************************************/


import java.util.HashMap;
import org.jscience.mathematics.number.LargeInteger;


public class FibonacciJ {
    private static HashMap&lt;LargeInteger, LargeInteger&gt; cache = new HashMap&lt;LargeInteger, LargeInteger&gt;();
    private static LargeInteger ONE  = LargeInteger.ONE;
    private static LargeInteger ZERO = LargeInteger.ZERO;

    public static LargeInteger fibonacci(LargeInteger n) {
        if (n.equals(ZERO)) return ZERO;

        if (n.equals(ONE))  return ONE;
        if (cache.containsKey(n)) return cache.get(n);

        // odd
        if (!n.isEven()) {
            LargeInteger n2 = n.shiftRight(1);
            LargeInteger n3 = n2.plus(ONE);
            LargeInteger result = fibonacci(n2).times(fibonacci(n2)).plus(fibonacci(n3).times(fibonacci(n3)));
            cache.put(n, result);
            return result;
        }

        // even

        else {
            LargeInteger n2 = n.shiftRight(1);
            LargeInteger n3 = n2.minus(ONE);
            LargeInteger result = fibonacci(n2).times(fibonacci(n2).plus(fibonacci(n3).plus(fibonacci(n3))));
            cache.put(n, result);
            return result;
        }
    }


    public static void main(String[] args) {
        long t = System.nanoTime();
        LargeInteger N = LargeInteger.valueOf(Integer.parseInt(args[0]));
        LargeInteger res = fibonacci(N);
        byte[] res_array = new byte[res.bitLength()/8+1];
        res.toByteArray(res_array, 0);
        System.out.println(&quot;Time (ms): &quot; + (System.nanoTime()-t)/1E6);
    }
}

Alexey, on the same machine, your program took 12081 ...

Alexey, on the same machine, your program took 12081 seconds.  I inserted some print outs you can refer to in the attachment.

Agreed, Alexey.&nbsp; It is singularly the worst forum I've ...

Agreed, Alexey.  It is singularly the worst forum I've ever encountered.  Worst of breed.

I think the difference between GMP and Java can probably be explained by the use of better algorithms.  It would be quite interesting to open up the lid and see what GMP uses.  But it's been years since I've read C code, and my Drupal has already exhausted my tolerance for pain, so I won't volunteer to scratch around.

So, I guess Java + JNI + GMP will also return in 36 seconds :-)

I wonder if the GMP algorithm can be parallelized at all?

I used a laptop to get my results.&nbsp; It has an Intel ...

I used a laptop to get my results.  It has an Intel i5-2520m (4 cores) @ 2.5GHz.  The java program uses about 2G memory.  I may add details about my home made algorithm and my handling of concurrency later.  Thanks.

F(14) = 377
unit time: 0 ms.
F(29) = 514229
unit time: 0 ms.
F(59) = 956722026041
unit time: 0 ms.
F(119) = 3311648143516982017180081
unit time: 0 ms.
F(238) = 10C780CAE80B7017CA42 ... 1BAA4297D9C6FA2032DF
unit time: 16 ms.
F(476) = 02758DE1D47CBAC7F9CD ... 6A55D1FB9EC25180AEBD
unit time: 0 ms.
F(953) = 15E16E41126CF2E4313B ... 91894AF6AAFEDFE6838D
unit time: 0 ms.
F(1,907) = 06C42BA74C0CA63E0AA5 ... 457AEDD9F337406B4BE9
unit time: 0 ms.
F(3,814) = 665F8B43C1A7F5654214 ... 2EB0CE1D10C9504513CF
unit time: 15 ms.
F(7,629) = 00941DFE96BE1B96E78F ... 4DA30AF4FCCE09739882
unit time: 0 ms.
F(15,258) = 00BFA069BC70F7FA0043 ... 3D5771A07FAAB83E5778
unit time: 16 ms.
F(30,517) = 0206F8F43B2F108D3228 ... B10100E472B06020DFD9
unit time: 15 ms.
F(61,035) = 0EDE75E43FA43F4B2596 ... AB1191D10C6543AFA6C2
unit time: 16 ms.
F(122,070) = 01EE5D71A76260C01921 ... 421212B189550116AFC8
unit time: 31 ms.
F(244,140) = 0856B7C9B36476D47527 ... 8DADDBE1E15378995410
unit time: 63 ms.
F(488,281) = 00FB941F6EF505D87517 ... 53D98C58A7A73A120091
unit time: 62 ms.
F(976,562) = 0228D4C126ADF2F8D0FF ... AF9C3FB91F81914EEE61
unit time: 109 ms.
F(1,953,125) = 10DF577CBAD3002AF87D ... 2553094299AABDF1D2C5
unit time: 297 ms.
F(3,906,250) = 027C8FAEC9FF639EFADA ... 473A0DAD6F8B2991ADB7
unit time: 842 ms.
F(7,812,500) = 0DD35DA39ADC01AA6EE0 ... 6374ED17411773D4516D
unit time: 2325 ms.
F(15,625,000) = 01AB6BCDC368CB820F38 ... 7C180848838F15CADCCB
unit time: 7051 ms.
F(31,250,000) = 063BB8959851F1B3A525 ... F61276CB3A2EB13D1DE5
unit time: 20 seconds.
F(62,500,000) = 56E13D2A6F85C7A4B9AD ... 793B4E9EDF34A81DE67B
unit time: 62 seconds.
F(125,000,000) = 41EE144C219F1C6C71F7 ... EDD873EE3E142834A645
unit time: 187 seconds.
F(250,000,000) = 25F7A935CA7BA33B4E48 ... 48821240557A9BBC633B
unit time: 576 seconds.
F(500,000,000) = 0C97594C04B5CE74CBEB ... AFFD3848AC567D65EFC5
unit time: 1881 seconds.
F(1,000,000,000) = 016280B82D8CBE0EDC1B ... A9532DF4D2D25B5DB63B
unit time: 6180 seconds.

Total Time: 8919 seconds.

Great job, rexyoung.&nbsp; Are all 4 cores being used to do ...

Great job, rexyoung.  Are all 4 cores being used to do the calculation?  Where is your bottleneck?

My program uses JScience LargeInteger which seems use all ...

My program uses JScience LargeInteger which seems use all cores available.  However it does not use cores hard enough.  I observed an overall CPU usage between 60% and 80%.

The complexity of my algorithm is O(lg N).  Each step consists of several multiplications of LargeInteger.  It is based on that when F(n), F(n-1), and F(n-2) are known, then

F(2n-2) = F(n) * F(n-1) + F(n-1) * F(n-2)
F(2n-1) = F(n) * F(n) + F(n-1) * F(n-1)
F(2n) = F(2n-1) + F(2n-2)

I identified the formula after I wrote down F(1)...F(20) on a piece of paper.  Obviously it is not optimized enough.  But that was a side issue to me.  I was more interested in parallelizing the multiplications in each step.  I used my own project FastMessenger (which allows developers writing concurrent / parallel programs without using multi-threading http://java.net/projects/fastmessenger) for parallelization of this part.  Finally CPU usage was above 95% most of time, and I got a result of 8919 seconds.

 

Heinz, thank you for bringing up the interesting challenge.  I think I will use Fibonacci as one of examples I am going to blog for promotion of FastMessenger.

Thanks,
Rex

Hello My algorithm with BigInteger and matrix ...

Hello

My algorithm with BigInteger and matrix exponentiation takes 1286 milliseconds to calculate Fibonacci of 1000000.

--- My lame attempt :) &nbsp; Windows 7. Intel Q9550 (12M ...

---

My lame attempt :)

Windows 7. Intel Q9550 (12M Cache, 2.83 GHz, 1333 MHz FSB).

Time: Ruby 1.9.3 - 3595 sec, gcc + gmp - 52 sec.

Source size: Ruby - 818 bytes, c - 126 bytes.

Output file size: 186 MB

First 10 bytes in hex: 481DF34ACFB62F5C5439

Last 10 bytes in hex: 0280A026FB794034F91D

Hi Alexey, your numbers do not match my result. &nbsp;Could ...

Hi Alexey,

your numbers do not match my result.  Could you please post your Ruby and C code here?  http://www.javaspecialists.eu/enquiry.jsp

Heinz

&nbsp; Sorry, sent something wrong first time ;) The ...

Sorry, sent something wrong first time ;) The correct sequence should be:

16280b82d8cbe0edc1b8...a9532df4d2d25b5db63b

Is that correct?

Yes, except the very first byte is 01, not 16, but the rest ...

Yes, except the very first byte is 01, not 16, but the rest is correct.

Would you mind sharing the Ruby and C code?

Heinz

The both algorithms based on that ...

The both algorithms based on that description:

http://www.gnu.org/software/gmp/manual/html_node/Fibonacci-Numbers-Algorithm.html

The c code just uses built-in gnu mp function mpz_fib_ui:

#include &lt;gmp.h&gt;
int main()
{
  mpz_t f;
  mpz_init(f);
  mpz_fib_ui(f, 1000000000);
  gmp_printf(&quot;%Zx\n&quot;, f);
  return 0;
}

Calculation time is ~50 sec (Q9550 2.8GHz).

But the Ruby code and performance is more interesting:

class Integer
  FC = Hash.new do |hash, key|
    if hash.has_key?(key - 1) and hash.has_key?(key - 2)
      hash[key] = hash[key - 1] + hash[key - 2]
    elsif hash.has_key?(key + 1) and hash.has_key?(key + 2)
      hash[key] = hash[key + 2] - hash[key + 1]
    else
      subkey = key.div(2)
      case key.modulo(4)
        when 1
          hash[key] = (2*hash[subkey] + hash[subkey - 1])*(2*hash[subkey] - hash[subkey - 1]) + 2
        when 3
          hash[key] = (2*hash[subkey] + hash[subkey - 1])*(2*hash[subkey] - hash[subkey - 1]) - 2
        else
          hash[key] = hash[subkey] * (hash[subkey] + 2*hash[subkey - 1])
      end
    end
  end
  FC[0] = 0
  FC[1] = 1
  def fib
    return FC[self]
  end
end
start_time = Time.now
puts 1000000000.fib.to_s(16)
puts &quot;Time (s):&quot;,(Time.now - start_time)

Execution time is 3189 sec only (not much slower than your java 8 threads app :)

PS. That's Drupal blog is awful, doesn't work under Chrome, isn't clear how to format code etc.

Hi Alexey, I'll disqualify your C version, if you don't ...

Hi Alexey,

I'll disqualify your C version, if you don't mind, as it is simply a method call.  But your Ruby version is good.  You have the advantage of a reasonable BigInteger implementation in Ruby.  The Java BigInteger multiply is O(n2), so I had to rewrite that with Karatsuba.  Fortunately I was able to parallelize it with Fork/Join.  How hard would that be to do parallelize your solution in Ruby?  It should at least double your speed and then it should hopefully beat my Java solution.

I've added your caching idea to my solution, which seems to speed it up a little big.

May I ask what version of Ruby you are using?  I tried this with several versions on Ubuntu and it was a lot slower than your version.

Heinz

 

Heinz, I use the following Ruby version for ...

Heinz,

I use the following Ruby version for Windows:

ruby 1.9.3p0 (2011-10-30) [i386-mingw32]

Small remark - the original ruby solution isn't mine (the author is C Erler (2006)), it's just the tiny modification of his well-known and pretty old ruby example :) My task was to find the right tool and get the job done as quick as possible, and not reinvent the wheel.

PS. C one-liner version takes 36 seconds only (on C2D E7200@3Ghz :)

Alexey.

Tsk, tsk, tsk.&nbsp; I&nbsp;was hoping that someone would at ...

Tsk, tsk, tsk.  I was hoping that someone would at least go to the trouble of coding a clever algorithm.  Or maybe take the Ruby example and parallelize it.

The clever algorithm was already invented by dr.Edsger ...

The clever algorithm was already invented by dr.Edsger W.Dijkstra in 1978 (http://www.cs.utexas.edu/users/EWD/ewd06xx/EWD654.PDF) :) Just for fun - a small benchmarking of 1 million fibonacci numbers:

c - 0.01 sec
ruby - 0.17 sec
python - 0.26 sec
jruby - 8.60 sec
java - 9.00 sec

PS. ruby and jruby use the same file :)

&nbsp;I am working of the same algorithm but using both ...

I am working of the same algorithm but using both caching and LongInteger from JScience on my dual core mac 1 million takes 200-250 milliconds.

Just using JScience LongInteger its 640-770 milliseconds.

I am now working on using a sliding cache otherwise the map saving previous results eat all memory.

I also tried quite a few other algorithms all with worse performance.

This is a more interesting puzle than I expected.

Jerven, if you run it with -Xloggc:fib.vgc and then open ...

Jerven, if you run it with -Xloggc:fib.vgc and then open that file in HPJmeter, you will see that the object creation rate is pretty close to maximum.  Thus, as an earlier commenter suggested, the only way to make this really fast is to have a mutable big integer that can avoid constructing new BigIntegers all the time.  And of course we need to use decent algorithms.

Dijkstra's algorithm is O(log n).  The Karatsuba long multiplication algorithm used in Karatsuba is approximately O(n1.585), as opposed to the standard BigInteger O(n2) multiplication algorithm.

Both of these can be parallelized.  However, we will still push against the limits at which we can create objects.

&nbsp;Karatsuba in JScience is parallized. And I was trying ...

Karatsuba in JScience is parallized. And I was trying to get github.com/tbuktu/bigint into a local JDK install to see how that works.

And so it is, thanks to Javolution's ConcurrentContext. ...

And so it is, thanks to Javolution's ConcurrentContext.  I missed that - thanks :-)

I managed to get the bigint compiled, by fixing an invalid method call to MutableBigInteger, which was probably due to a difference in Java versions.  The performance is quite good.

For the million's Fibonacci, we complete in 0.097 seconds.

With the stock-standard BigInteger, it completes this in 0.4 seconds.

Strange, I don't see any difference between that ...

Strange, I don't see any difference between that code github.com/tbuktu/bigint (9.4 sec) and built-in BigInteger (10 sec) for 1 mln Fibonacci.

Alexey, are you calling it with the -Xbootclasspath/p: ...

Alexey, are you calling it with the -Xbootclasspath/p: option to make sure it uses the doctored BigInteger?

&nbsp;No, I've just removed the package string from fixed ...

No, I've just removed the package string from fixed sources and the import java.math.BigInteger string and recompiled the application :)

Yeah, the algorithm is ancient.&nbsp; Considering that we ...

Yeah, the algorithm is ancient.  Considering that we have a half-life of 3 years in CS knowledge, this one is like the discovery of fire :-)  As I said: I was hoping someone would code a clever algorithm, not necessarily invent one.

However, the reason why Java is so slow is due to the BigInteger implementation.  The default multiply implementation is O(n2).  The org.jscience.* LargeInteger class has Karatsuba built in, but single-core.  Both the Karatsuba algorithm and Dijkstra's Fibonacci are excellent candidates for parallel execution to take advantage of multiple cores.

Has anyone heard of a good fast implementation of BigInteger that can get us results that are comparable with at least Ruby, maybe even C++?

&nbsp; &nbsp; &nbsp;

Heinz, is this open to any JVM language or just Java proper?

Heinz, is this open to any JVM language or just Java proper?

Scrotty, do it in C# if you like, or Groovy, Scala, ...

Scrotty, do it in C# if you like, or Groovy, Scala, Assembler.  Whatever you like

A far more useful way to speed up the calculation is to not ...

A far more useful way to speed up the calculation is to not use recursion in the first place! With my highly inelegant serial approach consuming only a single core on a two year-old PC, I get the value in 1.3 seconds.

I don't mean to be a wiseass about it, but it's important to note the importance of choosing the right algorithm over the latest coding tricks (and fork-join is definitely a nice one).

Absolutely, snagiel.&nbsp; You're not being a ...

Absolutely, snagiel.  You're not being a "wiseass" at all.  This question has everything to do with complexity and algorithms, rather than brute force or clever coding tricks with fork/join.  The problem with the algorithm I presented is not that it is using recursion, but that the complexity is 2n.  You need a much better algorithm than that.

I tried a basic iterative approach and started running into problems beyond a certain value due to the size of the numbers.  I certainly would not have been able to work out Fibonacci of one billion with my algorithm.

OK, won't you please post your first 10 bytes and the last 10 bytes of the number, plus the number of bits in the number, to verify that you indeed found it with your algorithm?

Looks like a memory allocation &amp; GC benchmark... my ...

Looks like a memory allocation & GC benchmark... my hint: use a mutable BigInteger implementation, such as GNU Classpath's.

That might work.&nbsp; I didn't use a mutable BigInteger for ...

That might work.  I didn't use a mutable BigInteger for my solution though.