You might think that the Ruby version is smart for using a O(log n) algorithm for computing the n-th fibonacci number, but in this case it's stupid (and has not

You might think that the Ruby version is smart for using a O(log n) algorithm for computing the n-th fibonacci number, but in this case it's stupid (and has nothing to do with differential equations). If you are just going to walk over them linearly it's much better to use the straightforward and fast method (like in Haskell and Clojure). So it's not a surprise that Ruby is slower. You CAN take advantage of matrix exponentiation by using binary search. Here are my benchmarks: require 'matrix' limit = 10**999 def fib(n) (Matrix[[1,1],[1,0]]**(n-1))[0,0] end # search for the point where the predicate changes from true to false def bsearch(lower,upper) while lower < upper + 1 mid = (lower+upper)/2 if yield mid lower = mid + 1 else upper = mid - 1 end end return lower end require 'benchmark' Benchmark.bm do |x| x.report('stupid linear search') do i=1 i += 1 while fib(i) < limit end x.report('linear search') do n,a,b = 1,0,1 while b < limit n += 1 a,b = b,a+b end end x.report('binary search') do lower = 1 # find an upper bound upper = 1 upper *= 2 while fib(upper) < limit bsearch(lower,upper){|n| fib(n) < limit} end end Results: user system total real stupid linear search 7.301000 0.000000 7.301000 ( 6.994000) linear search 0.016000 0.000000 0.016000 ( 0.021000) binary search 0.046000 0.000000 0.046000 ( 0.039000) So normal linear search wins and is pretty fast (faster than Clojure according to his benchmarks -- assuming our machines are about as fast because the slow Ruby takes ~7sec on both). Oh and Ruby wins the loc contest: n,a,b = 1,0,1 n,a,b = n+1,b,a+b while b<limit Compared to second best: (def fib-seq (lazy-cat [0 1] (map + fib-seq (rest fib-seq)))) (let [limit (.pow (BigInteger/TEN) 999)] (count (take-while #(< % limit) fib-seq))) Fewer lines and shorter lines and clearer and simpler.