使用Prolog计算多项式的GCD

Question

标题类似于说明了一切.我想要计算两个多项式的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).

Answer 1

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

首先,忘了你需要解析一个表达式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).

您还需要能够使用多项式进行简单算术.使用上的定义维基百科页面,我们可以看到,例如添加[]和[1]应该给你[1],乘以[-2, 2]与[1, -3, 1]应该给你[-2, 8, -8, 2].一个前期搜索在Stackoverflow上给了我这个问题.使用那里定义的谓词:

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

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

从这里开始,你应该可以尝试实现我上面链接的Wiki文章中概述的多项式除法.如果你遇到更多麻烦,你应该编辑你的问题或者问一个新问题.