Divison and remainder in Prolog

Question

Trying to figure out how to write a recursive predicate divide_by(X, D, I, R) that takes as input a positive integer X and a divisor D, and returns the answer as the whole number part I and the remainder part R, however, I can't seem to get my head around Prolog. How would I go about doing this?

Answer 1

There are predefined evaluable functors for this.

(div)/2 and (mod)/2 always rounding down. Recommended by LIA-1, Knuth etc.

(//)/2 and (rem)/2 rounding toward zero (actually, it's implementation defined, but all current implementations do it like that). You can ask this via current_prolog_flag(integer_rounding_function, F) which gives in current implementations toward_zero.

The difference between those pairs shows only when negative numbers are involved. It is kind of a religious war which one to prefer. ISO/IEC 10967:2012 Language independent arithmetic (vl. LIA-1) only provides rounding down "due to proneness for erroneous use" (C.5.1.2.2) of toward_zero, whereas Fortran and followers like C go for toward_zero calling it "algebraic" (6.5.5). See also: Advantages of using truncation towards minus infinity vs towards zero

Answer 2

I'm assuming your teacher is trying to teach recursion.

Division is repeated subtraction, just as multiplication is repeated addition, n'est-ce-pas?

A common prolog idiom, since variables can only be assigned a value once, is to have an outer "public" predicate, that invokes a private "worker" predicate that uses the accumulator(s) and does the actual work. This leads us to a solution like this.

%
% divide M (the dividend) by N (the divisor),
%yielding the quotient (Q) and remainder (R).
integer_division( M , N , Q , R ) :-
  M > 0 ,
  N > 0 ,
  div_rem( M , N , 0 , Q , R )
  .

%
% internal worker predicate for integer division
% requires dividend and divisor both to be unsigned (positive).
%
div_rem( M , N , Q , Q , M ) :-  % dividend M < divisor N? We're done.
  M < N ,                        % - unify the accumulator with the quotient 
  .                              % - and unify the divisor with the remainder
div_rem( M , N ,T , Q , R ) :-   % dividend M >= divisor N?
  M >= N ,                       % - increment the accumulator T
  T is T+1 ,                     % - decrement the divisor by N
  M1 is M-N ,                    % - recurse down
  div_rem( M1 , N , T1 , Q , R ) % - That's all.
  .                              % Easy!

From this it should be pretty easy to modify the outer public predicate to account for signed operands, bearing in mind that

• +/+ yields +
• +/- yields -
• -/+ yields -
• -/- yields +

And that having evaluated M/N to obtain quotient Q and remainder R, the property

M = N * Q + R

holds true. That should inform you as to the required signs for the quotient and remainder. Don't forget that addition of a negative number is the same as subtraction: M + -N is equivalent to M - N. That will get you to results that are mathematically correct (which may differ from the results obtained via your computer's integer division instructions). One should note that for the property noted above to be true, the sign of the quotient and the sign of the remainder may differ.

Answer 3

If you had to limit your arithmetic operations to addition, subtraction, then you could use recursion as follows:

divit(Dividend, Divisor, Q, R) :-
    Dividend > 0,    % Only allow positive dividend
    Divisor \== 0,   % Don't allow 0 divisor
    % Use an accumulator (starts at 0) for the quotient, counting subtractions
    % of the divisor from the dividend 
    divit(Dividend, Divisor, 0, Q, R).

% If Dividend < Divisor, then
%    quotient accumulator is quotient and dividend is remainder, done!
divit(Dividend, Divisor, Qacc, Qacc, Dividend) :-
    Dividend < Divisor.

% If Dividend >= Divisor, then
%    subtract the divisor from the dividend
%    increment the quotient accumulator
%    recurs on updated dividend and quotient accumulator until dividend < divisor
divit(Dividend , Divisor, Qacc, Q, R) :-
    Dividend >= Divisor,
    D1 is Dividend - Divisor,
    Qacc1 is Qacc + 1,
    divit(D1, Divisor, Qacc1, Q, R).