Prolog - Multiplication by recursive addition

Question

I am trying to recursively do addition to multiply two numbers in swi-prolog. I am currently learning Prolog and I do not want to use any library like clpfd.

mult(A, B, C) :- A < B, mult(B, A, C). % always make the first number bigger
mult(A, B, C) :- B > 0, B1 is B - 1, mult(A, B1, A + C). % keep adding
mult(A, B, C) :- B == 0, C is 0. % base case

'C' is supposed to be the result.

This is trying to replicate the following algorithm in Java:

int product(int x, int y) 
{ 
    # first prolog line
    if (x < y) 
        return product(y, x); 
    
    # second prolog line
    else if (y != 0) 
        return (x + product(x, y - 1)); 
   
    # third prolog line
    else
        return 0; 
}

However, no matter how I vary the input, the result will always be 'false'. I was able to step through my instructions with :- trace., but I cannot find out how to fix this.

tiffi tiffi · Accepted Answer · 2021-03-05T22:27:47

The problem is the last literal of your second clause: mult(A, B1, A + C).

What you really want is the result of A*B1 to add that to A.

So try replacing this line with:

mult(A, B, C) :- B > 0, B1 is B - 1, mult(A, B1, C1), C is A + C1.

Prolog - Multiplication by recursive addition

1 Answers