Ruby vs. Haskell – project Euler #25 deathmatch

What is the first term in the Fibonacci sequence to contain 1000 digits?

This is the quesion I’m answering, comparing the Ruby and the Haskell solutions.

Let’s see the ruby version first, with an imperative approach.

require 'matrix'
 
limit = 10**999
FIBONACCI_MATRIX = Matrix[[1,1],[1,0]]
def fibonacci(n)
  (FIBONACCI_MATRIX**(n-1)) [0,0]
end
i = 1
i+=1 while fibonacci(i) < limit
puts i

Here I am using the fast matrix-based fibonacci calculation method, see the Wikipedia entry – no, memoization is not faster in this case, I’ve tried it.
The code is pretty straight-forward, first I define the limit and initial 2×2 matrix used for the calculation, then I define the fibonacci calculation function. Probably it would be much faster using the native NArray package for matrix calculation.
The runtime on my macbook pro has an average of 3.5 seconds.

And now for the Haskell solution:

limit = 10^999
fibonacci_numbers = 0:1:(zipWith (+) 
                        fibonacci_numbers (tail fibonacci_numbers))
 
index = length w where w = takeWhile (< limit) fibonacci_numbers
 
main = do
  putStrLn(show(index))

This probably requires a bit more explanation. I think the variable ‘limit’ is clear, let’s look at the definition of the fibonacci_numbers function. This resolves to a list and is quite simple and logical when we give a bit of thought to it.
First, define a few things.

• ‘:‘ – this is the list concat/construct operator, it concatenates the item(s) on its right to the item(s) on its left
• ‘zipWith‘ – this is a list function, by definition “makes a list, its elements are calculated from the function and the elements of input lists occuring at the same position in both lists”
• ‘(+)‘ – this is the addition operator as a function.

What is the Fibonacci sequence? A list of numbers, starting with 0,1 where every other element is the sum of the previous two elements.
So, how is this fibonacci_numbers list being built? It has a recursive definition: start with 0 and 1, then calculate all further items by adding the previous two (zipWith (+) does exactly this). We are using this approach because of it’s witty speed – it doesn’t recalculate previous elements. One other thing about this construct: it’s called a lazy list. It’s lazy because the elements aren’t computed until they’re accessed. Also, this is an infinite list. If we tried printing it, it’d go ‘forever’ (until it has no more free RAM).

takeWhile behaves as it name suggests: it takes more and more elements from a list while its function predicate evaluates to true – we are scanning a list until we find an item which is not less than the limit specified.

Apart from its speed (an average of 0.008 seconds on my macbook pro) this solution has elegance and is much closer to the original (mathematic) definition of the Fibonacci sequence. Notice the biggest and most important difference between the approaches:
The Ruby implementation tells how to calculate the nth item of the Fibonacci sequence, the Haskell version defines what the Fibonacci sequence is.

If you liked it, take a look at my older post about solving project Euler problem #1 in erlang here

Stay tuned for more Project Euler solutions in haskell and ruby!

UPDATE

Code after applying HLint (thank you, Neil Mitchell!) suggestions:

limit = 10^999
fibonacciNumbers = 0:1:zipWith (+) fibonacciNumbers (tail fibonacciNumbers)
 
index = length w where w = takeWhile (< limit) fibonacciNumbers
 
main = print index

Much nicer!

What is the first term in the Fibonacci sequence to contain 1000 digits? This is the quesion I'm answering, comparing the Ruby and the Haskell solutions. Let's see the ruby version first, with an imperative approach. require 'matrix' limit = 10**999 FIBONACCI_MATRIX = Matrix[[1,1],[1,0]] def fibonacci(n) (FIBONACCI_MATRIX**(n-1)) [0,0] end i = 1 i+=1 while fibonacci(i) < limit puts i Here I am using the fast matrix-based fibonacci calculation method, see the Wikipedia entry - no, memoization is not faster in this case, I've tried it. The code is pretty straight-forward, first I define the limit and initial 2x2 matrix used for the calculation, then I define the fibonacci calculation function. Probably it would be much faster using the native NArray package for matrix calculation. The runtime on my macbook pro has an average of 3.5 seconds. And now for the Haskell solution: limit = 10^999 fibonacci_numbers = 0:1:(zipWith (+) fibonacci_numbers (tail fibonacci_numbers)) index = length w where w = takeWhile (< limit) fibonacci_numbers main = do putStrLn(show(index)) This probably requires a bit more explanation. I think the variable 'limit' is clear, let's look at the definition of the fibonacci_numbers function. This resolves to a list and is quite simple and logical when we give a bit of thought to it. First, define a few things. ':' - this is the list concat/construct operator, it concatenates the item(s) on its right to the item(s) on its left 'zipWith' - this is a list function, by definition "makes a list, its elements are calculated from the function and the elements of input lists occuring at the same position in both lists" '(+)' - this is the addition operator as a function. What is the Fibonacci sequence? A list of numbers, starting with 0,1 where every other element is the sum of the previous two elements. So, how is this fibonacci_numbers list being built? It has a recursive definition: start with 0 and 1, then calculate all further items by adding the previous two (zipWith (+) does exactly this). We are using this approach because of it's witty speed - it doesn't recalculate previous elements. One other thing about this construct: it's called a lazy list. It's lazy because the elements aren't computed until they're accessed. Also, this is an infinite list. If we tried printing it, it'd go 'forever' (until it has no more free RAM). takeWhile behaves as it name suggests: it takes more and more elements from a list while its function predicate evaluates to true - we are scanning a list until we find an item which is not less than the limit specified. Apart from its speed (an average of 0.008 seconds on my macbook pro) this solution has elegance and is much closer to the original (mathematic) definition of the Fibonacci sequence. Notice the biggest and most important difference between the approaches: The Ruby implementation tells how to calculate the nth item of the Fibonacci sequence, the Haskell version defines what the Fibonacci sequence is. If you liked it, take a look at my older post about solving project Euler problem #1 in erlang here Stay tuned for more Project Euler solutions in haskell and ruby! UPDATE Code after applying HLint (thank you, Neil Mitchell!) suggestions: limit = 10^999 fibonacciNumbers = 0:1:zipWith (+) fibonacciNumbers (tail fibonacciNumbers) index = length w where w = takeWhile (< limit) fibonacciNumbers main = print index Much nicer!

Tagged as: fibonacci, haskell, math, project euler, ruby, solution