News for hackers. Stuff that matters.
Re:A program to compute the nth Fibonacci number by dubya on Saturday April 28, 2012 @04:26PM (#3903994)
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.
Re:A program to compute the nth Fibonacci number by drostie on Saturday April 28, 2012 @05:05PM (#3904119)
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.

Re:A program to compute the nth Fibonacci number by dullcrisp on Saturday April 28, 2012 @05:32PM (#3904180)
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
Re:A program to compute the nth Fibonacci number by raganwald on Saturday April 28, 2012 @05:42PM (#3904206)
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