Path: utzoo!mnetor!uunet!mcvax!prlb2!kulcs!bimbart From: bimbart@kulcs.uucp (Bart Demoen) Newsgroups: comp.lang.prolog Subject: Re: triangle puzzle (496-497) Message-ID: <1153@kulcs.UUCP> Date: 24 Feb 88 10:40:04 GMT Reply-To: bimbart@kulcs.UUCP (Bart Demoen) Organization: Katholieke Universiteit Leuven, Dept. Computer Science Lines: 103 In news letter, we found a solution to the triangle problem, to which we will refer as the ......program: not naming the author nor the company he works for, is not out of maliciousness, rather because the not mentioned author refuses systematically to name BIMprolog when naming other prolog implementations. During a coffee break (no, if you think ......program stands for KOffeeprogram, your are wrong, yes you are :-), we asked ourselves 2 questions: 1. how easy is it to write a program that is faster than the ......program and still readable 2. how relevant is the figure 0.75 quoted for finding the first solution (to be honest: ...... himself says that this figure 'doesn't mean much') Before we looked at the ......program, we wrote our own, which we will refer to as the BIMprogram. Our findings are summarized in the following table: there are 15 possible starting positions, numbered from 1 to 15, as in the triangle below: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 The figures mentioned in the column under BIMprogram and ......program, represent the cputime in seconds needed to find the first solution. start position BIMprogram ......program -------------- ---------- ------------- 1 0.500000 0.660000 2 9.780001 12.740001 3 42.760002 55.980000 4 0.539997 0.680000 5 25.719997 33.900002 6 0.059998 0.080002 7 0.520004 0.659996 8 18.820000 24.659996 9 10.680000 14.000000 10 0.519997 0.660004 11 9.779999 12.779999 12 32.980003 43.180008 13 0.520004 0.659988 14 32.660004 42.800003 15 10.300003 14.079987 4 conclusions: 1. the BIMprogram is systematically about 30% faster than the ......program 2. the figure 0.75 is absolutely no indication of the quality of the prolog program or the prolog implementation: the order of the facts (or rules) for 'jump' is the most important factor determining the time needed to find the (a !) first solution 3. the BIMprogram is really a partially evaluated version of the ......program, but not at all less readable ... just to give you the flavour: the 12th startposition is represented by: start(12,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1). and the 'jump' facts are replaced by rules: jump(_A,1,_C,_D,1,_F,_G,_H,0,_J,_K,_L,_M,_N,_O,['2 to 9'|_restjumps],_n) :- _m is _n - 1, jump(_A,0,_C,_D,0,_F,_G,_H,1,_J,_K,_L,_M,_N,_O,_restjumps,_m) . the stop condition is : jump(_A,_B,_C,_D,_E,_F,_G,_H,_I,_J,_K,_L,_M,_N,_O,[],1) . /*put at the end and not first, although it is a simple case*/ and the query to get the first solution from starting position 12 is: ?- start(12,_A,_B,_C,_D,_E,_F,_G,_H,_I,_J,_K,_L,_M,_N,_O,_s), jump(_A,_B,_C,_D,_E,_F,_G,_H,_I,_J,_K,_L,_M,_N,_O,_jumplist,14) , write(_jumplist) . 4. why is the BIMprogram faster ? less ALLOCATE's no creation on the heap of new structures; no UNIFY's a lot of optimised away GET_'s and PUT_'s the disadvantage of having longer choicepoints does not outweight the above advantages moreover, a lot less heap and local stack are used ! bimbart@kulcs.uucp andre@sunbim Bart Demoen Andre Marien Dept. of Computer Science BIM Celestijnenlaan 200A Kwikstraat 4 B-3030 Leuven B-3078 Everberg Belgium Belgium