10
3
This is yet another challenge about the Fibonacci numbers.
The goal is to compute the 20'000'000th Fibonacii number as fast as possible. The decimal output is about 4 MiB large; it starts with:
28543982899108793710435526490684533031144309848579
The MD5 sum of the output is
fa831ff5dd57a830792d8ded4c24c2cb
You have to submit a program that calculates the number while running and puts the result to stdout
. The fastest program, as measured on my own machine, wins.
Here are some additional rules:
- You have to submit the source code and a binary runnable on an x64 Linux
- The source code must be shorter than 1 MiB, in case of assembly it is also acceptable if only the binary is that small.
- You must not include the number to be computed in your binary, even in a disguised fashion. The number has to be calculated at runtime.
- My computer has two cores; you are allowed to use parallelism
I took a small implementation from the Internet which runs in about 4.5 seconds. It should not be very difficult to beat this, assuming that you have a good algorithm.
Related: first 1000 digits of Fib(10**9). Some fast implementations, including one using a Fib(2n) and 2n+1 in terms of Fib(n),n+1 recurrence that runs near-instantly. Also including my x86 machine code answer, featuring lots of brute force, no clever math :P.
– Peter Cordes – 2017-07-25T09:55:59.240If you have high float precision, it's just
Fibo(x) = (phi^x)/sqrt(5)
an O(log(n)) operation – JBernardo – 2011-07-16T17:39:15.553@JBernardo If you think this can beat 4.5 sec, please implement it like that for an x64 Linux. I'd live to see your code. – FUZxxl – 2011-07-16T17:52:05.210
The operation is quite simple. It's all about precision – JBernardo – 2011-07-16T18:05:23.370
@Jbernardo The spec says that you have to output the exact number. (Though I won't check every single digit, just a hash). If you think you can code it like that, just do so. But I doubt, that that will be faster than 4.5 secs. – FUZxxl – 2011-07-16T18:11:23.397
1Dude, anything like Sage that has indeterminate float precision will run that thing in less thant 1/10th of second. It's just a simple expression as
phi = (1+sqrt(5))/2
– JBernardo – 2011-07-16T18:14:23.473@FUZxxl: hash collision FTW! :D You can use
diff
to be 100% certain. – boothby – 2011-07-16T18:53:41.710@Bothby I don't know how mlong it takes for you to get a collision for this hash, but IMHP it takes longer than 4.5 secs. – FUZxxl – 2011-07-16T19:19:11.560
4Can we output the number in hex? – Keith Randall – 2011-07-18T00:25:12.817
2@Keith Nope. That's part of the spec. – FUZxxl – 2011-07-18T10:16:42.377
3Since it's to be measured on your CPU, we might as well have some more information about it, couldn't we? Intel or AMD? Size of the L1 and instruction caches? Instruction set extensions? – J B – 2011-07-19T13:37:49.393
@J B My cpuinfo
– FUZxxl – 2011-07-19T14:43:36.8972As I compute it, your start string and MD5 are for the 20'000'000th number, not the mere 2'000'000th. – J B – 2011-07-19T17:07:30.473
@J B, I just noticed that, too -- and FUZxxl's solution is obviously computing the 20,000,000th. – boothby – 2011-07-19T17:13:10.020
@boothby oops.... I should really think longer before postin. – FUZxxl – 2011-07-19T17:19:46.243
1@JBernardo, I implemented an arbitrary-precision solution, and it gets utterly killed by my double-and-add solution. That, in turn, is embarrassingly slow compared to Sage. I looked into the Sage source; it calls Pari. I looked at the Pari source... and the algorithm is insane. I patently refuse to re-implement it and take credit for it. – boothby – 2011-07-20T00:06:32.997
@boothby link to the algo in the pari source? – Sparr – 2014-11-20T04:54:02.727