| 962 | |
| 963 | #ifndef HAVE_NTL |
| 964 | void tryExtgcd( const CanonicalForm & F, const CanonicalForm & G, const CanonicalForm & M, CanonicalForm & result, CanonicalForm & s, CanonicalForm & t, bool & fail ) |
| 965 | { // F, G are univariate polynomials (i.e. they have exactly one polynomial variable) |
| 966 | // F and G must have the same level AND level > 0 |
| 967 | // we try to calculate gcd(F,G) = s*F + t*G |
| 968 | // if a zero divisor is encountered, 'fail' is set to one |
| 969 | // M is assumed to be monic |
| 970 | CanonicalForm P; |
| 971 | if(F.inCoeffDomain()) |
| 972 | { |
| 973 | tryInvert( F, M, P, fail ); |
| 974 | if(fail) |
| 975 | return; |
| 976 | result = 1; |
| 977 | s = P; t = 0; |
| 978 | return; |
| 979 | } |
| 980 | if(G.inCoeffDomain()) |
| 981 | { |
| 982 | tryInvert( G, M, P, fail ); |
| 983 | if(fail) |
| 984 | return; |
| 985 | result = 1; |
| 986 | s = 0; t = P; |
| 987 | return; |
| 988 | } |
| 989 | // here: both not inCoeffDomain |
| 990 | CanonicalForm inv, rem, tmp, u, v, q, sum=0; |
| 991 | if( F.degree() > G.degree() ) |
| 992 | { |
| 993 | P = F; result = G; s=v=0; t=u=1; |
| 994 | } |
| 995 | else |
| 996 | { |
| 997 | P = G; result = F; s=v=1; t=u=0; |
| 998 | } |
| 999 | Variable x = P.mvar(); |
| 1000 | // here: degree(P) >= degree(result) |
| 1001 | while(true) |
| 1002 | { |
| 1003 | tryDivrem (P, result, q, rem, inv, M, fail); |
| 1004 | if(fail) |
| 1005 | return; |
| 1006 | if( rem.isZero() ) |
| 1007 | { |
| 1008 | s*=inv; |
| 1009 | s= reduce (s, M); |
| 1010 | t*=inv; |
| 1011 | t= reduce (t, M); |
| 1012 | result *= inv; // monify result |
| 1013 | result= reduce (result, M); |
| 1014 | return; |
| 1015 | } |
| 1016 | sum += q; |
| 1017 | if(result.degree(x) >= rem.degree(x)) |
| 1018 | { |
| 1019 | P=result; |
| 1020 | result=rem; |
| 1021 | tmp=u-sum*s; |
no test coverage detected