Archive for the ‘Erlang’ Category
How I beat Project Euler using Erlang: Christmas Edition, problem one
Posted by Giovanni Intini | Filed under Erlang, Euler
Merry Christmas everyone!
It’s been a long time since I wrote a post, but I’ve been very busy coding, and I could only muster some posts for Stacktrace, so express all your Christmas-y goodness and pardon me 
On Stacktrace we just started posting in depth analysis of the Project Euler problems, and I decided to try and solve them using Erlang, since I already did using Ruby a couple of years ago.
The first problem is quite simple:
If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23. Find the sum of all the multiples of 3 or 5 below 1000.
I will not try to give you the clever solution since this problem is quite simple, and the brute force solutions works fine
-module(p1). -export([sum_mul/1]). sum_mul([H|T]) -> valid(H) + sum_mul(T); sum_mul([]) -> 0. valid(H) when H rem 3 =:= 0; H rem 5 =:= 0 -> H; valid(H) -> 0.
To get the solution just call _sum_mul(lists:seq(1,999))_.
Have a Merry Erlang Christmas!
Erlang, Ruby and PHP battle it out!
Posted by Giovanni Intini | Filed under Erlang, Javascript, PHP, Programming, Ruby
Update: here’s the followup!
Yesterday I attended PHP Day, in the beautiful city of Verona, and while going there by train, together with my friend Federico Feroldi, I told him that in a test I made a week ago Erlang was much slower than ruby in finding pythagorean triplets.
That was a partial lie, since the ruby implementation was somewhat optimized, while the erlang implementation wasn’t at all. So we decided to rewrite both programs using the same optimized algorithm and then test their speeds.
This is the ruby implementation of a method that counts the number of pythagorean triplets up to N:
def pythag(n) result = [] (2..n).each do |c| (1...c).each do |b| a = Math.sqrt(c*c - b*b) result << [a.to_i, b, c] if a.to_i == a end end result end
Then we coded it in Erlang. The code I’m going to show you is more complex than the ruby code because we took advantage of the parallelization features of the Erlang language:
-module(pythag). -export([bard/1, pbard/1]). my_is_integer(X) -> round(X) == X. pbard(N) -> pmap(fun(C) -> [ {C, B, trunc(A)} || B <- lists:seq(C, N), A <- [math:sqrt(C*C + B*B)], my_is_integer(A) ] end, lists:seq(2, N)). bard(N) -> lists:map(fun(C) -> [ {C, B, trunc(A)} || B <- lists:seq(C, N), A <- [math:sqrt(C*C + B*B)], my_is_integer(A) ] end, lists:seq(2, N)). pmap(F, L) -> S = self(), %% make_ref() returns a unique reference %% we'll match on this later Ref = erlang:make_ref(), Pids = lists:map(fun(I) -> spawn(fun() -> do_f(S, Ref, F, I) end) end, L), %% gather the results gather(Pids, Ref). do_f(Parent, Ref, F, I) -> Parent ! {self(), Ref, (catch F(I))}. gather([Pid|T], Ref) -> receive {Pid, Ref, Ret} -> [Ret|gather(T, Ref)] end; gather([], _) -> [].
The pythag function has been named bard, as in The Bard
The pbard function fires up a thread for each iteration of the outer loop and then gathers all the result back. This allows for up to 50% performance increase when using dual core CPUs (like my Macbook Pro ).
Once we coded it in two languages we couldn’t stop, so here’s a PHP implementation, a Javascript one and, last, but not least, a C implementation, because you can never forget C when you need speed
PHP:
<?php $i=0; for ($c = 2; $c <= 5000; $c++) { for ($b = 1; $b < $c; $b++) { $a = sqrt($c*$c - $b*$b); if (is_int($a)) { $i++; } } } print("$i"); ?>
JavaScript:
function pythag(n) { var a,b,c,i for (c = 2; c <= n; c++) { for (b = 1; b < c; b++) { a = Math.sqrt(c*c - b*b); if (Math.floor(a) == a) { i++; } } } return i; }
C:
#include <stdio.h> #include <math.h> #define MAX 5000 int main() { double c, b; int i = 0; double a; for (c = 2; c <= MAX; c++) { for (b = 1; b < c; b++) { a = sqrt(c*c - b*b); if (trunc(a) == a) { i++; } } } printf("%d\n", i); }
To test the various relative speeds I ran them from the shell using time (php ruby and c), or used the internal timer (erlang), or ran them in firefox (js only actually).
The results were interesting. At the first run, using 5000 as N in the pythag functions the order was:
- C (obviously): 0.40s
- Erlang (smp): 3.95s
- Erlang (non-smp): 5.66s
- Ruby: 15.31s
- PHP: 19s (or so)
- Javascript: couldn’t even finish running because firefox said it was taking too much time
Fullo passed by and asked what we were doing, I told him I was testing languages and that PHP was dog-slow. He said it couldn’t be and asked me what version of PHP I was using. I checked and it was PHP 4.x.x.
After downloading and compiling PHP5 I ran the tests again and the final result was this:
- C (obviously): 0.40s
- Erlang (smp): 3.95s
- Erlang (non-smp): 5.66s
- PHP5: 8.9s (or so)
- Ruby: 15.31s
- Javascript: couldn’t even finish running because firefox said it was taking too much time
Now the numbers make sense. Doing these comparations was a nice experience, because when you implement the same thing in different languages you always learn something about optimization and code beauty.
Learning Erlang: The Beautiful Quicksort
Posted by Giovanni Intini | Filed under Erlang, Learning Erlang, Programming
Sometimes you really have to stop and contemplate how beautiful code is. This is an erlang quicksort algorithm, one of the most efficient (if I remember correctly it’s the most efficient) sorting algorithms. I still remember the pains of implementing it in C.
qsort([]) -> []; qsort([Pivot|T]) -> qsort([X || X <- T, X =< Pivot]) ++ [Pivot] ++ qsort([X || X <- T, X > Pivot]).
Short + Clean + Elegant = Beautiful.
Erlang and Poker
Posted by Giovanni Intini | Filed under Erlang, Programming
Just when I started writing some poker odds analysis code in Erlang, a friend sent me this link. Sometimes it looks like the Universe really wants you to do something, isn’t it?
Learning Erlang, day 1: No Variables?
Posted by Giovanni Intini | Filed under Erlang, Learning Erlang, Programming
I first heard of Erlang from SamePlace creator, Massimiliano Mirra. He mostly praised the functional nature of the language and its performance.
I always listen to my friends, so I made a mental note, and every once in a while I tried to start with Erlang, but other stuff(tm) always got the priority.
A few days ago, generating a burst of blog posts, the Pragmatic Programmers released the beta version of Programming Erlang. This was not a coincidence. When both Massimiliano and the Pragmatic Programmers suggest you should learn a new language you better do it, and be happy
So I went to the pragprog website and looked through the table of contents. It was really interesting and I bought the beta book.
Yesterday I got my hands wet with erlangness for the first time and decided to create a new category of posts, Learning Erlang, that will be filled with my observation about my efforts to learn a functional language after all these years of object orientedness.
The first thing you will notice when working with erlang is that there are no variables. Ok, stop, don’t close the browser, it’s not entirely true, there are variables, but you can assign them only once.
To better explain how erlang treats variables I’ll show you a snippet taken from the erlang interactive interpreter, erl:
Eshell V5.5.3 (abort with ^G) 1> X = 45. 45 2> X. 45 3> X = 23.=ERROR REPORT==== 15-Mar-2007::09:55:53 ===
Error in process <0.29.0> with exit value: {{badmatch,23},[{erl_eval,expr,3}]}
- exited: {{badmatch,23},[{erl_eval,expr,3}]} **
4> X = 45.
45
Line 1 just assigns the X variable (in erlang variables start with a capital letter, and statements end with a period). What erlang really does here is matching X with 45. It notices that X is unbound and does whatever it can to make the statement true, so it binds X to 45. In line 2 we just check what X is bound to. In line 3 we learn how erlang works by trying to match X (now 45) to 23. Boom! nasty error for us. Being very scared, in line 4 we try to match X to 45, just in case, and we notice erlang likes that statement.
I promise that once you get used to this way of handling variables it doesn’t look so strange anymore