# Fibonacci (1000000000) Challenge

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.

- Login or register to post comments
- Printer-friendly version
- kabutz's blog
- 15192 reads

## Comments

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

by

T_xy-2014-04-26 15:13"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 ...

by

alexey.solodovnikov-2012-05-30 12:36New 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):

170944The source:

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

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

by

alexey.solodovnikov-2012-05-29 12:16:) 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

270842msand 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

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

by

kabutz-2012-05-29 13:39How 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 ...

by

alexey.solodovnikov-2012-05-30 11:18It'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? ...

by

wfreeman-2012-04-09 10:30When 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 ...

by

alexey.solodovnikov-2012-03-01 16:46Current results:

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

## I switched to "the well-known formulas" ...

by

rexyoung-2012-03-03 02:44I 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.

## rexyoung, could you please test the following ...

by

alexey.solodovnikov-2012-03-03 13:53

rexyoung, could you please test the following code on your PC (my is pretty old :)?## Alexey, on the same machine, your program took 12081 ...

by

rexyoung-2012-03-04 09:49Alexey, on the same machine, your program took 12081 seconds. I inserted some print outs you can refer to in the attachment.

## Agreed, Alexey. It is singularly the worst forum I've ...

by

kabutz-2012-03-02 01:31Agreed, 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. It has an Intel ...

by

rexyoung-2012-02-29 01:22I 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.

## Great job, rexyoung. Are all 4 cores being used to do ...

by

kabutz-2012-02-29 02:17Great 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 ...

by

rexyoung-2012-03-02 13:00My 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

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

by

avasin-2012-02-28 10:19Hello

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

## --- My lame attempt :) Windows 7. Intel Q9550 (12M ...

by

alexey.solodovnikov-2012-02-25 18:37---

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

by

kabutz-2012-02-26 00:24Hi 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

## Sorry, sent something wrong first time ;) The ...

by

alexey.solodovnikov-2012-02-26 04:05Sorry, 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 ...

by

kabutz-2012-02-26 04:23Yes, 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 ...

by

alexey.solodovnikov-2012-02-26 05:56The 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:

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

But the Ruby code and performance is more interesting:

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

by

kabutz-2012-02-26 05:56Hi 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(n

^{2}), 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 ...

by

alexey.solodovnikov-2012-02-27 02:37Heinz,

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. I was hoping that someone would at ...

by

kabutz-2012-02-27 06:46Tsk, 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 ...

by

alexey.solodovnikov-2012-02-28 05:48The 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 :)

## I am working of the same algorithm but using both ...

by

jerven-2012-02-28 05:59I 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 ...

by

kabutz-2012-02-28 06:11Jerven, 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(n

^{1.585}), as opposed to the standard BigInteger O(n^{2}) multiplication algorithm.Both of these can be parallelized. However, we will still push against the limits at which we can create objects.

## Karatsuba in JScience is parallized. And I was trying ...

by

jerven-2012-02-28 07:33Karatsuba 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. ...

by

kabutz-2012-02-28 09:25And 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 ...

by

alexey.solodovnikov-2012-02-29 09:30Strange, 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: ...

by

kabutz-2012-02-29 09:37Alexey, are you calling it with the -Xbootclasspath/p: option to make sure it uses the doctored BigInteger?

## No, I've just removed the package string from fixed ...

by

alexey.solodovnikov-2012-03-01 02:21No, 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. Considering that we ...

by

kabutz-2012-02-28 05:58Yeah, 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

codea 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(n

^{2}). 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++?

##

by

alexey.solodovnikov-2012-03-01 16:25## Heinz, is this open to any JVM language or just Java proper?

by

scrotty-2012-02-24 17:33Heinz, is this open to any JVM language or just Java proper?

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

by

kabutz-2012-02-24 23:17Scrotty, 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 ...

by

snagiel-2012-02-24 19:48A 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. You're not being a ...

by

kabutz-2012-02-24 23:55Absolutely, 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 2

^{n}. 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 & GC benchmark... my ...

by

opinali-2012-02-24 13:51Looks like a memory allocation & GC benchmark... my hint: use a mutable BigInteger implementation, such as GNU Classpath's.

## That might work. I didn't use a mutable BigInteger for ...

by

kabutz-2012-02-24 13:56That might work. I didn't use a mutable BigInteger for my solution though.