剰余

Prologで作る数学の世界―Prologそして集合‐位相‐群の第４章の問題。余りを求めろ。

abs(A, B) :- A > 0 -> B is  A ; B is -A.

% 条件は
% A = B * Q + R, 0 <= R < abs(B) 
% 割る数の絶対値よりも余りが小さい
res_q(A = B*Q + R) :-
        abs(B, B1),
        Q1 is A // B,
        (B1 > A - B*Q1,A - B*Q1 >= 0  ->
        Q is Q1; Q is Q1 - B1 // B),
        R is A - B*Q.

% 条件は
% A = B * Q + R, - abs(B)/2 < R < abs(B)/2
% 余りの絶対値が最も小さくなる。「余りの絶対値最小割り算」というらしい。
res_q2(A = B*Q + R) :-
        abs(B, B1),
        Q1 is A // B,
        (A - B*Q1 >= B1/2     -> Q is Q1 + B1 // B;
         -B1/2    >= A - B*Q1 -> Q is Q1 - B1 // B;
         Q is Q1),
        R is A - B*Q.