Thread: The highest Fibonacci number ever calculated

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

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

Originally Posted by Rashakil Fol

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

Maybe recursion was involved, but I still don't think it should be that slow.

I hope everybody here realizes that there is a formula for calculating Fibonacci numbers.

Code:

(pow(1 + sqrt(5), n) - pow(1 - sqrt(5), n)) / (sqrt(5) * pow(2, n))

This means that fib(10) can be calculated just as fast as fib(200000) which can be calculated just as fast as fib(999999999).

The only thing that would slow down the process is the fact that you would have to use a library for abitrary precision arithmetic.

Originally Posted by the pooper

I hope everybody here realizes that there is a formula for calculating Fibonacci numbers.

Code:

(pow(1 + sqrt(5), n) - pow(1 - sqrt(5), n)) / (sqrt(5) * pow(2, n))

This means that fib(10) can be calculated just as fast as fib(200000) which can be calculated just as fast as fib(999999999).

The only thing that would slow down the process is the fact that you would have to use a library for abitrary precision arithmetic.

woah

Originally Posted by the pooper

Code:

(pow(1 + sqrt(5), n) - pow(1 - sqrt(5), n)) / (sqrt(5) * pow(2, n))

I couldn't get this formula to produce correct values, but see below.

Originally Posted by the pooper

The only thing that would slow down the process is the fact that you would have to use a library for abitrary precision arithmetic.

And that really does slow things down, because you need more and more precision, the bigger the numbers.

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)

Originally Posted by the pooper

I hope everybody here realizes that there is a formula for calculating Fibonacci numbers.

Code:

(pow(1 + sqrt(5), n) - pow(1 - sqrt(5), n)) / (sqrt(5) * pow(2, n))

This means that fib(10) can be calculated just as fast as fib(200000) which can be calculated just as fast as fib(999999999).

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

The only thing that would slow down the process is the fact that you would have to use a library for abitrary precision arithmetic.

Exactly.

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

Code:

1 1
1 0

which when exponentiated produces results such as

Code:

13 8
8 5