News for hackers. Stuff that matters.
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