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!
Related posts:
39 comments
Trackbacks/Pingbacks
- Csaba Okrona - Ruby vs. Haskell – project Euler #25 deathmatch http://is.gd/8rr4p
- Leandro N. Padula - Ruby vs. Haskell: http://is.gd/8t5rp
- Ruby News - Ruby vs. Haskell – project Euler #25 deathmatch http://bit.ly/97bh2Y
- takkanm - RT @ruby_news: Ruby vs. Haskell – project Euler #25 deathmatch http://bit.ly/97bh2Y
- ??????? - ??? index = fromJust . findIndex (>= limit) $ fibonacciNumbers ?? http://blog.mostof.it/ruby-vs.-haskell-project-euler-25-deathmatch
- Jérémy Lecour - Ruby vs. Haskell – project Euler #25 deathmatch http://bit.ly/97bh2Y /via @ruby_news cc @alpmestan
- Project Euler and Erlang – introduction, problem #1 | implements Developer { - [...] you liked this, check out my haskell-ruby solution to problem #25! ...
- mfcastellani - rt @ruby_news Ruby vs. Haskell – project Euler #25 deathmatch http://bit.ly/97bh2Y
- Richard Laksana - Ruby vs. Haskell – project Euler #25 deathmatch - http://su.pr/9wyESj
Leave a Reply
Additional comments powered by BackType
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.
This comment was originally posted on Reddit
[Reply]
Ruby vs. Haskell – project Euler #25 deathmatch http://is.gd/8rr4p
This comment was originally posted on Twitter
[Reply]
Just an FYI, you are over-parenthesizing your Haskell code. As such, you can write the Haskell much simpler as:
limit = 10^999
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
main = print . length . takeWhile (< limit) $ fibs
[Reply]
ochronus Reply:
February 15th, 2010 at 20:03
Thanks for the tip, I’m a Haskell newbie coming from the C/java/ruby/php world :)
[Reply]
Ruby vs. Haskell: http://is.gd/8t5rp
This comment was originally posted on Twitter
[Reply]
If you use HLint (http://community.haskell.org/~ndm/hlint) it would have spotted some of the redundant brackets (although it wouldn’t have ended up as nice as Don’s code)
[Reply]
It’s nice, but I wish people did less fib and factorial examples in Haskell. It gets a bit embarrassing.
[Reply]
Thanks for the tip about HLint, I didn’t know about that.
About fib/fact examples: I’m solving the project euler problems, and I’m actually at #25, that’s why I posted about it. But you’re right, I could also probably write even faster code in C, but it wasn’t speed that I wanted to demonstrate.
[Reply]
Sorry, I don’t get in which way your ruby approach is straightforward. I’d consider something like this much more so:
limit = 10**999
i = 0
n, m = 0, 1
while n < limit do
n, m = m, n + m
i += 1
end
puts i
[Reply]
ochronus Reply:
February 16th, 2010 at 16:18
@Rörd, I’ve benchmarked your version, it has an average of 0.015 seconds on my machine :) Much closer to the haskell version!
[Reply]
Rörd: you’re right, that’s a much better close-up solution for the problem and also much faster. I wanted to abstract the concept of the fibonacci series though. When I’m dealing with project euler problems, I usually approach them with a quick-and-dirty solution first (such as yours), then I try to abstract. I’m not heading for speed.
[Reply]
Why did you publish project Euler solution? There are so many other nice problems to demonstrate diferences between languages.
[Reply]
ochronus Reply:
February 16th, 2010 at 15:37
Hlupacek: You’re right, there’s a huge list of possible problem domains for this, but I’m progressing in the list of project Euler problems (for my own joy) and it came in handy. I’m also learning Haskell now, so it seemed like a good combination. Probably when I get more proficient in the language I’ll be able to do more complex things :)
[Reply]
The Ruby algorithm here is a different one, and probably less efficient.. One of the comments suggested the Haskell algorithm in imperative form, and he should benchmark that.
This comment was originally posted on Reddit
[Reply]
I’ve benchmarked it (I think you meant the more optimized ruby version) and it’s much closer to the haskell one’s performance, but see my reply on that comment, I wasn’t heading for speed/performance.
This comment was originally posted on Reddit
[Reply]
Ruby vs. Haskell – project Euler #25 deathmatch http://bit.ly/97bh2Y
This comment was originally posted on Twitter
[Reply]
We don’t need more fibonacci benchmarks. They always go into stupid land — not measuring the same thing, and reaching odd conclusions about performance in general. This is why "nofib" is a 20 year old Haskell testsuite.
This comment was originally posted on Reddit
[Reply]
??? index = fromJust . findIndex (>= limit) $ fibonacciNumbers ?? http://blog.mostof.it/ruby-vs.-haskell-project-euler-25-deathmatch
This comment was originally posted on Twitter
[Reply]
Ruby vs. Haskell – project Euler #25 deathmatch http://bit.ly/97bh2Y /via @ruby_news cc @alpmestan
This comment was originally posted on Twitter
[Reply]
[Haskell is great!](http://imgur.com/vv9OO.png)
This comment was originally posted on Reddit
[Reply]
Sorry guys I probably missed to emphasize my point enough in the post – I didn’t want to compare/do benchmarks… my primary goal was to write about a naive Haskell newbie’s thoughts about his two favourite languages and compare the two ways (of many) to solve a simple maths problem. My apologies for not being clear :(
This comment was originally posted on Reddit
[Reply]
Edvin Aghanian Reply:
February 16th, 2010 at 22:37
@ochronus, I don’t think you need to apologize. You wrote some comparison code in two languages, which resulted in a conversation and contributions from people on how to improve your code in both languages. I drew benefit from seeing some Haskell in action, and then seeing how it can be reformatted to look very elegant. Frankly, I’m amazed how negatively people react to these kinds of posts.
[Reply]
ochronus Reply:
February 16th, 2010 at 22:44
@Edvin Aghanian, Thanks for the kind words, but they are right that I made a mistake with choosing a title that suggests a benchmark, so that criticism is fair, I feel. I’m also happy about the constructive additions people made – and I’m glad the post proved useful :)
[Reply]
"Deathmatch" might have been a bit misleading :-)
This comment was originally posted on Reddit
[Reply]
Hall of shame / catchy titles, I get it :)
This comment was originally posted on Reddit
[Reply]
Anyway, points taken, thanks for the comments and suggestions, I will watch out for these mistakes in my forthcoming posts.
This comment was originally posted on Reddit
[Reply]
Yes, you’re right, the same goes for almost all mathematical constructs. I only wanted to show/sugges the ease and naturalness of the Haskell representation of the Fibonacci series – which is also the basic difference (for me at this point) of the imperative and functional approaches.
This comment was originally posted on Reddit
[Reply]
I like to write:
Prelude> let fib x y = y:fib y (x+y)
Prelude> take 20 $ fib 0 1
[1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765]
That is a little easier to understand than the zip version, I think.
[Reply]
ochronus Reply:
February 16th, 2010 at 19:17
@solrize, thanks for the idea, that’s right – it’s easier to comprehend.
[Reply]
Not as concise as Haskel, but based on the same idea:
fibs = Enumerator.new { |y| a, b = 0, 1; loop { y.yield a; b, a = a, a+b } }
fibs.take_while { |f| f < 10**999 }.last
[Reply]
ochronus Reply:
February 16th, 2010 at 19:40
@Shot, Nice one, thanks :) I like it!
[Reply]
Shot Reply:
February 16th, 2010 at 19:43
…although the actual answer to the question is obtained with
fibs.find { |f| f >= 10**999 }
:)
[Reply]
ochronus Reply:
February 16th, 2010 at 19:49
@Shot, and also don’t calculate 10**999 in every cycle :)
[Reply]
Either way… it’s kinda silly given that there’s a closed form soln for fibonacci…
This comment was originally posted on Reddit
[Reply]
Ruby vs. Haskell – project Euler #25 deathmatch – http://su.pr/9wyESj
This comment was originally posted on Twitter
[Reply]
Web technologies like PHP, Javascript, HTML, CSS also seem a must to learn. Even if you are not going to be a pro in these, they help when you want to maintain or tweak your website or blog.
[Reply]
Matrix exponentiation, while a very fast way to calculate an arbitrary fibonacci number, is much slower than simple addition when all you want to do is get the next fibonacci number. However, you get *two adjacent* fibonacci numbers from one matrix exponentiation, which you can then use to get the next (or previous) number. So you might consider some kind of search (e.g. binary, although there would be better choices given the nature of the problem), combined with a linear scan once you get close enough. But really, that level of algorithmic sophistication is overkill for this particular problem…
This comment was originally posted on Reddit
[Reply]
Right, thanks for the clarification. Someone also posted a specific faster solution for this problem using simple addition – which I avoided by decision. But again, probably that’s even more imperative… :)
This comment was originally posted on Reddit
[Reply]
Thanks for the clarification, great article
[Reply]