Proof that Prolog can be faster than C

[vanroy at pisces.uucp]

Benchmark timings:

Benchmark	Prolog  	C (no opt.)	C (opt. 4)

tak(24,16,8)    1.2		2.1		1.6

All three timings are in user seconds (with 'time') measured on a 25 MHz MIPS
processor.  The Prolog version is compiled with the Aquarius Prolog compiler
under development at Berkeley.  The C versions are compiled with the MIPS C
compiler, with no optimization and full optimization (level 4).

Disclaimer: this benchmark has a particularly easy translation to C.
The result does not necessarily hold for other programs.  But don't
you believe it anymore that Prolog is slow!

	Peter Van Roy

-------------------------------------------------------------------------------

/* C version of tak benchmark */

#include <stdio.h>

int tak(x,y,z)
int x, y, z;
{
  int a1, a2, a3;
  if (x <= y) return z;
  a1 = tak(x-1,y,z);
  a2 = tak(y-1,z,x);
  a3 = tak(z-1,x,y);
  return tak(a1,a2,a3);
}

main()
{
  printf("%d\n", tak(24, 16, 8));
}

-------------------------------------------------------------------------------

/* Prolog version of tak benchmark */

main :- tak(24,16,8,X), write(X), nl.

tak(X,Y,Z,A) :- X =< Y, Z = A.
tak(X,Y,Z,A) :- X > Y,
        X1 is X - 1, tak(X1,Y,Z,A1),
        Y1 is Y - 1, tak(Y1,Z,X,A2),
        Z1 is Z - 1, tak(Z1,X,Y,A3),
        tak(A1,A2,A3,A).

-------------------------------------------------------------------------------