Changeset 7d1c995 in git for factory/algext.cc
 Timestamp:
 May 31, 2011, 3:48:35 PM (12 years ago)
 Branches:
 (u'spielwiese', '8e0ad00ce244dfd0756200662572aef8402f13d5')
 Children:
 a8e8b95ce901a8a52041639c48329ebc09efae2b
 Parents:
 5b274570b3977c8b95131bdda194e0b179f17b8b
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

factory/algext.cc
r5b2745 r7d1c995 145 145 return false; 146 146 } 147 148 CanonicalForm univarQGCD( const CanonicalForm & F, const CanonicalForm & G )149 { // F,G in Q(a)[x]150 CanonicalForm f, g, tmp, M, q, D, Dp, cl, newD, newq;151 int p, dp_deg, bound, i;152 bool fail;153 On(SW_RATIONAL);154 f = F * bCommonDen(F);155 g = G * bCommonDen(G);156 Variable a,b;157 if( !hasFirstAlgVar( f, a ) && !hasFirstAlgVar( g, b ))158 {159 // F and G are in Q[x], call...160 #ifdef HAVE_NTL161 if ( isOn( SW_USE_NTL_GCD_0 ))162 return gcd_univar_ntl0( f, g );163 #endif164 return gcd_poly_univar0( f, g, false );165 }166 if( b.level() > a.level() )167 a = b;168 // here: a is the biggest alg. var in f and g169 tmp = getMipo(a);170 M = tmp * bCommonDen(tmp);171 Off(SW_RATIONAL);172 // calculate upper bound for degree of gcd173 bound = degree(f);174 i = degree(g);175 if( i < bound )176 bound = i;177 178 cl = lc(M) * lc(f) * lc(g);179 q = 1;180 D = 0;181 for(i=cf_getNumBigPrimes()1; i>1; i)182 {183 p = cf_getBigPrime(i);184 if( mod( cl, p ).isZero() ) // skip lcbad primes185 continue;186 187 fail = false;188 setCharacteristic(p);189 tryEuclid( mapinto(f), mapinto(g), mapinto(M), Dp, fail );190 setCharacteristic(0);191 if( fail ) // M splits in char p192 continue;193 194 dp_deg = degree(Dp);195 196 if( dp_deg == 0 ) // early termination197 {198 CanonicalForm inv;199 tryInvert(Dp, M, inv, fail);200 if(fail)201 continue;202 return CanonicalForm(1);203 }204 205 if( dp_deg > bound ) // current prime unlucky206 continue;207 208 if( dp_deg < bound ) // all previous primes unlucky209 {210 q = p;211 D = mapinto(Dp); // shortcut CRA212 bound = dp_deg; // tighten bound213 continue;214 }215 chineseRemainder( D, q, mapinto(Dp), p, newD, newq );216 // newD = Dp mod p217 // newD = D mod q218 // newq = p*q219 q = newq;220 if( D != newD )221 {222 D = newD;223 continue;224 }225 On( SW_RATIONAL );226 tmp = Farey( D, q );227 if( fdivides( tmp, f ) && fdivides( tmp, g )) // trial division228 {229 Off( SW_RATIONAL );230 return tmp;231 }232 Off( SW_RATIONAL );233 }234 // hopefully, we never reach this point235 Off( SW_USE_QGCD );236 D = gcd( f, g );237 On( SW_USE_QGCD );238 return D;239 }240 241 242 147 243 148 CanonicalForm QGCD( const CanonicalForm & F, const CanonicalForm & G );
Note: See TracChangeset
for help on using the changeset viewer.