使用 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).头([头| _]，头).规范(旧，N，新):-长度(尾，N)，追加(新，尾，旧).规范(旧，N，[]): -长度(旧，L)，N＞L.mult_GCD(List, GCD) :- 长度(List, L),L>2、尾部(列表，尾部)，mult_GCD(尾，GCD).mult_GCD([H | T], GCD) :-长度(T，L)，L == 1, head(T, N),gcd(H, N, GCD).铅(列表，列表): -长度(列表，L)，L==1.铅([0 |尾]，出): -！，铅(尾，出).铅([头|尾]，[头|尾]):-头=\= 0.poly_deg([], 0).poly_deg(F, D) :-铅(F，O)，长度(O，N)，D 是 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 是 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 是 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 是 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＜是，出 = 出建.poly_div(INum, IDen, OutBuild, Out) :-铅(INum，[NumHead | NumTail])，铅(IDen，[DenHead | DenTail])，Q 是 NumHead/DenHead，追加(OutBuild，[Q]，Out1)，追加([DenHead]，DenTail，DenNorm)，追加([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＜是，领先(数量，Out1)，poly_red(Out1, Out2),铅(输出2，输出).poly_mod(INum, IDen, Out) :-铅(INum，[NumHead | NumTail])，铅(IDen，[DenHead | DenTail])，Q 是 NumHead/DenHead，追加([DenHead]，DenTail，DenNorm)，追加([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＞是，！，X1 是 X - Y，gcd(-X, Y, Z).gcd(X, Y, Z) :-Y＜0, Y >= X, !,Y1 是 Y - X，gcd(X, -Y, Z).gcd(X, 0, X).gcd(0, Y, Y).gcd(X, Y, Z) :-X＞Y，Y＞0,X1 是 X - Y，gcd(Y, X1, Z).gcd(X, Y, Z) :-X＝＜Y，X＞0,Y1 是 Y - X，gcd(X, Y1, Z).gcd(X, Y, Z) :-X＞Y，Y＜0,X1 是 X + Y，gcd(Y, X1, Z).gcd(X, Y, Z) :-X＝＜Y，X＜0,Y1 是 Y + X，gcd(X, Y1, Z).

解决方案

这个答案意味着朝着正确的方向前进.

首先，暂时忘记你需要解析像x^2 + 7x + 6这样的表达式；这在 Prolog 中甚至还不是一个合适的术语.如果你试图在顶层写它，你会得到一个错误:

?- Expr = x^2 + 7x + 6.错误:语法错误:需要操作员错误:Expr = x^2 +错误:**这里**错误: 7x + 6 .

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

[6, 7, 1]

类似地，x^2 − 5x − 6 变为:

[-6, -5, 1]

并且要表示 0，您将使用空列表:

<代码>[]

现在，看看维基百科页面上的算法.它使用 deg 作为度数，使用 lc 作为领先系数.使用上面的列表表示，您可以将它们定义为:

<块引用>

度数比保存系数的列表的长度少一.

poly_deg(F, D) :-长度(F，N)，D 是 N - 1.

<块引用>

前导系数是列表的最后一个元素.

poly_lc(F, C) :-最后(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 文章中所述.如果您遇到更多麻烦，您应该编辑您的问题或提出新问题.

The title kind of says it all. I'm looking to compute the GCD of two polynomials. Is there any way this can be done in Prolog? If so, what's a good starting point? Specifically, I'm having trouble with how to implement polynomial division using Prolog.

Edit to include example input and output:

Example input:

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

Example output:

X = x + 1.

Solution

On the off chance that someone else needs to do this, here's my final 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).

解决方案

This answer is meant as a push in the right direction.

First, forget for a moment that you need to parse an expression like x^2 + 7x + 6; this isn't even a proper term in Prolog yet. If you tried to write it on the top level, you will get an error:

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

Prolog doesn't know how to deal with the 7x you have there. Parsing the expression is a question of its own, and maybe it is easier if you assumed you have already parsed it and gotten a representation that looks for example like this:

[6, 7, 1]

Similarly, x^2 − 5x − 6 becomes:

[-6, -5, 1]

and to represent 0 you would use the empty list:

[]

Now, take a look at the algorithm at the Wikipedia page. It uses deg for the degree and lc for the leading coefficient. With the list representation above, you can define those as:

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).

You also need to be able to do simple arithmetic with polynomials. Using the definitions on the 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 Stackoverflow. Using the predicates defined there:

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

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

From here on, it should be possible for you to try and implement polynomial division as outlined in the Wiki article I linked above. If you get into more trouble, you should edit your question or ask a new one.

这篇关于使用 Prolog 计算多项式的 GCD的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！