Changeset ec970e in git
 Timestamp:
 Jul 6, 2011, 2:41:32 PM (12 years ago)
 Branches:
 (u'jengelhdatetime', 'ceac47cbc86fe4a15902392bdbb9bd2ae0ea02c6')(u'spielwiese', 'f875bbaccd0831e36aaed09ff6adeb3eb45aeb94')
 Children:
 42281d63800a31c74efe7fb9afecba0a2d1cbe9d
 Parents:
 e28e6d1742e673c091f48a99b5d6d522e5d5bfa2
 Location:
 factory
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

factory/int_poly.cc
re28e6d rec970e 256 256 257 257 InternalCF* 258 InternalPoly::tryInvert ( const CanonicalForm& M, bool& fail) 259 { 260 if ( inExtension() && !getReduce ( var ) ) 261 { 262 CanonicalForm b, inverse; 263 CanonicalForm F ( this >copyObject() ); 264 Variable a = M.mvar(); 265 Variable x = Variable(1); 266 F= mod (F, M); //reduce mod M 267 CanonicalForm g= extgcd (replacevar( F, a, x ), replacevar( M, a, x ), inverse, b ); 268 if(!g.isOne()) 269 fail = true; 270 else 271 inverse = replacevar( inverse, x, a ); // change back to alg var 272 CanonicalForm test= mod (inverse*F, M); 273 return inverse.getval(); 274 } 275 else 276 return CFFactory::basic( 0 ); 277 } 278 279 InternalCF* 258 280 InternalPoly::addsame( InternalCF* aCoeff ) 259 281 { … … 398 420 399 421 InternalCF* 422 InternalPoly::tryMulsame( InternalCF* aCoeff, const CanonicalForm& M) 423 { 424 if (is_imm(aCoeff)) 425 return mulcoeff(aCoeff); 426 InternalPoly *aPoly = (InternalPoly*)aCoeff; 427 termList resultFirst = 0, resultLast = 0; 428 termList theCursor = firstTerm; 429 430 while ( theCursor ) 431 { 432 resultFirst = mulAddTermList( resultFirst, aPoly>firstTerm, 433 theCursor>coeff, theCursor>exp, resultLast, false ); 434 theCursor = theCursor>next; 435 } 436 if ( inExtension() && !getReduce( var ) ) 437 { 438 resultFirst= reduceTermList (resultFirst, ((InternalPoly*) M.getval())>firstTerm, resultLast); 439 if ( resultFirst == 0 ) 440 { 441 if ( getRefCount() <= 1 ) 442 { 443 delete this; 444 return CFFactory::basic(0); 445 } 446 else 447 { 448 decRefCount(); 449 return CFFactory::basic(0); 450 } 451 } 452 else if ( resultFirst>exp == 0 ) 453 { 454 if ( getRefCount() <= 1 ) 455 { 456 InternalCF * res = resultFirst>coeff.getval(); 457 delete resultFirst; 458 delete this; 459 return res; 460 } 461 else 462 { 463 decRefCount(); 464 InternalCF * res = resultFirst>coeff.getval(); 465 delete resultFirst; 466 return res; 467 } 468 } 469 } 470 if ( getRefCount() <= 1 ) 471 { 472 freeTermList( firstTerm ); 473 firstTerm = resultFirst; 474 lastTerm = resultLast; 475 return this; 476 } 477 else 478 { 479 decRefCount(); 480 return new InternalPoly( resultFirst, resultLast, var ); 481 } 482 } 483 484 InternalCF* 400 485 InternalPoly::dividesame( InternalCF* aCoeff ) 401 486 { … … 448 533 delete dummy; 449 534 appendTermList( resultfirst, resultlast, newcoeff, newexp ); 535 } 536 freeTermList( first ); 537 if ( singleObject ) 538 { 539 if ( resultfirst && resultfirst>exp != 0 ) 540 { 541 firstTerm = resultfirst; 542 lastTerm = resultlast; 543 return this; 544 } 545 else if ( resultfirst ) 546 { 547 InternalCF * res = resultfirst>coeff.getval(); 548 delete resultfirst; 549 firstTerm = 0; 550 delete this; 551 return res; 552 } 553 else 554 { 555 // this should not happen (evtl use assertion) 556 ASSERT( 0, "FATAL ERROR, PLEASE INFORM THE AUTHOR" ); 557 firstTerm = 0; 558 delete this; 559 return CFFactory::basic( 0 ); 560 } 561 } 562 else 563 { 564 if ( resultfirst && resultfirst>exp != 0 ) 565 return new InternalPoly( resultfirst, resultlast, var ); 566 else if ( resultfirst ) 567 { 568 InternalCF * res = resultfirst>coeff.getval(); 569 delete resultfirst; 570 return res; 571 } 572 else 573 return CFFactory::basic( 0 ); 574 } 575 } 576 577 InternalCF* 578 InternalPoly::tryDivsame( InternalCF* aCoeff, const CanonicalForm& M, bool& fail ) 579 { 580 if ( inExtension() && !getReduce( var ) ) 581 { 582 InternalCF * dummy = aCoeff>tryInvert(M, fail); 583 if (fail) 584 return CFFactory::basic( 0 ); 585 if (is_imm(dummy)) dummy=this>tryMulsame(dummy, M); 586 else dummy = dummy>tryMulsame( this, M); 587 if (fail) 588 { 589 if (getRefCount() <= 1) 590 delete this; 591 else 592 decRefCount(); 593 return dummy; 594 } 595 if ( getRefCount() <= 1 ) 596 { 597 delete this; 598 return dummy; 599 } 600 else 601 { 602 decRefCount(); 603 return dummy; 604 } 605 } 606 InternalPoly *aPoly = (InternalPoly*)aCoeff; 607 termList dummy, first, last, resultfirst = 0, resultlast = 0; 608 CanonicalForm coeff, newcoeff; 609 int exp, newexp; 610 bool singleObject; 611 612 if ( getRefCount() <= 1 ) 613 { 614 first = firstTerm; last = lastTerm; singleObject = true; 615 } 616 else 617 { 618 first = copyTermList( firstTerm, last ); singleObject = false; 619 decRefCount(); 620 } 621 coeff = aPoly>firstTerm>coeff; 622 exp = aPoly>firstTerm>exp; 623 while (first && ( first>exp >= exp ) ) 624 { 625 newcoeff= first>coeff.tryDiv (coeff, M, fail); 626 if (fail) 627 { 628 freeTermList (first); 629 return CFFactory::basic (0); 630 } 631 newcoeff= reduce (newcoeff, M); 632 newexp = first>exp  exp; 633 dummy = first; 634 first = mulAddTermList( first>next, aPoly>firstTerm>next, newcoeff, newexp, last, true ); 635 delete dummy; 636 if (!newcoeff.isZero()) 637 appendTermList( resultfirst, resultlast, newcoeff, newexp ); 450 638 } 451 639 freeTermList( first ); … … 620 808 } 621 809 622 623 810 bool 624 811 InternalPoly::divremsamet( InternalCF* acoeff, InternalCF*& quot, InternalCF*& rem ) … … 676 863 else 677 864 rem = new InternalPoly( first, last, var ); 865 else 866 rem = CFFactory::basic( 0 ); 867 } 868 else 869 { 870 freeTermList( resultfirst ); 871 freeTermList( first ); 872 } 873 return divideok; 874 } 875 876 bool 877 InternalPoly::tryDivremsamet( InternalCF* acoeff, InternalCF*& quot, InternalCF*& rem, const CanonicalForm& M, bool& fail) 878 { 879 if (inExtension() && !getReduce (var)) 880 { 881 InternalCF * dummy = acoeff>tryInvert(M, fail); 882 if (fail) 883 return false; 884 quot = dummy>tryMulsame( this, M); 885 rem = CFFactory::basic( 0 ); 886 if (fail) 887 return false; 888 return true; 889 } 890 InternalPoly *aPoly = (InternalPoly*)acoeff; 891 termList dummy, first, last, resultfirst = 0, resultlast = 0; 892 CanonicalForm coeff, newcoeff, dummycoeff; 893 int exp, newexp; 894 bool divideok = true; 895 896 first = copyTermList( firstTerm, last ); 897 898 coeff = aPoly>firstTerm>coeff; 899 exp = aPoly>firstTerm>exp; 900 while (first && ( first>exp >= exp ) && divideok ) 901 { 902 divideok = tryDivremt( first>coeff, coeff, newcoeff, dummycoeff, M, fail ); 903 if (fail) 904 { 905 freeTermList (first); 906 return false; 907 } 908 if ( divideok && dummycoeff.isZero() ) 909 { 910 newexp = first>exp  exp; 911 dummy = first; 912 first = mulAddTermList( first>next, aPoly>firstTerm>next, newcoeff, newexp, last, true ); 913 delete dummy; 914 if (!newcoeff.isZero()) 915 appendTermList( resultfirst, resultlast, newcoeff, newexp ); 916 } 917 else 918 divideok = false; 919 } 920 if ( divideok ) 921 { 922 if ( resultfirst ) 923 if ( resultfirst>exp == 0 ) 924 { 925 quot = resultfirst>coeff.getval(); 926 delete resultfirst; 927 } 928 else 929 quot = new InternalPoly( resultfirst, resultlast, var ); 930 else 931 quot = CFFactory::basic( 0 ); 932 if ( first ) 933 if ( first>exp == 0 ) 934 { 935 rem = first>coeff.getval(); 936 delete first; 937 } 938 else 939 { 940 if (first>coeff.isZero()) 941 { 942 rem= CFFactory::basic (0); 943 delete first; 944 } 945 else 946 rem = new InternalPoly( first, last, var ); 947 } 678 948 else 679 949 rem = CFFactory::basic( 0 ); … … 1027 1297 1028 1298 InternalCF* 1299 InternalPoly::tryDividecoeff( InternalCF* cc, bool invert, const CanonicalForm& M, bool& fail ) 1300 { 1301 CanonicalForm c( is_imm(cc) ? cc : cc>copyObject() ); 1302 if ( inExtension() && !getReduce( var ) && invert ) 1303 { 1304 InternalCF * dummy; 1305 dummy = this>tryInvert(M, fail); 1306 if (fail) 1307 { 1308 if (getRefCount() <= 1) 1309 delete this; 1310 else 1311 decRefCount(); 1312 return dummy; //is equal to CFFactory::basic (0) in this case 1313 } 1314 if (is_imm(dummy)) 1315 { 1316 if (is_imm(cc)) 1317 { 1318 InternalInteger *d=new InternalInteger(imm2int(dummy)*imm2int(cc)); 1319 dummy=d; 1320 } 1321 else 1322 dummy=cc>mulcoeff(dummy); 1323 } 1324 else dummy = dummy>mulcoeff( cc ); 1325 if ( getRefCount() <= 1 ) 1326 { 1327 delete this; 1328 return dummy; 1329 } 1330 else 1331 { 1332 decRefCount(); 1333 return dummy; 1334 } 1335 } 1336 if ( invert ) 1337 { 1338 if ( getRefCount() <= 1 ) 1339 { 1340 delete this; 1341 return CFFactory::basic( 0 ); 1342 } 1343 else 1344 { 1345 decRefCount(); 1346 return CFFactory::basic( 0 ); 1347 } 1348 } 1349 if ( c.isOne() ) 1350 return this; 1351 //one should never get here 1352 else 1353 { 1354 if ( getRefCount() <= 1 ) 1355 { 1356 firstTerm = divideTermList( firstTerm, c, lastTerm ); 1357 if ( firstTerm && firstTerm>exp != 0 ) 1358 return this; 1359 else if ( firstTerm ) 1360 { 1361 InternalCF * res = firstTerm>coeff.getval(); 1362 delete this; 1363 return res; 1364 } 1365 else 1366 { 1367 delete this; 1368 return CFFactory::basic( 0 ); 1369 } 1370 } 1371 else 1372 { 1373 decRefCount(); 1374 termList last, first = copyTermList( firstTerm, last ); 1375 first = divideTermList( first, c, last ); 1376 if ( first && first>exp != 0 ) 1377 return new InternalPoly( first, last, var ); 1378 else if ( first ) 1379 { 1380 InternalCF * res = first>coeff.getval(); 1381 delete first; 1382 return res; 1383 } 1384 else 1385 { 1386 delete first; 1387 return CFFactory::basic( 0 ); 1388 } 1389 } 1390 } 1391 } 1392 1393 1394 InternalCF* 1029 1395 InternalPoly::divcoeff( InternalCF* cc, bool invert ) 1030 1396 { … … 1103 1469 1104 1470 InternalCF* 1471 InternalPoly::tryDivcoeff( InternalCF* cc, bool invert, const CanonicalForm& M, bool& fail ) 1472 { 1473 CanonicalForm c( is_imm(cc) ? cc : cc>copyObject() ); 1474 if ( inExtension() && !getReduce( var ) && invert ) 1475 { 1476 InternalCF * dummy; 1477 dummy = this>tryInvert(M, fail); 1478 if (fail) 1479 { 1480 if (getRefCount() <= 1) 1481 delete this; 1482 else 1483 decRefCount(); 1484 return dummy; 1485 } 1486 dummy = dummy>mulcoeff( cc ); 1487 if ( getRefCount() <= 1 ) 1488 { 1489 delete this; 1490 return dummy; 1491 } 1492 else 1493 { 1494 decRefCount(); 1495 return dummy; 1496 } 1497 } 1498 if ( invert ) 1499 { 1500 if ( getRefCount() <= 1 ) 1501 { 1502 delete this; 1503 return CFFactory::basic( 0 ); 1504 } 1505 else 1506 { 1507 decRefCount(); 1508 return CFFactory::basic( 0 ); 1509 } 1510 } 1511 if ( c.isOne() ) 1512 return this; 1513 else 1514 { 1515 if ( getRefCount() <= 1 ) 1516 { 1517 firstTerm = tryDivTermList( firstTerm, c, lastTerm, M, fail ); 1518 if (fail) 1519 { 1520 delete this; 1521 return CFFactory::basic (0); 1522 } 1523 if ( firstTerm && firstTerm>exp != 0 ) 1524 return this; 1525 else if ( firstTerm ) 1526 { 1527 InternalCF * res = firstTerm>coeff.getval(); 1528 delete this; 1529 return res; 1530 } 1531 else 1532 { 1533 delete this; 1534 return CFFactory::basic( 0 ); 1535 } 1536 } 1537 else 1538 { 1539 decRefCount(); 1540 termList last, first = copyTermList( firstTerm, last ); 1541 first = tryDivTermList( first, c, last, M, fail ); 1542 if (fail) 1543 { 1544 delete this; 1545 return CFFactory::basic (0); 1546 } 1547 if (fail) 1548 { 1549 delete first; 1550 return CFFactory::basic (0); 1551 } 1552 if ( first && first>exp != 0 ) 1553 return new InternalPoly( first, last, var ); 1554 else if ( first ) 1555 { 1556 InternalCF * res = first>coeff.getval(); 1557 delete first; 1558 return res; 1559 } 1560 else 1561 { 1562 delete first; 1563 return CFFactory::basic( 0 ); 1564 } 1565 } 1566 } 1567 } 1568 1569 InternalCF* 1105 1570 InternalPoly::modulocoeff( InternalCF* cc, bool invert ) 1106 1571 { … … 1249 1714 { 1250 1715 divideok = divremt( cursor>coeff, c, cquot, crem ); 1716 divideok = divideok && crem.isZero(); 1717 if ( divideok ) 1718 { 1719 if ( ! cquot.isZero() ) 1720 { 1721 quotcursor>next = new term( 0, cquot, cursor>exp ); 1722 quotcursor = quotcursor>next; 1723 } 1724 cursor = cursor>next; 1725 } 1726 } 1727 quotcursor>next = 0; 1728 if ( divideok ) 1729 { 1730 cursor = quotfirst; quotfirst = quotfirst>next; delete cursor; 1731 if ( quotfirst ) 1732 if ( quotfirst>exp == 0 ) 1733 { 1734 quot = quotfirst>coeff.getval(); 1735 delete quotfirst; 1736 } 1737 else 1738 quot = new InternalPoly( quotfirst, quotcursor, var ); 1739 else 1740 quot = CFFactory::basic( 0 ); 1741 rem = CFFactory::basic( 0 ); 1742 } 1743 else 1744 { 1745 freeTermList( quotfirst ); 1746 } 1747 return divideok; 1748 } 1749 1750 bool 1751 InternalPoly::tryDivremcoefft( InternalCF* cc, InternalCF*& quot, InternalCF*& rem, bool invert, const CanonicalForm& M, bool& fail ) 1752 { 1753 if ( inExtension() && !getReduce( var ) ) 1754 { 1755 quot = copyObject(); 1756 quot = quot>tryDividecoeff( cc, invert, M, fail ); 1757 if (fail) 1758 return false; 1759 rem = CFFactory::basic( 0 ); 1760 return true; 1761 } 1762 else if ( invert ) 1763 { 1764 if ( is_imm( cc ) ) 1765 rem = cc; 1766 else 1767 rem = cc>copyObject(); 1768 quot = CFFactory::basic( 0 ); 1769 return true; 1770 } 1771 CanonicalForm c( is_imm(cc) ? cc : cc>copyObject() ); 1772 ASSERT( ! c.isZero(), "divide by zero!" ); 1773 termList quotfirst, quotcursor; 1774 termList cursor; 1775 CanonicalForm cquot, crem; 1776 bool divideok = true; 1777 1778 cursor = firstTerm; 1779 quotcursor = quotfirst = new term; 1780 1781 while ( cursor && divideok ) 1782 { 1783 divideok = tryDivremt( cursor>coeff, c, cquot, crem, M, fail ); 1784 if (fail) 1785 { 1786 freeTermList (quotfirst); 1787 return false; 1788 } 1251 1789 divideok = divideok && crem.isZero(); 1252 1790 if ( divideok ) … … 1529 2067 1530 2068 termList 2069 InternalPoly::tryDivTermList ( termList firstTerm, const CanonicalForm& coeff, termList& lastTerm, const CanonicalForm& M, bool& fail ) 2070 { 2071 termList theCursor = firstTerm; 2072 lastTerm = 0; 2073 termList dummy; 2074 2075 while ( theCursor ) 2076 { 2077 theCursor>coeff.tryDiv( coeff, M, fail ); 2078 if (fail) 2079 return 0; 2080 if ( theCursor>coeff.isZero() ) 2081 { 2082 if ( theCursor == firstTerm ) 2083 firstTerm = theCursor>next; 2084 else 2085 lastTerm>next = theCursor>next; 2086 dummy = theCursor; 2087 theCursor = theCursor>next; 2088 delete dummy; 2089 } 2090 else 2091 { 2092 lastTerm = theCursor; 2093 theCursor = theCursor>next; 2094 } 2095 } 2096 return firstTerm; 2097 } 2098 2099 termList 1531 2100 InternalPoly::modTermList ( termList firstTerm, const CanonicalForm& coeff, termList& lastTerm ) 1532 2101 { … … 1674 2243 return first; 1675 2244 } 2245 
factory/int_poly.h
re28e6d rec970e 71 71 static termList divideTermList ( termList, const CanonicalForm&, termList& ); 72 72 static termList divTermList ( termList, const CanonicalForm&, termList& ); 73 static termList tryDivTermList ( termList, const CanonicalForm&, termList&, const CanonicalForm&, bool& ); 73 74 static termList modTermList ( termList, const CanonicalForm&, termList& ); 74 75 static void appendTermList ( termList&, termList&, const CanonicalForm&, const int ); … … 106 107 InternalCF* neg(); 107 108 InternalCF* invert(); 108 109 InternalCF* tryInvert( const CanonicalForm&, bool& ); 109 110 int comparesame ( InternalCF* ); 110 111 … … 112 113 InternalCF* subsame( InternalCF* ); 113 114 InternalCF* mulsame( InternalCF* ); 115 InternalCF* tryMulsame ( InternalCF*, const CanonicalForm&); 114 116 InternalCF* dividesame( InternalCF* ); 115 117 InternalCF* modulosame( InternalCF* ); 116 118 InternalCF* divsame( InternalCF* ); 119 InternalCF* tryDivsame ( InternalCF*, const CanonicalForm&, bool& ); 117 120 InternalCF* modsame( InternalCF* ); 118 121 void divremsame( InternalCF*, InternalCF*&, InternalCF*& ); 119 122 bool divremsamet( InternalCF*, InternalCF*&, InternalCF*& ); 123 bool tryDivremsamet( InternalCF*, InternalCF*&, InternalCF*&, const CanonicalForm&, bool& ); 120 124 121 125 int comparecoeff ( InternalCF* ); … … 125 129 InternalCF* mulcoeff( InternalCF* ); 126 130 InternalCF* dividecoeff( InternalCF*, bool ); 131 InternalCF* tryDividecoeff ( InternalCF*, bool, const CanonicalForm&, bool& ); 127 132 InternalCF* modulocoeff( InternalCF*, bool ); 128 133 InternalCF* divcoeff( InternalCF*, bool ); 134 InternalCF* tryDivcoeff ( InternalCF*, bool, const CanonicalForm&, bool& ); 129 135 InternalCF* modcoeff( InternalCF*, bool ); 130 136 void divremcoeff( InternalCF*, InternalCF*&, InternalCF*&, bool ); 131 137 bool divremcoefft( InternalCF*, InternalCF*&, InternalCF*&, bool ); 138 bool tryDivremcoefft ( InternalCF*, InternalCF*&, InternalCF*&, bool, const CanonicalForm&, bool& ); 132 139 133 140 int sign() const;
Note: See TracChangeset
for help on using the changeset viewer.