Prolog - multiplying by addition

Question

I need simple fuction in SWI-prolog which multiplying by addition. Something like m(X,Y,Z) where for example X=5, Z=3 <==> 5*3. Y is result: Y=5, Y=10, Y=15 [stop]. I was thinking about something like that:

m(X,Y,Z):- Z>0, /*when Z reaches 0 you stop */ I=X+X, W=Z-1, m(I,Y,W).

But it always return "false" and dunno why.

It returns false because it continues to call itself until Z goes to zero, then it fails since Z > 0 no longer succeeds. There is no success case. Where did you tell Prolog what the rule is for Z = 0 case? — lurker
You probably want I is X+X, W is Z-1 instead of using =/2 (which means unify, not assign). — Daniel Lyons

tas tas · Accepted Answer · 2017-10-13T22:24:54

Let's start by thinking about what the predicate should describe: it's a relation between three numbers, where the third is the product of the first two. Since you want to describe multiplication by reducing the second argument to zero while adding up the first accordingly many times we are talking about natural numbers. So a nicely descriptive name would be nat_nat_prod/3. Next consider the possible cases:

The second argument can be zero. Then the product has to be zero as well since X*0=0. So this is the base case.
Otherwise the second argument is greater than zero. Then you want to decrement it by one and calculate the product of the first argument and this new number. Since the predicate can use itself to describe that, this is a recursive goal. Subsequently you add the first argument to the intermediary product described by the recursion.

This can be written in Prolog like so:

nat_nat_prod(_X,0,0).         % case 1)
nat_nat_prod(X,Y1,P1) :-      % case 2)
   Y1 > 0,
   Y0 is Y1-1,
   nat_nat_prod(X,Y0,P0),
   P1 is P0+X.

Now let's try some queries:

?- nat_nat_prod(5,3,P).
P = 15 ;
false.

?- nat_nat_prod(5,4,P).
P = 20 ;
false.

?- nat_nat_prod(5,0,P).
P = 0 ;
false.

?- nat_nat_prod(1,0,P).
P = 0 ;
false.

?- nat_nat_prod(1,1,P).
P = 1 ;
false.

However, when playing around with the predicate, you'll notice that the first two arguments have to be instantiated otherwise you'll get an error:

?- nat_nat_prod(1,Y,3).
ERROR: >/2: Arguments are not sufficiently instantiated
?- nat_nat_prod(X,1,3).
ERROR: is/2: Arguments are not sufficiently instantiated

This happens due to the use of >/2 and is/2. You could get around this problem by using CLP(FD) but I think that's beside the point. This way of defining multiplication is obviously very inefficient compared to using the standard arithmetic function */2, e.g.:

?- time(nat_nat_prod(2,1000000,P)).
% 3,000,000 inferences, 33.695 CPU in 33.708 seconds (100% CPU, 89035 Lips)
P = 2000000 ;
% 3 inferences, 0.031 CPU in 0.031 seconds (100% CPU, 97 Lips)
false.

?- time(P is 2*1000000).
% 1 inferences, 0.000 CPU in 0.000 seconds (86% CPU, 82325 Lips)
P = 2000000.

As already hinted by @false in the comments it is more common to introduce people to successor arithmetics first and then to define addition/multiplication of two numbers in s(X) notation this way. Since you can't use the standard arithmetic functions with s(X) numbers, you also don't run into the associated instantiation errors.

Prolog - multiplying by addition

1 Answers