Changeset ce2576 in git for libpolys/polys/clapsing.cc
- Timestamp:
- Nov 10, 2011, 5:59:46 PM (12 years ago)
- Branches:
- (u'spielwiese', '8e0ad00ce244dfd0756200662572aef8402f13d5')
- Children:
- 3826d071b0fe1a52a0fa5cdc532b9c99960c5018
- Parents:
- 6051d879db769fabc5f68f3052af02b306ccf1a6
- git-author:
- Martin Lee <martinlee84@web.de>2011-11-10 17:59:46+01:00
- git-committer:
- Oleksandr Motsak <motsak@mathematik.uni-kl.de>2011-11-10 18:27:53+01:00
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
libpolys/polys/clapsing.cc
r6051d87 rce2576 31 31 #include "ext_fields/transext.h" 32 32 33 // TODO(Martin, Please adapt the following code for the use in SW)34 35 33 36 34 #include "clapsing.h" … … 58 56 59 57 Off(SW_RATIONAL); 60 CanonicalForm F( convSingPFactoryP( f,r ) ), G( convSingPFactoryP( g, r ) ); 61 bool b1=isOn(SW_USE_QGCD); 62 bool b2=isOn(SW_USE_fieldGCD); 63 if ( rField_is_Q_a(r) ) On(SW_USE_QGCD); 64 else On(SW_USE_fieldGCD); 65 res=convFactoryPSingP( gcd( F, G ) , r); 66 if (!b1) Off(SW_USE_QGCD); 67 if (!b2) Off(SW_USE_fieldGCD); 58 if (rField_is_Q(r) || (rField_is_Zp(r))) 59 { 60 bool b1=isOn(SW_USE_EZGCD_P); 61 Off (SW_USE_NTL_GCD_P); 62 setCharacteristic( rChar(r) ); 63 CanonicalForm F( convSingPFactoryP( f,r ) ), G( convSingPFactoryP( g, r ) ); 64 res=convFactoryPSingP( gcd( F, G ) , r); 65 if (!b1) Off (SW_USE_EZGCD_P); 66 } 67 // and over Q(a) / Fp(a) 68 else if ( rField_is_Extension(r)) 69 { 70 if ( rField_is_Q_a(r)) setCharacteristic( 0 ); 71 else setCharacteristic( rChar(r) ); 72 if (r->cf->extRing->minideal!=NULL) 73 { 74 bool b1=isOn(SW_USE_QGCD); 75 bool b2=isOn(SW_USE_fieldGCD); 76 if ( rField_is_Q_a(r) ) On(SW_USE_QGCD); 77 else On(SW_USE_fieldGCD); 78 CanonicalForm mipo=convSingPFactoryP(r->cf->extRing->minideal->m[0], 79 r->cf->extRing); 80 Variable a=rootOf(mipo); 81 CanonicalForm F( convSingAPFactoryAP( f,a,r ) ), 82 G( convSingAPFactoryAP( g,a,r ) ); 83 res= convFactoryAPSingAP( gcd( F, G ),r ); 84 if (!b1) Off(SW_USE_QGCD); 85 if (!b2) Off(SW_USE_fieldGCD); 86 } 87 else 88 { 89 CanonicalForm F( convSingTrPFactoryP( f,r ) ), G( convSingTrPFactoryP( g,r ) ); 90 res= convFactoryPSingTrP( gcd( F, G ),r ); 91 } 92 } 93 else 94 WerrorS( feNotImplemented ); 68 95 Off(SW_RATIONAL); 69 96 return res; … … 111 138 if ((f==NULL) || (g==NULL)) 112 139 goto resultant_returns_res; 113 { 114 Variable X(i); // TODO: consider extensions 115 CanonicalForm F( convSingPFactoryP( f, r ) ), G( convSingPFactoryP( g, r ) ); 116 res=convFactoryPSingP( resultant( F, G, X ), r ); 140 // for now there is only the possibility to handle polynomials over 141 // Q and Fp ... 142 if (rField_is_Zp(r) || rField_is_Q(r)) 143 { 144 Variable X(i); 145 setCharacteristic( rChar(r) ); 146 CanonicalForm F( convSingPFactoryP( f,r ) ), G( convSingPFactoryP( g,r ) ); 147 res=convFactoryPSingP( resultant( F, G, X),r ); 117 148 Off(SW_RATIONAL); 118 } 149 goto resultant_returns_res; 150 } 151 // and over Q(a) / Fp(a) 152 else if (rField_is_Extension(r)) 153 { 154 if (rField_is_Q_a(r)) setCharacteristic( 0 ); 155 else setCharacteristic( rChar(r) ); 156 Variable X(i+rPar(r)); 157 if (r->cf->extRing->minideal!=NULL) 158 { 159 //Variable X(i); 160 CanonicalForm mipo=convSingPFactoryP(r->cf->extRing->minideal->m[0], 161 r->cf->extRing); 162 Variable a=rootOf(mipo); 163 CanonicalForm F( convSingAPFactoryAP( f,a,r ) ), 164 G( convSingAPFactoryAP( g,a,r ) ); 165 res= convFactoryAPSingAP( resultant( F, G, X ),r ); 166 } 167 else 168 { 169 //Variable X(i+rPar(currRing)); 170 number nf,ng; 171 p_Cleardenom_n(f,r,nf);p_Cleardenom_n(g,r,ng); 172 int ef,eg; 173 ef=pGetExp_Var(f,i,r); 174 eg=pGetExp_Var(g,i,r); 175 CanonicalForm F( convSingTrPFactoryP( f,r ) ), G( convSingTrPFactoryP( g,r ) ); 176 res= convFactoryPSingTrP( resultant( F, G, X ),r ); 177 if ((nf!=NULL)&&(!n_IsOne(nf,r->cf))&&(!n_IsZero(nf,r->cf))) 178 { 179 number n=n_Invers(nf,r->cf); 180 while(eg>0) 181 { 182 res=p_Mult_nn(res,n,r); 183 eg--; 184 } 185 n_Delete(&n,r->cf); 186 } 187 n_Delete(&nf,r->cf); 188 if ((ng!=NULL)&&(!n_IsOne(ng,r->cf))&&(!n_IsZero(ng,r->cf))) 189 { 190 number n=n_Invers(ng,r->cf); 191 while(ef>0) 192 { 193 res=p_Mult_nn(res,n,r); 194 ef--; 195 } 196 n_Delete(&n,r->cf); 197 } 198 n_Delete(&ng,r->cf); 199 } 200 Off(SW_RATIONAL); 201 goto resultant_returns_res; 202 } 203 else 204 WerrorS( feNotImplemented ); 119 205 resultant_returns_res: 120 206 p_Delete(&f,r); … … 190 276 res=NULL;pa=NULL;pb=NULL; 191 277 On(SW_SYMMETRIC_FF); 192 CanonicalForm F( convSingPFactoryP( f, r ) ), G( convSingPFactoryP( g, r ) ); 193 CanonicalForm FpG=F+G; 194 if (!(FpG.isUnivariate()|| FpG.inCoeffDomain())) 195 //if (!F.isUnivariate() || !G.isUnivariate() || F.mvar()!=G.mvar()) 196 { 278 if ( rField_is_Q(r) || rField_is_Zp(r) ) 279 { 280 setCharacteristic( rChar(r) ); 281 CanonicalForm F( convSingPFactoryP( f,r ) ), G( convSingPFactoryP( g,r) ); 282 CanonicalForm FpG=F+G; 283 if (!(FpG.isUnivariate()|| FpG.inCoeffDomain())) 284 //if (!F.isUnivariate() || !G.isUnivariate() || F.mvar()!=G.mvar()) 285 { 286 Off(SW_RATIONAL); 287 WerrorS("not univariate"); 288 return TRUE; 289 } 290 CanonicalForm Fa,Gb; 291 On(SW_RATIONAL); 292 res=convFactoryPSingP( extgcd( F, G, Fa, Gb ),r ); 293 pa=convFactoryPSingP(Fa,r); 294 pb=convFactoryPSingP(Gb,r); 197 295 Off(SW_RATIONAL); 198 WerrorS("not univariate"); 296 } 297 // and over Q(a) / Fp(a) 298 else if ( rField_is_Extension(r)) 299 { 300 if (rField_is_Q_a(r)) setCharacteristic( 0 ); 301 else setCharacteristic( rChar(r) ); 302 CanonicalForm Fa,Gb; 303 if (r->cf->extRing->minideal!=NULL) 304 { 305 CanonicalForm mipo=convSingPFactoryP(r->cf->extRing->minideal->m[0], 306 r->cf->extRing); 307 Variable a=rootOf(mipo); 308 CanonicalForm F( convSingAPFactoryAP( f,a,r ) ), 309 G( convSingAPFactoryAP( g,a,r ) ); 310 CanonicalForm FpG=F+G; 311 if (!(FpG.isUnivariate()|| FpG.inCoeffDomain())) 312 //if (!F.isUnivariate() || !G.isUnivariate() || F.mvar()!=G.mvar()) 313 { 314 WerrorS("not univariate"); 315 return TRUE; 316 } 317 res= convFactoryAPSingAP( extgcd( F, G, Fa, Gb ),r ); 318 pa=convFactoryAPSingAP(Fa,r); 319 pb=convFactoryAPSingAP(Gb,r); 320 } 321 else 322 { 323 CanonicalForm F( convSingTrPFactoryP( f, r ) ), G( convSingTrPFactoryP( g, r ) ); 324 CanonicalForm FpG=F+G; 325 if (!(FpG.isUnivariate()|| FpG.inCoeffDomain())) 326 //if (!F.isUnivariate() || !G.isUnivariate() || F.mvar()!=G.mvar()) 327 { 328 Off(SW_RATIONAL); 329 WerrorS("not univariate"); 330 return TRUE; 331 } 332 res= convFactoryPSingTrP( extgcd( F, G, Fa, Gb ), r ); 333 pa=convFactoryPSingTrP(Fa, r); 334 pb=convFactoryPSingTrP(Gb, r); 335 } 336 Off(SW_RATIONAL); 337 } 338 else 339 { 340 WerrorS( feNotImplemented ); 199 341 return TRUE; 200 342 } 201 CanonicalForm Fa,Gb;202 On(SW_RATIONAL);203 res=convFactoryPSingP( extgcd( F, G, Fa, Gb ), r );204 pa=convFactoryPSingP(Fa, r);205 pb=convFactoryPSingP(Gb, r);206 Off(SW_RATIONAL);207 343 #ifndef NDEBUG 208 344 // checking the result of extgcd: … … 212 348 { 213 349 PrintS("extgcd( ");p_Write(f,r);p_Write0(g,r);PrintS(" )\n"); 214 PrintS(" gcd, co-factors:");p_Write(res,r); p_Write(pa,r);p_Write(pb,r);350 PrintS("extgcd( ");p_Write(f,r);p_Write0(g,r);PrintS(" )\n"); 215 351 p_Delete(&dummy,r); 216 352 } … … 223 359 poly res=NULL; 224 360 On(SW_RATIONAL); 225 CanonicalForm F( convSingPFactoryP( f,r ) ), G( convSingPFactoryP( g,r ) ); 226 res = convFactoryPSingP( F / G,r ); 361 if (rField_is_Zp(r) || rField_is_Q(r)) 362 { 363 setCharacteristic( rChar(r) ); 364 CanonicalForm F( convSingPFactoryP( f,r ) ), G( convSingPFactoryP( g,r ) ); 365 res = convFactoryPSingP( F / G,r ); 366 } 367 else if (rField_is_Extension(r)) 368 { 369 if (rField_is_Q_a(r)) setCharacteristic( 0 ); 370 else setCharacteristic( rChar(r) ); 371 if (r->cf->extRing->minideal!=NULL) 372 { 373 CanonicalForm mipo=convSingPFactoryP(r->cf->extRing->minideal->m[0], 374 r->cf->extRing); 375 Variable a=rootOf(mipo); 376 CanonicalForm F( convSingAPFactoryAP( f,a,r ) ), 377 G( convSingAPFactoryAP( g,a,r ) ); 378 res= convFactoryAPSingAP( F / G, r ); 379 } 380 else 381 { 382 CanonicalForm F( convSingTrPFactoryP( f,r ) ), G( convSingTrPFactoryP( g,r ) ); 383 res= convFactoryPSingTrP( F / G,r ); 384 } 385 } 386 #if 0 // not yet working 387 else if (rField_is_GF()) 388 { 389 //Print("GF(%d^%d)\n",nfCharP,nfMinPoly[0]); 390 setCharacteristic( nfCharP,nfMinPoly[0], currRing->parameter[0][0] ); 391 CanonicalForm F( convSingGFFactoryGF( f ) ), G( convSingGFFactoryGF( g ) ); 392 res = convFactoryGFSingGF( F / G ); 393 } 394 #endif 395 else 396 WerrorS( feNotImplemented ); 227 397 Off(SW_RATIONAL); 228 398 return res; … … 342 512 { 343 513 #ifdef FACTORIZE2_DEBUG 344 printf("start count_Factors(%d), Fdeg=%d, factor deg=%d\n",j,p Totaldegree(f),pTotaldegree(fac));514 printf("start count_Factors(%d), Fdeg=%d, factor deg=%d\n",j,p_Totaldegree(f,r),p_Totaldegree(fac,r)); 345 515 p_wrp(fac,r);PrintLn(); 346 516 #endif … … 348 518 CanonicalForm F, FAC,Q,R; 349 519 Variable a; 350 F=convSingPFactoryP( f,r ); 351 FAC=convSingPFactoryP( fac,r ); 520 if (rField_is_Zp(r) || rField_is_Q(r)) 521 { 522 F=convSingPFactoryP( f,r ); 523 FAC=convSingPFactoryP( fac,r ); 524 } 525 else if (rField_is_Extension(r)) 526 { 527 if (r->cf->extRing->minideal!=NULL) 528 { 529 CanonicalForm mipo=convSingPFactoryP(r->cf->extRing->minideal->m[0], 530 r->cf->extRing); 531 a=rootOf(mipo); 532 F=convSingAPFactoryAP( f,a,r ); 533 FAC=convSingAPFactoryAP( fac,a,r ); 534 } 535 else 536 { 537 F=convSingTrPFactoryP( f,r ); 538 FAC=convSingTrPFactoryP( fac,r ); 539 } 540 } 541 else 542 WerrorS( feNotImplemented ); 352 543 353 544 poly q; … … 361 552 if (R.isZero()) 362 553 { 363 q = convFactoryPSingP( Q,r ); 554 if (rField_is_Zp(r) || rField_is_Q(r)) 555 { 556 q = convFactoryPSingP( Q,r ); 557 } 558 else if (rField_is_Extension(r)) 559 { 560 if (r->cf->extRing->minideal!=NULL) 561 { 562 q= convFactoryAPSingAP( Q,r ); 563 } 564 else 565 { 566 q= convFactoryPSingTrP( Q,r ); 567 } 568 } 364 569 e++; p_Delete(&f,r); f=q; q=NULL; F=Q; 365 570 } … … 394 599 p_Test(f,r); 395 600 #ifdef FACTORIZE2_DEBUG 396 printf("singclap_factorize, degree %ld\n",p Totaldegree(f));601 printf("singclap_factorize, degree %ld\n",p_Totaldegree(f,r)); 397 602 #endif 398 603 // with_exps: 3,1 return only true factors, no exponents … … 461 666 return res; 462 667 } 463 //PrintS("S:");p Write(f);PrintLn();668 //PrintS("S:");p_Write(f,r);PrintLn(); 464 669 // use factory/libfac in general ============================== 465 670 Off(SW_RATIONAL); … … 482 687 N=n_Copy(n0,r->cf); 483 688 p_Cleardenom(f, r); 689 //after here f should not have a denominator!! 690 //PrintS("S:");p_Write(f,r);PrintLn(); 484 691 NN=n_Div(n0,pGetCoeff(f),r->cf); 485 692 n_Delete(&n0,r->cf); … … 519 726 else if (rField_is_Extension(r)) 520 727 { 728 if (rField_is_Q_a (r)) setCharacteristic (0); 729 else setCharacteristic( rChar(r) ); 521 730 if (r->cf->extRing->minideal!=NULL) 522 731 { … … 524 733 r->cf->extRing); 525 734 Variable a=rootOf(mipo); 526 CanonicalForm F( convSing PFactoryP( f,r ) );735 CanonicalForm F( convSingAPFactoryAP( f, a, r ) ); 527 736 if (rField_is_Zp_a(r)) 528 737 { … … 537 746 else 538 747 { 539 CanonicalForm F( convSing PFactoryP( f,r ) );748 CanonicalForm F( convSingTrPFactoryP( f,r ) ); 540 749 L = factorize( F ); 541 750 } … … 583 792 if (r->cf->extRing->minideal==NULL) 584 793 { 585 if(!count_Factors(res,w,j,ff,convFactoryPSing P( J.getItem().factor(),r ),r))794 if(!count_Factors(res,w,j,ff,convFactoryPSingTrP( J.getItem().factor(),r ),r)) 586 795 { 587 796 if (w!=NULL) … … 592 801 else 593 802 { 594 if (!count_Factors(res,w,j,ff,convFactory PSingP( J.getItem().factor(),r ),r))803 if (!count_Factors(res,w,j,ff,convFactoryAPSingAP( J.getItem().factor(),r ),r)) 595 804 { 596 805 if (w!=NULL) … … 1229 1438 #endif 1230 1439 1231 /*1232 napoly singclap_alglcm ( napoly f, napoly g )1233 {1234 1235 // over Q(a) / Fp(a)1236 if (nGetChar()==1) setCharacteristic( 0 );1237 else setCharacteristic( -nGetChar() );1238 napoly res;1239 1240 if (currRing->minpoly!=NULL)1241 {1242 CanonicalForm mipo=convSingPFactoryP(((lnumber)currRing->minpoly)->z,1243 currRing->extRing);1244 Variable a=rootOf(mipo);1245 CanonicalForm F( convSingAFactoryA( f,a, currRing ) ),1246 G( convSingAFactoryA( g,a, currRing ) );1247 CanonicalForm GCD;1248 1249 // calculate gcd1250 GCD = gcd( F, G );1251 1252 // calculate lcm1253 res= convFactoryASingA( (F/GCD)*G,currRing );1254 }1255 else1256 {1257 CanonicalForm F( convSingPFactoryP( f,currRing->extRing ) ),1258 G( convSingPFactoryP( g,currRing->extRing ) );1259 CanonicalForm GCD;1260 // calculate gcd1261 GCD = gcd( F, G );1262 1263 // calculate lcm1264 res= convFactoryPSingP( (F/GCD)*G, currRing->extRing );1265 }1266 1267 Off(SW_RATIONAL);1268 return res;1269 }1270 1271 void singclap_algdividecontent ( napoly f, napoly g, napoly &ff, napoly &gg )1272 {1273 // over Q(a) / Fp(a)1274 if (nGetChar()==1) setCharacteristic( 0 );1275 else setCharacteristic( -nGetChar() );1276 ff=gg=NULL;1277 On(SW_RATIONAL);1278 1279 if (currRing->minpoly!=NULL)1280 {1281 CanonicalForm mipo=convSingPFactoryP(((lnumber)currRing->minpoly)->z,1282 currRing->extRing);1283 Variable a=rootOf(mipo);1284 CanonicalForm F( convSingAFactoryA( f,a, currRing ) ),1285 G( convSingAFactoryA( g,a, currRing ) );1286 CanonicalForm GCD;1287 1288 GCD=gcd( F, G );1289 1290 if ((GCD!=1) && (GCD!=0))1291 {1292 ff= convFactoryASingA( F/ GCD, currRing );1293 gg= convFactoryASingA( G/ GCD, currRing );1294 }1295 }1296 else1297 {1298 CanonicalForm F( convSingPFactoryP( f,currRing->extRing ) ),1299 G( convSingPFactoryP( g,currRing->extRing ) );1300 CanonicalForm GCD;1301 1302 GCD=gcd( F, G );1303 1304 if ((GCD!=1) && (GCD!=0))1305 {1306 ff= convFactoryPSingP( F/ GCD, currRing->extRing );1307 gg= convFactoryPSingP( G/ GCD, currRing->extRing );1308 }1309 }1310 1311 Off(SW_RATIONAL);1312 }1313 */1314 1315 #if 01316 lists singclap_chineseRemainder(lists x, lists q)1317 {1318 //assume(x->nr == q->nr);1319 //assume(x->nr >= 0);1320 int n=x->nr+1;1321 if ((x->nr<0) || (x->nr!=q->nr))1322 {1323 WerrorS("list are empty or not of equal length");1324 return NULL;1325 }1326 lists res=(lists)omAlloc0Bin(slists_bin);1327 CFArray X(1,n), Q(1,n);1328 int i;1329 for(i=0; i<n; i++)1330 {1331 if (x->m[i-1].Typ()==INT_CMD)1332 {1333 X[i]=(int)x->m[i-1].Data();1334 }1335 else if (x->m[i-1].Typ()==NUMBER_CMD)1336 {1337 number N=(number)x->m[i-1].Data();1338 X[i]=convSingNFactoryN(N);1339 }1340 else1341 {1342 WerrorS("illegal type in chineseRemainder");1343 omFreeBin(res,slists_bin);1344 return NULL;1345 }1346 if (q->m[i-1].Typ()==INT_CMD)1347 {1348 Q[i]=(int)q->m[i-1].Data();1349 }1350 else if (q->m[i-1].Typ()==NUMBER_CMD)1351 {1352 number N=(number)x->m[i-1].Data();1353 Q[i]=convSingNFactoryN(N);1354 }1355 else1356 {1357 WerrorS("illegal type in chineseRemainder");1358 omFreeBin(res,slists_bin);1359 return NULL;1360 }1361 }1362 CanonicalForm r, prod;1363 chineseRemainder( X, Q, r, prod );1364 res->Init(2);1365 res->m[0].rtyp=NUMBER_CMD;1366 res->m[1].rtyp=NUMBER_CMD;1367 res->m[0].data=(char *)convFactoryNSingN( r );1368 res->m[1].data=(char *)convFactoryNSingN( prod );1369 return res;1370 }1371 #endif1372 1373 number nChineseRemainder(number *x, number *q,int rl, const coeffs r)1374 // elemenst in the array are x[0..(rl-1)], q[0..(rl-1)]1375 {1376 #ifdef HAVE_FACTORY1377 if (r->type!=n_Q)1378 { Werror("nChineseRemainder only for integers"); return NULL; }1379 setCharacteristic( 0 ); // only in char 01380 CFArray X(rl), Q(rl);1381 int i;1382 for(i=rl-1;i>=0;i--)1383 {1384 X[i]=r->convSingNFactoryN(x[i],FALSE,r); // may be larger MAX_INT1385 Q[i]=r->convSingNFactoryN(q[i],FALSE,r); // may be larger MAX_INT1386 }1387 CanonicalForm xnew,qnew;1388 chineseRemainder(X,Q,xnew,qnew);1389 number n=r->convFactoryNSingN(xnew,r);1390 number p=r->convFactoryNSingN(qnew,r);1391 number p2=n_IntDiv(p,n_Init(2, r),r);1392 if (n_Greater(n,p2,r))1393 {1394 number n2=n_Sub(n,p,r);1395 n_Delete(&n,r);1396 n=n2;1397 }1398 n_Delete(&p,r);1399 n_Delete(&p2,r);1400 return n;1401 #else1402 WerrorS("not implemented");1403 return n_Init(0,r);1404 #endif1405 }
Note: See TracChangeset
for help on using the changeset viewer.