Does anyone know of the highest fibonacci number calculated? How quickly it was done? I tried google but couldn't find anything.
Printable View
Does anyone know of the highest fibonacci number calculated? How quickly it was done? I tried google but couldn't find anything.
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
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]
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
I calculated the 200,000th Fibonacci number in half an hour with my C program. :)
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.
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.Quote:
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.
woahQuote:
Originally Posted by the pooper
I couldn't get this formula to produce correct values, but see below.Quote:
Originally Posted by the pooper
And that really does slow things down, because you need more and more precision, the bigger the numbers.Quote:
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.Quote:
Originally Posted by the pooper
Exactly.Quote:
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).