I need a progam in Prolog to find the GCD of polynomialsSolu

I need a progam in Prolog to find the GCD of polynomials??

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