使用 Prolog 计算多项式的 GCD

标题已经说明了一切。我正在计算两个多项式的 GCD。有什么办法可以在 Prolog 中完成这个任务吗？如果是这样，什么是好的起点？具体来说，我在如何使用 Prolog 实现多项式除法方面遇到了麻烦。

编辑以包括示例输入和输出：

输入示例：

?-  GCD(x^2 + 7x + 6, x2 − 5x − 6, X).

输出示例：

X = x + 1.

Solution

如果其他人需要这样做，这是我的最终解决方案：

tail([_|Tail], Tail).
head([Head | _], Head).

norm(Old, N, New) :- 
    length(Tail, N),
    append(New, Tail, Old).
norm(Old, N, []) :-
    length(Old, L),
    N > L.

mult_GCD(List, GCD) :- length(List, L),
    L > 2, tail(List, Tail),
    mult_GCD(Tail, GCD).
mult_GCD([H | T], GCD) :-
    length(T, L),
    L == 1, head(T, N),
    gcd(H, N, GCD).

lead(List, List) :-
    length(List, L),
    L == 1.
lead([0 | Tail], Out) :- 
    !, lead(Tail, Out).
lead([Head | Tail], [Head | Tail]) :- Head =\= 0.

poly_deg([], 0).
poly_deg(F, D) :-
    lead(F, O),
    length(O, N),
    D is N - 1.

poly_red([0], [0]).
poly_red(Poly, Out) :-
    mult_GCD(Poly, GCD),
    scal_div(Poly, GCD, Out).

poly_sub(Poly,[],Poly) :- Poly = [_|_].
poly_sub([],Poly,Poly).
poly_sub([P1_head|P1_rest], [P2_head|P2_rest], [PSub_head|PSub_rest]) :-
    PSub_head is P1_head-P2_head,
    poly_sub(P1_rest, P2_rest, PSub_rest).

scal_prod([],_Sc,[]).
scal_prod([Poly_head|Poly_rest], Sc, [Prod_head|Prod_rest]) :-
    Prod_head is Poly_head*Sc,
    scal_prod(Poly_rest, Sc, Prod_rest).

scal_div([],_,[]).
scal_div([Poly_head|Poly_rest], Sc, [Prod_head|Prod_rest]) :-
    Prod_head is Poly_head / Sc,
    scal_div(Poly_rest, Sc, Prod_rest).

poly_div(Num, Den, OutBuild, Out) :-
    poly_deg(Num, X),
    poly_deg(Den, Y),
    X < Y,
    Out = OutBuild.
poly_div(INum, IDen, OutBuild, Out) :-
    lead(INum, [NumHead | NumTail]), lead(IDen, [DenHead | DenTail]),
    Q is NumHead / DenHead,
    append(OutBuild, [Q], Out1),
    append([DenHead], DenTail, DenNorm), append([NumHead], NumTail, Num),
    scal_prod(DenNorm, Q, DenXQ),
    poly_sub(Num, DenXQ, N),
    poly_div(N, IDen, Out1, Out).

poly_mod(Num, Den, Out) :-
    poly_deg(Num, X), poly_deg(Den, Y),
    X < Y,
    lead(Num, Out1),
    poly_red(Out1, Out2),
    lead(Out2, Out).
poly_mod(INum, IDen, Out) :-
    lead(INum, [NumHead | NumTail]), lead(IDen, [DenHead | DenTail]),
    Q is NumHead / DenHead,
    append([DenHead], DenTail, DenNorm), append([NumHead], NumTail, Num),
    scal_prod(DenNorm, Q, DenXQ),
    poly_sub(Num, DenXQ, N),
    poly_mod(N, IDen, Out).

poly_gcd(X, Y, X):- poly_deg(Y, O), O == 0, !.
poly_gcd(Y, X, X):- poly_deg(Y, O), O == 0, !.
poly_gcd(X, Y, D):- poly_deg(X, Xd), poly_deg(Y, Yd), Xd > Yd, !, poly_mod(X, Y, Z), poly_gcd(Y, Z, D).
poly_gcd(X, Y, D):- poly_mod(Y, X, Z), poly_gcd(X, Z, D).

gcd(X, Y, Z) :-
    X < 0, X > Y, !,
    X1 is X - Y,
    gcd(-X, Y, Z).
gcd(X, Y, Z) :-
    Y < 0, Y >= X, !,
    Y1 is Y - X,
    gcd(X, -Y, Z).
gcd(X, 0, X).
gcd(0, Y, Y).
gcd(X, Y, Z) :-
    X > Y, Y > 0,
    X1 is X - Y,
    gcd(Y, X1, Z).
gcd(X, Y, Z) :-
    X =< Y, X > 0,
    Y1 is Y - X,
    gcd(X, Y1, Z).
gcd(X, Y, Z) :-
    X > Y, Y < 0,
    X1 is X + Y,
    gcd(Y, X1, Z).
gcd(X, Y, Z) :-
    X =< Y, X < 0,
    Y1 is Y + X,
    gcd(X, Y1, Z).

这个答案意味着朝着正确的方向推动。

首先，暂时忘记您需要解析如下表达式x^2 + 7x + 6;这在 Prolog 中还不是一个合适的术语。如果你尝试把它写在顶层，你会得到一个错误：

?- Expr = x^2 + 7x + 6.
ERROR: Syntax error: Operator expected
ERROR: Expr = x^2 + 
ERROR: ** here **
ERROR: 7x + 6 . 

Prolog不知道如何处理7x你在那里。解析表达式本身就是一个问题，如果您假设已经解析了它并获得了如下所示的表示，也许会更容易：

[6, 7, 1]

相似地，x^2 − 5x − 6变成：

[-6, -5, 1]

要表示 0，您可以使用空列表：

[]

现在，看一下维基百科页面上的算法。它用deg对于学位和lc为首项系数。通过上面的列表表示，您可以将它们定义为：

次数比保存系数的列表的长度减一。

poly_deg(F, D) :-
    length(F, N),
    D is N - 1.

首项系数是列表的最后一个元素。

poly_lc(F, C) :-
    last(F, C).

您还需要能够使用多项式进行简单的算术运算。使用上的定义维基百科页面，我们看到例如添加[] and [1]应该给你[1], 相乘[-2, 2] with [1, -3, 1]应该给你[-2, 8, -8, 2]. A 前兆搜索给我这个问题在 Stackoverflow 上。使用那里定义的谓词：

?- poly_prod([-2,2], [1, -3, 1], P).
P = [-2.0, 8.0, -8.0, 2] .

?- poly_sum([], [1], S).
S = [1].

从现在开始，您应该可以尝试实现多项式除法，如我上面链接的 Wiki 文章中所述。如果您遇到更多麻烦，您应该编辑您的问题或提出新问题。