4 ms·

Optimal solution assuming that you've got perfectly accurate arbitrary precision arithmetic. Which is as likely as a unicorn that poops Haagen-Dazs.

dubya 14y ago
You could work in the Euclidean domain of integers with sqrt(5) adjoined and avoid floating point completely. The matrix version is actually pretty efficient, and leads to the above if you diagonalize.
- drostie 14y ago
  Just to expand this for people who aren't familiar with this idea, which has a nice analogue with complex numbers, one can take the number a + b sqrt(5) and represent it as the matrix: [a, 5b] [b, a] This implements the multiplication rule for such numbers as a matrix multiplication. There is a straightforward generalization where you replace 5 with -1 and get complex numbers, which is one of the easiest ways to see that the complex numbers are scaled rotation matrices -- which is the easy way to see that a holomorphic function preserves angles and obeys the Cauchy Riemann equation ∂f/∂y = i ∂f/∂x. It's very cute mathematics, but it's still not O(1). At the very least, exponentiating to the n requires log(n) matrix multiplications.
- dullcrisp 14y ago
  I'm late to the party, but a quick and dirty implementation of this in ghci computes the 10,000,000th Fibonacci number for me in about 3 seconds, though it takes a lot longer to print to my terminal. It's pretty neat. newtype T = T (Rational,Rational) deriving Show :{ instance Num T where { T (a,b) + T (c,d) = T (a+c,b+d); T (a,b) * T (c,d) = T (a*c+5*b*d,b*c+a*d); abs (T (a,b)) = T (a*a+5*b*b,0); fromInteger n = T(fromInteger n,0); signum (T (a,_)) = T (signum a,0); negate (T(a,b)) = T(-a,-b) } instance Fractional T where { recip (T(a,b)) = T(a/(a^2-5*b^2),-b/(a^2-5*b^2)); fromRational r = T(r,0)} :} let r5 = T(0,1) let phi = (1+r5)/2 let psi = (1-r5)/2 let fromT (T(a,b)) = (a,b) let fib n = floor . fst . fromT $ (phi^n-psi^n)/r5 let x = fib 10000000 x == 0
  - raganwald 14y ago
    It takes about nineteen seconds for the matrix implementation in Ruby: ruby-1.9.3 043 > x = Time.new.to_i; y = 10000000.matrix_fib; Time.new.to_i - x => 19

dubya 14y ago

You could work in the Euclidean domain of integers with sqrt(5) adjoined and avoid floating point completely. The matrix version is actually pretty efficient, and leads to the above if you diagonalize.

drostie 14y ago
Just to expand this for people who aren't familiar with this idea, which has a nice analogue with complex numbers, one can take the number a + b sqrt(5) and represent it as the matrix: [a, 5b] [b, a] This implements the multiplication rule for such numbers as a matrix multiplication. There is a straightforward generalization where you replace 5 with -1 and get complex numbers, which is one of the easiest ways to see that the complex numbers are scaled rotation matrices -- which is the easy way to see that a holomorphic function preserves angles and obeys the Cauchy Riemann equation ∂f/∂y = i ∂f/∂x. It's very cute mathematics, but it's still not O(1). At the very least, exponentiating to the n requires log(n) matrix multiplications.
dullcrisp 14y ago
I'm late to the party, but a quick and dirty implementation of this in ghci computes the 10,000,000th Fibonacci number for me in about 3 seconds, though it takes a lot longer to print to my terminal. It's pretty neat. newtype T = T (Rational,Rational) deriving Show :{ instance Num T where { T (a,b) + T (c,d) = T (a+c,b+d); T (a,b) * T (c,d) = T (a*c+5*b*d,b*c+a*d); abs (T (a,b)) = T (a*a+5*b*b,0); fromInteger n = T(fromInteger n,0); signum (T (a,_)) = T (signum a,0); negate (T(a,b)) = T(-a,-b) } instance Fractional T where { recip (T(a,b)) = T(a/(a^2-5*b^2),-b/(a^2-5*b^2)); fromRational r = T(r,0)} :} let r5 = T(0,1) let phi = (1+r5)/2 let psi = (1-r5)/2 let fromT (T(a,b)) = (a,b) let fib n = floor . fst . fromT $ (phi^n-psi^n)/r5 let x = fib 10000000 x == 0
- raganwald 14y ago
  It takes about nineteen seconds for the matrix implementation in Ruby: ruby-1.9.3 043 > x = Time.new.to_i; y = 10000000.matrix_fib; Time.new.to_i - x => 19