Here comes a naive benchmark for C, Java, Erlang, Prolog and Haskell. The benchmark is to compute Pythagorean triples. The triple consists of three positive integers a, b, and c, such that a*a + b*b = c*c and additionally a+b+c<=n, where n=500.

Haskell:

f :: Int -> [ (Int, Int, Int) ] f n = [ (x, y, z) | x <- [ 1 .. n ], y <- [ 1 .. n ], z <- [ 1 .. n ], x + y + z <= n, (x * x) + (y * y) == (z * z) ]Prolog:

pytriangle(N,A,B,C):- between(1,N,A), between(1,N,B), between(1,N,C), A + B + C =< N , A*A + B*B =:= C*C.Erlang:

-module(test). -export([pythag/1]). pythag(N) -> [ {A,B,C} || A <- lists:seq(1,N), B <- lists:seq(1,N), C <- lists:seq(1,N), A+B+C =< N, A*A+B*B =:= C*C ].C:

int main(int argc,char *argv[]){ int a,b,c,n; n=atoi(argv[1]); for (a=1; a<=n; a++) { for (b=1; b<=n; b++) { for (c=1; c<=n; c++) { if ((a+b+c <= n) && (a*a + b*b == c*c)){ printf("%d,%d,%d;",a,b,c); } } } } return 0; }Java:

public class triangles { public static void main(String [] args) { int a,b,c,n; n=Integer.parseInt(args[0]); for (a=1; a<=n; a++) { for (b=1; b<=n; b++) { for (c=1; c<=n; c++) { if ((a+b+c <= n) && (a*a + b*b == c*c)){ System.out.printf("%d,%d,%d;",a,b,c); } } } } } }

Here comes the results (in seconds).

Haskell (GHCi, version 6.12.1): 380

Haskell compiled (GHCi, version 6.12.1): 32

Prolog (SWI Prolog 5.7.4): 197.2

Erlang (R13B03): 59.5

Erlang HiPE (High Performance Erlang), native: 13.2

C (gcc 4.4.3): 0.8

Java (IcedTea6 1.8.1): 2.2 (with output redirected to /dev/null: 1.3)

The winner was obvious from the begining. But it's quite interesting how the declarative languages perform... hmmm. Kudos to Erlang.

By the way, have you noticed that the code is far better readable with the declarative approach?

I found the following CLP(FD) version more than twice as fast as your Prolog version with SWI-Prolog 5.11.6:

ReplyDelete:- use_module(library(clpfd)).

pytriangle(N, A, B, C):-

[A,B,C] ins 1..N,

A + B + C #=< N ,

A*A + B*B #= C*C,

labeling([ff,bisect], [A,B,C]).

Example:

?- time((pytriangle(500, A, B, C), false)).

% 41,035,022 inferences, 17.930 CPU in 18.153 seconds (99% CPU, 2288624 Lips)

false.

Thanks mat! Yo've got the point. CLP is far more suitable for this benchmark. On my PC it gives around 27 seconds which is waaaaaay faster. Thanks again.

ReplyDelete