Re: Computing binomial coefficients (puzzle)

In message <pan.2007.11.15.20.16.47.158697@xxxxxxxxxxxxxx>, bart demoen <bmd@xxxxxxxxxxxxxx> writes
On Thu, 15 Nov 2007 19:14:47 +0000, Nick Wedd wrote:

binomial( 0, _, 0 ) :- !.
binomial( X, 1, X ) :- !.
binomial( X, X, 1 ) :- !.
binomial( P, Q, R ) :-
P1 is P-1,
Q1 is Q-1,
binomial( P1, Q, R1 ),
binomial( P1, Q1, R2 ),
R is R1+R2.

You can't make that tail-recursive, as it uses double recursion. You
can make it a lot faster by using tabling.

I am afraid I have to shatter your belief :-)

Every Prolog program can be transformed in a slavish way to
a binary program - such programs don't have double recursion.
BinProlog uses that property. Here is a binarized version of
your doubly recursive binomial/3, named bin/3:

bin(X,Y,Z) :- bin2(X,Y,Z,true).

bin2( 0, _, 0 , C) :- !, call(C).
bin2( X, 1, X , C) :- !, call(C).
bin2( X, X, 1 , C) :- !, call(C).
bin2( P, Q, R , C) :-
P1 is P-1,
Q1 is Q-1,
bin2( P1, Q, R1 , bin2( P1, Q1, R2 , myplusis(R,R1,R2,C))).

myplusis(R,R1,R2,C) :- R is R1 + R2, call(C).

If you think I have cheated in making your double recursion into
tailrecursion, let us know.

One can avoid the need for the metacall (and metapredicates in general)
as well. It has been known since long that binary clauses are
Turingcomplete. A simple proof consists in writing a Universal Turing
Machine with binary clauses. And one needs only one predicate symbol.

My first thoughts were, definitely not cheating, just ugly and unintuitive. And it ought to run a fair bit faster because of tail-recursion. So I decided to test it to see how much faster, using SWI Prolog in its default configuration.

My code, as quoted above, took about a quarter of an hour an hour to do "binomial(34,13,X).", and gave the answer as 927983760. Your code, as quoted above, responded rapidly to "bin(34,13,X)." with a local stack overflow error. This surprised me.

Nick
--
Nick Wedd nick@xxxxxxxxxxxxx
.

Relevant Pages