Der Titel sagt schon alles. Ich suche die GCD von zwei Polynomen zu berechnen. Gibt es eine Möglichkeit, dies in Prolog zu tun? Wenn ja, was ist ein guter Ausgangspunkt? Insbesondere habe ich Probleme mit der Implementierung der Polynomdivision mit Prolog.

Bearbeiten, um Beispieleingabe und -ausgabe einzuschließen:

Beispieleingabe:

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

Beispielausgabe:

X = x + 1.

Lösun

Nach dem Zufall, dass jemand anderes dies tun muss, ist hier meine endgültige Lösung:

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