Prolog, triangular numbers, accumulators and tail recursion

Question

I'm working on a homework assignment, consisting of 2 parts. The first is to write a Prolog program that checks if a certain pair X, Y belongs to a http://en.wikipedia.org/wiki/Triangular_number. For example: (2, 3) = true; (4, 10) = true et cetera.

The first solution uses 'ordinary' recursion, and I've solved this like this:

triangle(0, 0).
triangle(X, Y) :- X > 0, Y > 0, A is X - 1, B is Y - X, triangle(A, B).

The second part is to solve this using tail recursion/an accumulator, using a triangle/3 predicate. Though I have used an accumulator in another assigment, in which the use was quite obvious, so I have a general idea of how to use an accumulator, I'm quite puzzeled as to how to use it in this context.

So, I'm not looking for an algorithm, I'd much rather solve that myself, but more of a practical advise on how to apply an accumulator in this context.

Felix Dombek Felix Dombek · Accepted Answer · 2011-02-19T14:32:07

The beginning is always the same, i.e. the first three lines are basically what you write for each and every tail recursive predicate (with a [] instead of a 0 for list predicates).

From there you can go on without many changes:

 triangle_t(X, Y) :- triangle_t(X, 0, Y).
 triangle_t(0, Y, Y).
 triangle_t(X, Acc, Y) :-
          X > 0,
          A is X - 1,
          AccX is Acc + X,
          triangle_t(A, AccX, Y).

Here are some statistics for large X:

64 ?- time(triangle(1000000,500000500000)).
% 4,000,000 inferences, 0.50 CPU in 0.52 seconds (96% CPU, 8012769 Lips)
true.

65 ?- time(triangle_t(1000000,500000500000)).
% 3,000,001 inferences, 0.41 CPU in 0.44 seconds (92% CPU, 7396405 Lips)
true.

So, while your own predicate is basically already tail recursive (because the recursive call is the last thing to do) the version with an accumulator still saves some time because you do not need the check for Y > 0. If you introduce this line in the triangle_t predicate, they have exactly the same runtime characteristics again:

67 ?- time(triangle_t(1000000,500000500000)).
% 4,000,001 inferences, 0.53 CPU in 0.53 seconds (100% CPU, 7541432 Lips)
true.

Also note that you can now use the predicate to generate the n'th triangular number.

Prolog, triangular numbers, accumulators and tail recursion

1 Answers