Clojure, Haskell & Ruby vs Euler 25 | Hacker News Reader

Clojure, Haskell & Ruby vs Euler 25

bestinclass.dk

31 pointstwism18 comments

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.

Nice but all you're proving is that you know Ruby and you don't know Clojure. I'll gladly admit I don't know Ruby.

  (defn fib [n a b lim] (if (< b lim) (recur (inc n) b (+ a b) lim) n))
  (fib 1 0 1 (.pow (BigInteger/TEN) 999))

~0.0014 on my machine.

EDIT: I don't condone the article at all, it's link bait. And I think it's silly that people get up in arms about articles like this. Ruby is great. Haskell is great. Haskell and Clojure are really fast. End of story.

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.

Good point. Can you work out the asymptotics of the binary search algoritm, assuming multiplication is O(f(n))?

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

NO FIB!!

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.

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.

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.

Very nice. Looks like assembly language :)

Hm, I don't think it's that bad. It's just the usual fib algorithm:

    a,b = 0,1
    a,b = b,a+b while b<limit

With a counter interspersed ;)

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.

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);
    }

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

nice!

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

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

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?

It's well known not to be.

Reply on news.ycombinator.com