Prologを使用して多項式のGCDを計算する

Question

タイトルの種類はすべてです。私は2つの多項式のGCDを計算しようとしています。これはPrologでこれを行う方法はありますか？もしそうなら、良い出発点は何ですか？具体的には、Prologを使用して多項式除算を実装する方法に問題があります。

編集は、例えば、入力と出力を含めます

例入力：

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

出力例：オフのチャンスで

X = x + 1. 

ソリューション

その誰かこれを行う必要があります、私のfiはここにありますソリューション：

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] 

、今

[] 

algorithm at the Wikipedia pageを見てみましょう：

と表現する0あなたは空のリストを使用します。度は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の定義を使用して、たとえば[]と[1]を追加すると、[1]が得られるはずです。[-2, 2]と[1, -3, 1]を掛け合わせると、[-2, 8, -8, 2]となります。 precursory searchは私にthis question here on Stackoverflowを与えました。そこに定義された述語を使用して：あなたは試してみて、私は上記のリンク先のWikiの記事で概説したよう多項式除算を実装するため

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

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

ここから上、それは可能なはずです。さらに困ったことがある場合は、質問を編集するか、新しい質問をする必要があります。