An Arithmetic with Polynomials

多項式を始めとする抽象化された代数上の演算では、記号処理に長けたLispやPrologが本領を発揮する。しかし代数表現の実装としてどのような構造を選ぶかによって、その難しさには大きな差が出る。例えば多項式の場合、恐らく一般的で経済的な表現形式はRisa/asirの採用している分散表現多項式である。これは変数と主項ごとに次数を、主項ごとに係数を行列として保持する形式である。

  3x^3*z+x^2*y^3-5x*y-x*z+2y^3+y+z^2-2
=  c | x  y  z
  ---+---------
   3 | 3  0  1
   1 | 2  3  0
  -5 | 1  1  0
  -1 | 1  0  1
   2 | 0  3  0
   1 | 0  1  0
   1 | 0  0  2
  -2 | 0  0  0

この形式のメリットは明白で、多項式の四則演算が簡便に実装出来る点にある。例えば加算は次数（xyz列）が一致する行の係数（c列）を足せばよい。また乗算は、乗数と被乗数の主項毎に次数行の加算と係数の乗算を行えばよい。減算と除算は逆である。乗算と除算に関しては、同じ主項を生成する場合があるので後から正規形に正す必要がある。ここで云う正規形とは主項を辞書式順序付けで並べた形式を指す。一般的に多項式の表現は一意ではないため（また理論上の取り扱いのため）、このような措置を取る必要がある。

以下にPrologでの加乗算 実装例を示す。

% ordinal/2
ordinal(_C1*L1, _C2*L2) :- ordinal_aux(L1, L2).
ordinal_aux([], []) :- !.
ordinal_aux([X|_], [Y|_]) :- X > Y, !.
ordinal_aux([X|Xs], [X|Ys]) :- !, ordinal_aux(Xs, Ys).
?- ordinal(1*[1, 0, 2],
           1*[1, 1, 1]).
fail.
?- ordinal(1*[0, 1, 2],
           1*[0, 0, 3]).
true.

% norm/2
norm([], []).
norm([C1*L1|R1], P) :-
    !, norm_aux(C1*L1, R1, C2, R3), norm(R3, R2),
    (C2 = 0 -> P = R2;
     P = [C2*L1|R2]).
norm_aux(C1*_L1, [], C1, []).
norm_aux(C1*L1, [C2*L1|R2], C3, R3) :-
    !, norm_aux(C1*L1, R2, C4, R3), C3 is C2 + C4.
norm_aux(T1, [T2|R2], C3, [T2|R3]) :-
    !, norm_aux(T1, R2, C3, R3).
?- norm([2*[1, 0, 1],-1*[1, 0, 1]], Ans).
Ans = [1*[1, 0, 1]].

% add/3
add([], [], []) :- !.
add([], R2, R2) :- !.
add(R1, [], R1) :- !.
add([C1*L|R1], [C2*L|R2], [C3*L|R]) :-
    !, plus(C1, C2, C3), add(R1, R2, R).
add([T1|R1], [T2|R2], [T1|R]) :-
    ordinal(T1, T2), !, add(R1, [T2|R2], R).
add([T1|R1], [T2|R2], [T2|R]) :-
    ordinal(T2, T1), !, add([T1|R1], R2, R).
?- add([ 2*[2, 0, 1], 1*[0, 1, 0],-3*[0, 0, 2],              4*[0, 0, 0]],
       [-1*[2, 0, 1], 1*[0, 1, 0],              2*[0, 0, 1],-2*[0, 0, 0]],
       Ans).
Ans = [1*[2, 0, 1], 2*[0, 1, 0], -3*[0, 0, 2], 2*[0, 0, 1], 2*[0, 0, 0]].

% mult/3
mult(P1, P2, P3) :- mult_aux(P1, P2, P), !, norm(P, P3).
mult_aux([], _R2, []).
mult_aux([T1|R1], R2, P) :-
    !, mult_aux1(T1, R2, P1), mult_aux(R1, R2, P2), append(P1, P2, P).
mult_aux1(_T1, [], []).
mult_aux1(C1*L1, [C2*L2|R2], [C3*L3|R3]) :-
    !, C3 is C1 * C2, mult_aux2(L1, L2, L3), mult_aux1(C1*L1, R2, R3).
mult_aux2([], [], []).
mult_aux2([X|Xs], [Y|Ys], [Z|Zs]) :-
    !, Z is X + Y, mult_aux2(Xs, Ys, Zs).
?- mult([1*[2], 1*[1], 1*[0]],
        [       1*[1],-1*[0]],
        Ans).
Ans = [1*[3],-1[0]].