9 ms·

Clojure, Haskell & Ruby vs Euler 25

31 points by twism 17y ago

huherto 17y ago
Ok, here is my solution in Java. BigInt makes things simple and there is no need for memoization. public void test25() { BigInt f1 = new BigInt(0); BigInt f2 = new BigInt(1); BigInt f3 = null; int i = 2; while(true) { f3 = f1.add(f2); f1 = f2; f2 = f3; if (f3.toString().length() >= 1000) break; i++; } res("25", 4782, i); }
- vito 17y ago
  Did it in Io (was already doing Euler stuff), pretty similar: problem25 := method(digits, term := 0 n0 := BigNum with(0) n1 := BigNum with(1) loop( n0 = n0 + n1 n1 = n0 - n1 if(n1 asString size >= digits, break) term = term + 1 ) term ) problem25(1000) println
  - deleted 17y ago
    [deleted]
  - huherto 17y ago
    nice!
tedunangst 17y ago
Am I the only person to notice that all 3 programs fail to consider the fact that the first 1000 digit Fibonnaci number may be 10^999?
- deleted 17y ago
  [deleted]
- tel 17y ago
  It's well known not to be.
dons 17y ago
Please, I don't want to see any more benchmarks using fibonacci. NO FIB!!
- kscaldef 17y ago
  Not only is it a silly benchmark, the implementation and methodology is awful. The Ruby code is at a huge disadvantage because it recomputes the whole sequence from scratch every time. The Ruby and Haskell programs print the answer, while the Clojure doesn't. And the LOC comparison is just completely useless. (The Haskell solution can be reduced to 3 lines without excessive golfing, which line up pretty directly with the Clojure, and it could be 1 "line of code" if you wanted.) And, there's no indication of how he's measuring or if he's measuring multiple iterations. In short, this article seems to combine just about everything bad about simple blog article benchmarking in one place.
  - dons 17y ago
    And no description of which compilers, which versions, which compiler flags, what architecture/OS. We have the shootout to answer these questions, and it doesn't include fibonacci.
  - jrockway 17y ago
    Agreed. As Haskell is the only language among the three that I know well, I had to say it was pretty strange looking. The "length w where w = ..." was especially strange. Why not, you know, just apply "length" to that expression? That's what functions do :) I won't comment on the single-expression do block or all the parens in the putStrLn expression or mention that "putStrLn . show" is just "print". Anyway, 6 lines of Haskell is just excessive. How about two lines: fibs = 1 : 1 : (zipWith (+) fibs $ tail fibs) main = print . length . takeWhile (< 10^999) $ fibs I think this is as readable as the example, and I didn't even have to line-break any expression.
    - jules 17y ago
      Here's some Ruby golf: n,a,b = 1,0,1 n,a,b = n+1,b,a+b while b<10**999 p n 48 chars.
jules 17y ago
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.
- klipt 17y ago
  Glad I'm not the only one who cringed at that. Another thing to consider when using phrases like "O(logn)" is that the numbers grow exponentially with n (meaning their lengths grow linearly). Many CS students are trained to think of addition, multiplication etc. as "constant time" operations but that's not true for bignums! BTW, I assume they meant difference equations.
nuggien 17y ago
Not as short as the clojure from the article, but easier to understand (maybe): user> (time (let [limit (.pow (BigInteger/TEN) 999)] (loop [a 0 b 1 i 1] (if (< b limit) (recur b (+ a b) (inc i)) i)))) "Elapsed time: 3.554351 msecs" 4782
seles 17y ago
p (Math.log(10)*999/Math.log(g=5**0.5/2+0.5)+g).ceil

31 points by twism 17y ago

Ok, here is my solution in Java. BigInt makes things simple and there is no need for memoization. public void test25() { BigInt f1 = new BigInt(0); BigInt f2 = new BigInt(1); BigInt f3 = null; int i = 2; while(true) { f3 = f1.add(f2); f1 = f2; f2 = f3; if (f3.toString().length() >= 1000) break; i++; } res("25", 4782, i); }

vito 17y ago
Did it in Io (was already doing Euler stuff), pretty similar: problem25 := method(digits, term := 0 n0 := BigNum with(0) n1 := BigNum with(1) loop( n0 = n0 + n1 n1 = n0 - n1 if(n1 asString size >= digits, break) term = term + 1 ) term ) problem25(1000) println
- deleted 17y ago
  [deleted]
- huherto 17y ago
  nice!

tedunangst 17y ago

Am I the only person to notice that all 3 programs fail to consider the fact that the first 1000 digit Fibonnaci number may be 10^999?

deleted 17y ago
[deleted]
tel 17y ago
It's well known not to be.

dons 17y ago

Please, I don't want to see any more benchmarks using fibonacci. NO FIB!!

kscaldef 17y ago
Not only is it a silly benchmark, the implementation and methodology is awful. The Ruby code is at a huge disadvantage because it recomputes the whole sequence from scratch every time. The Ruby and Haskell programs print the answer, while the Clojure doesn't. And the LOC comparison is just completely useless. (The Haskell solution can be reduced to 3 lines without excessive golfing, which line up pretty directly with the Clojure, and it could be 1 "line of code" if you wanted.) And, there's no indication of how he's measuring or if he's measuring multiple iterations. In short, this article seems to combine just about everything bad about simple blog article benchmarking in one place.
- dons 17y ago
  And no description of which compilers, which versions, which compiler flags, what architecture/OS. We have the shootout to answer these questions, and it doesn't include fibonacci.
- jrockway 17y ago
  Agreed. As Haskell is the only language among the three that I know well, I had to say it was pretty strange looking. The "length w where w = ..." was especially strange. Why not, you know, just apply "length" to that expression? That's what functions do :) I won't comment on the single-expression do block or all the parens in the putStrLn expression or mention that "putStrLn . show" is just "print". Anyway, 6 lines of Haskell is just excessive. How about two lines: fibs = 1 : 1 : (zipWith (+) fibs $ tail fibs) main = print . length . takeWhile (< 10^999) $ fibs I think this is as readable as the example, and I didn't even have to line-break any expression.
  - jules 17y ago
    Here's some Ruby golf: n,a,b = 1,0,1 n,a,b = n+1,b,a+b while b<10**999 p n 48 chars.

jules 17y ago

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.

klipt 17y ago
Glad I'm not the only one who cringed at that. Another thing to consider when using phrases like "O(logn)" is that the numbers grow exponentially with n (meaning their lengths grow linearly). Many CS students are trained to think of addition, multiplication etc. as "constant time" operations but that's not true for bignums! BTW, I assume they meant difference equations.

nuggien 17y ago

Not as short as the clojure from the article, but easier to understand (maybe): user> (time (let [limit (.pow (BigInteger/TEN) 999)] (loop [a 0 b 1 i 1] (if (< b limit) (recur b (+ a b) (inc i)) i)))) "Elapsed time: 3.554351 msecs" 4782

seles 17y ago

p (Math.log(10)*999/Math.log(g=5**0.5/2+0.5)+g).ceil