使用 Prolog 计算多项式的 GCD
Using Prolog to compute the GCD of a polynomial
标题说明了一切。我正在寻找计算两个多项式的 GCD。有什么办法可以在 Prolog 中完成吗？如果是这样，什么是好的起点？具体来说，我在如何使用 Prolog 实现多项式除法方面遇到了问题。
编辑以包含示例输入和输出：
示例输入：
?- GCD(x^2 + 7x + 6, x2 − 5x − 6, X).
示例输出：
X = x + 1.
解决方案
如果其他人需要这样做，这是我的最终解决方案：
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，您将使用空列表：
[]
现在，看看 algorithm at the Wikipedia page。它使用 deg 作为度数，使用 lc 作为前导系数。使用上面的列表表示，您可以将它们定义为：
The degree is one less then the length of the list holding the coefficients.
poly_deg(F, D) :-
length(F, N),
D is N - 1.
The leading coefficient is the last element of the list.
poly_lc(F, C) :-
last(F, C).
您还需要能够使用多项式进行简单的算术运算。使用 Wikipedia page, we see that for example adding [] and [1] should give you [1], multiplying [-2, 2] with [1, -3, 1] should give you [-2, 8, -8, 2]. A precursory search gave me this question here on Whosebug 上的定义。使用那里定义的谓词：
?- poly_prod([-2,2], [1, -3, 1], P).
P = [-2.0, 8.0, -8.0, 2] .
?- poly_sum([], [1], S).
S = [1].
从这里开始，您应该可以按照我在上面链接的 Wiki 文章中概述的那样尝试并实现多项式除法。如果遇到更多麻烦，您应该编辑问题或提出新问题。
标题说明了一切。我正在寻找计算两个多项式的 GCD。有什么办法可以在 Prolog 中完成吗？如果是这样，什么是好的起点？具体来说，我在如何使用 Prolog 实现多项式除法方面遇到了问题。
编辑以包含示例输入和输出：
示例输入：
?- GCD(x^2 + 7x + 6, x2 − 5x − 6, X).
示例输出：
X = x + 1.
解决方案
如果其他人需要这样做，这是我的最终解决方案：
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，您将使用空列表：
[]
现在，看看 algorithm at the Wikipedia page。它使用 deg 作为度数，使用 lc 作为前导系数。使用上面的列表表示，您可以将它们定义为：
The degree is one less then the length of the list holding the coefficients.
poly_deg(F, D) :-
length(F, N),
D is N - 1.
The leading coefficient is the last element of the list.
poly_lc(F, C) :-
last(F, C).
您还需要能够使用多项式进行简单的算术运算。使用 Wikipedia page, we see that for example adding [] and [1] should give you [1], multiplying [-2, 2] with [1, -3, 1] should give you [-2, 8, -8, 2]. A precursory search gave me this question here on Whosebug 上的定义。使用那里定义的谓词：
?- poly_prod([-2,2], [1, -3, 1], P).
P = [-2.0, 8.0, -8.0, 2] .
?- poly_sum([], [1], S).
S = [1].
从这里开始，您应该可以按照我在上面链接的 Wiki 文章中概述的那样尝试并实现多项式除法。如果遇到更多麻烦，您应该编辑问题或提出新问题。