Does anyone know of the highest fibonacci number calculated? How quickly it was done? I tried google but couldn't find anything.
Does anyone know of the highest fibonacci number calculated? How quickly it was done? I tried google but couldn't find anything.
dwk
Seek and ye shall find. quaere et invenies.
"Simplicity does not precede complexity, but follows it." -- Alan Perlis
"Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
"The only real mistake is the one from which we learn nothing." -- John Powell
Other boards: DaniWeb, TPS
Unofficial Wiki FAQ: cpwiki.sf.net
My website: http://dwks.theprogrammingsite.com/
Projects: codeform, xuni, atlantis, nort, etc.
There's not much use to calculating high Fibonacci numbers, and unlike prime numbers, where calculating a high one takes a lot of luck and is a one-time affair, once you calculate the nth and (n+1)th Fibonacci numbers, you can very easily calculate the (n+2)th Fibonacci number. As soon as a high was published, it would be out of date.
Here's the first five digits of the 100000th Fibonacci number, which is 20899 digits long: 25974
Last edited by Rashakil Fol; 07-23-2005 at 01:25 PM.
No, because they could only publish one number, without the previous number, and therefore you couldn't calculate any higher with one number.
[edit]
How did you know that about the 100,000th number?
[/edit]
dwk
Seek and ye shall find. quaere et invenies.
"Simplicity does not precede complexity, but follows it." -- Alan Perlis
"Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
"The only real mistake is the one from which we learn nothing." -- John Powell
Other boards: DaniWeb, TPS
Unofficial Wiki FAQ: cpwiki.sf.net
My website: http://dwks.theprogrammingsite.com/
Projects: codeform, xuni, atlantis, nort, etc.
I calculated it with this Ruby program:
And you could still calculate the next Fibonacci number -- when n gets large, fib(n) is approximately equal to (1 + sqrt(5)) / 2 * fib(n - 1) (close enough that rounding to the nearest integer works).Code:low = 0 high = 1 n = ARGV[0].to_i while (n -= 1) != 0 high += low low = high - low end puts high
Last edited by Rashakil Fol; 07-23-2005 at 07:22 PM.
I calculated the 200,000th Fibonacci number in half an hour with my C program.
dwk
Seek and ye shall find. quaere et invenies.
"Simplicity does not precede complexity, but follows it." -- Alan Perlis
"Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
"The only real mistake is the one from which we learn nothing." -- John Powell
Other boards: DaniWeb, TPS
Unofficial Wiki FAQ: cpwiki.sf.net
My website: http://dwks.theprogrammingsite.com/
Projects: codeform, xuni, atlantis, nort, etc.
Why would it take half an hour? That's a very long amount of time. It took about 10 seconds here (and Ruby should be (read: "is") slower than C).
Perhaps he wrote his own number library -- which probably (read: "surely") would be slower than Ruby's.
Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling
Hmmm.... that's a decent (read: "good") point.
Yeah 30 minutes is very slow for fib(200000) it took less than a minute to calculate the 200,000th one in my relatively slow scheme interpreter.
I just translated Rashakil's ruby.
Code:(define fib (lambda (n) (let loop ((i 1) (low 0) (high 1)) (if (= i n) high (loop (+ i 1) high (+ high low))))))
Maybe recursion was involved, but I still don't think it should be that slow.Originally Posted by Rashakil Fol
I hope everybody here realizes that there is a formula for calculating Fibonacci numbers.This means that fib(10) can be calculated just as fast as fib(200000) which can be calculated just as fast as fib(999999999).Code:(pow(1 + sqrt(5), n) - pow(1 - sqrt(5), n)) / (sqrt(5) * pow(2, n))
The only thing that would slow down the process is the fact that you would have to use a library for abitrary precision arithmetic.
woahOriginally Posted by the pooper
I couldn't get this formula to produce correct values, but see below.Originally Posted by the pooper
And that really does slow things down, because you need more and more precision, the bigger the numbers.Originally Posted by the pooper
For example, fib(200000) takes 1.7 seconds on my machine, but fib(1000000) takes 40 seconds. I used the following python code taken from Wikipedia's Fibonacci programs entry:
Code:def mul(A, B): a, b, c = A d, e, f = B return a*d + b*e, a*e + b*f, b*e + c*f def pow(A, n): if n == 1: return A if n & 1 == 0: return pow(mul(A, A), n/2) else: return mul(A, pow(mul(A, A), (n-1)/2)) def fib(n): if n < 2: return n return pow((1,1,0), n-1)[0] print fib(1000000)
Not true! pow is not an O(1) operation! Not on integers. With doubles, pow uses logarithms, but as N increases, you need linearly increasing amounts of precision to your numbers. This means that using pow (well, some longfloat-capable version of it) would still take at least linear time.Originally Posted by the pooper
Exactly.Originally Posted by the pooper
One interesting solution would be to use a special datatype which stores irrational numbers of the form x + y*sqrt(5) (storing just x and y) and using exponents of these numbers in calculating the given Binet's formula.
This is similar to the Python solution given, which instead uses exponents of the matrix
which when exponentiated produces results such asCode:1 1 1 0
Code:13 8 8 5
When I said half an hour, I was speaking relatively. Besides, my computer is 400MHz.
The number, stored in a text file, is over 50KB (with commas).
dwk
Seek and ye shall find. quaere et invenies.
"Simplicity does not precede complexity, but follows it." -- Alan Perlis
"Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
"The only real mistake is the one from which we learn nothing." -- John Powell
Other boards: DaniWeb, TPS
Unofficial Wiki FAQ: cpwiki.sf.net
My website: http://dwks.theprogrammingsite.com/
Projects: codeform, xuni, atlantis, nort, etc.