 Timestamp:
 Jan 22, 1998, 11:56:22 AM (26 years ago)
 Branches:
 (u'spielwiese', 'e7cc1ebecb61be8b9ca6c18016352af89940b21a')
 Children:
 5f6df6f34dfdbe021b6854f9f20fa223f27dc78d
 Parents:
 05d0b37ce4c169ece2138d4d69b2e13b305468bb
 Location:
 factory
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

factory/canonicalform.cc
r05d0b3 r77aa42 1 1 /* emacs edit mode for this file is * C++ * */ 2 /* $Id: canonicalform.cc,v 1.2 4 19971218 17:05:33schmidt Exp $ */2 /* $Id: canonicalform.cc,v 1.25 19980122 10:56:12 schmidt Exp $ */ 3 3 4 4 #include <config.h> … … 1055 1055 // foo( i, f[ i ] ); 1056 1056 // 1057 // Thisis much slower than1057 // which is much slower than 1058 1058 // 1059 1059 // for ( int i = degree( f ), CFIterator I = f; I.hasTerms(); I++ ) { … … 1329 1329 // sensible to order these objects, e.g. to sort them. 1330 1330 // 1331 // For this reason, the ordering defined by these operators in 1332 // any case is a total ordering which fulfills the law of 1333 // trichotomy. 1331 // Therefore, the ordering defined by these operators in any case 1332 // is a total ordering which fulfills the law of trichotomy. 1334 1333 // 1335 1334 // It is clear how this is done in the case of the integers and … … 1491 1490 //}}} 1492 1491 1492 //{{{ CanonicalForm bgcd ( const CanonicalForm & f, const CanonicalForm & g ) 1493 //{{{ docu 1494 // 1495 // bgcd()  return base coefficient gcd. 1496 // 1497 // If both f and g are integers and `SW_RATIONAL' is off the 1498 // positive greatest common divisor of f and g is returned. 1499 // Otherwise, if `SW_RATIONAL' is on or one of f and g is not an 1500 // integer, the greatest common divisor is trivial: either zero 1501 // if f and g equal zero or one (both from the current domain). 1502 // 1503 // f and g should come from one base domain which should be not 1504 // the prime power domain. 1505 // 1506 // Implementation: 1507 // 1508 // CanonicalForm::bgcd() handles the immediate case with a 1509 // standard euclidean algorithm. For the nonimmediate cases 1510 // `InternalCF::bgcdsame()' or `InternalCF::bgcdcoeff()', resp. are 1511 // called following the usual level/levelcoeff approach. 1512 // 1513 // InternalCF::bgcdsame() and 1514 // InternalCF::bgcdcoeff() throw an assertion ("not implemented") 1515 // 1516 // InternalInteger::bgcdsame() is a wrapper around `mpz_gcd()' 1517 // which takes some care about immediate results and the sign 1518 // of the result 1519 // InternalInteger::bgcdcoeff() is a wrapper around 1520 // `mpz_gcd_ui()' which takes some care about the sign 1521 // of the result 1522 // 1523 // InternalRational::bgcdsame() and 1524 // InternalRational::bgcdcoeff() always return one 1525 // 1526 //}}} 1527 CanonicalForm 1528 bgcd ( const CanonicalForm & f, const CanonicalForm & g ) 1529 { 1530 // check immediate cases 1531 int what = is_imm( g.value ); 1532 if ( is_imm( f.value ) ) { 1533 ASSERT( ! what  (what == is_imm( f.value )), "incompatible operands" ); 1534 if ( what == 0 ) 1535 return g.value>bgcdcoeff( f.value ); 1536 else if ( what == INTMARK && ! cf_glob_switches.isOn( SW_RATIONAL ) ) { 1537 // calculate gcd using standard integer 1538 // arithmetic 1539 int fInt = imm2int( f.value ); 1540 int gInt = imm2int( g.value ); 1541 1542 if ( fInt < 0 ) fInt = fInt; 1543 if ( gInt < 0 ) gInt = gInt; 1544 // swap fInt and gInt 1545 if ( gInt > fInt ) { 1546 int swap = gInt; 1547 gInt = fInt; 1548 fInt = swap; 1549 } 1550 1551 // now, 0 <= gInt <= fInt. Start the loop. 1552 while ( gInt ) { 1553 // calculate (fInt, gInt) = (gInt, fInt%gInt) 1554 int r = fInt % gInt; 1555 fInt = gInt; 1556 gInt = r; 1557 } 1558 1559 return CanonicalForm( fInt ); 1560 } else 1561 // we do not go for maximal speed for these stupid 1562 // special cases 1563 return CanonicalForm( f.isZero() && g.isZero ? 0 : 1 ); 1564 } 1565 else if ( what ) 1566 return f.value>bgcdcoeff( g.value ); 1567 1568 int fLevel = f.value>level(); 1569 int gLevel = g.value>level(); 1570 1571 // check levels 1572 if ( fLevel == gLevel ) { 1573 fLevel = f.value>levelcoeff(); 1574 gLevel = g.value>levelcoeff(); 1575 1576 // check levelcoeffs 1577 if ( fLevel == gLevel ) 1578 return f.value>bgcdsame( g.value ); 1579 else if ( fLevel < gLevel ) 1580 return g.value>bgcdcoeff( f.value ); 1581 else 1582 return f.value>bgcdcoeff( g.value ); 1583 } 1584 else if ( fLevel < gLevel ) 1585 return g.value>bgcdcoeff( f.value ); 1586 else 1587 return f.value>bgcdcoeff( g.value ); 1588 } 1589 //}}} 1590 1591 //{{{ CanonicalForm bextgcd ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & a, CanonicalForm & b ) 1592 //{{{ docu 1593 // 1594 // bextgcd()  return base coefficient extended gcd. 1595 // 1596 //}}} 1597 CanonicalForm 1598 bextgcd ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & a, CanonicalForm & b ) 1599 { 1600 // check immediate cases 1601 int what = is_imm( g.value ); 1602 if ( is_imm( f.value ) ) { 1603 ASSERT( ! what  (what == is_imm( f.value )), "incompatible operands" ); 1604 if ( what == 0 ) 1605 return g.value>bextgcdcoeff( f.value, b, a ); 1606 else if ( what == INTMARK && ! cf_glob_switches.isOn( SW_RATIONAL ) ) { 1607 // calculate extended gcd using standard integer 1608 // arithmetic 1609 int fInt = imm2int( f.value ); 1610 int gInt = imm2int( g.value ); 1611 1612 // to avoid any system dpendencies with `%', we work 1613 // with positive numbers only. To a pity, we have to 1614 // redo all the checks when assigning to a and b. 1615 if ( fInt < 0 ) fInt = fInt; 1616 if ( gInt < 0 ) gInt = gInt; 1617 // swap fInt and gInt 1618 if ( gInt > fInt ) { 1619 int swap = gInt; 1620 gInt = fInt; 1621 fInt = swap; 1622 } 1623 1624 int u = 1; int v = 0; 1625 int uNext = 0; int vNext = 1; 1626 1627 // at any step, we have: 1628 // fInt_0 * u + gInt_0 * v = fInt 1629 // fInt_0 * uNext + gInt_0 * vNext = gInt 1630 // where fInt_0 and gInt_0 denote the values of fint 1631 // and gInt, resp., at the beginning 1632 while ( gInt ) { 1633 int r = fInt % gInt; 1634 int q = fInt / gInt; 1635 int uSwap = u  q * uNext; 1636 int vSwap = v  q * vNext; 1637 1638 // update variables 1639 fInt = gInt; 1640 gInt = r; 1641 u = uNext; v = vNext; 1642 uNext = uSwap; vNext = vSwap; 1643 } 1644 1645 // now, assign to a and b 1646 int fTest = imm2int( f.value ); 1647 int gTest = imm2int( g.value ); 1648 if ( gTest > fTest ) { 1649 a = v; b = u; 1650 } else { 1651 a = u; b = v; 1652 } 1653 if ( fTest < 0 ) a = a; 1654 if ( gTest < 0 ) b = b; 1655 return CanonicalForm( fInt ); 1656 } else 1657 // stupid special cases 1658 if ( ! f.isZero() ) { 1659 a = 1/f; b = 0; return CanonicalForm( 1 ); 1660 } else if ( ! g.isZero() ) { 1661 a = 0; b = 1/g; return CanonicalForm( 1 ); 1662 } else { 1663 a = 0; b = 0; return CanonicalForm( 0 ); 1664 } 1665 } 1666 else if ( what ) 1667 return f.value>bextgcdcoeff( g.value, a, b ); 1668 1669 int fLevel = f.value>level(); 1670 int gLevel = g.value>level(); 1671 1672 // check levels 1673 if ( fLevel == gLevel ) { 1674 fLevel = f.value>levelcoeff(); 1675 gLevel = g.value>levelcoeff(); 1676 1677 // check levelcoeffs 1678 if ( fLevel == gLevel ) 1679 return f.value>bextgcdsame( g.value, a, b ); 1680 else if ( fLevel < gLevel ) 1681 return g.value>bextgcdcoeff( f.value, b, a ); 1682 else 1683 return f.value>bextgcdcoeff( g.value, a, b ); 1684 } 1685 else if ( fLevel < gLevel ) 1686 return g.value>bextgcdcoeff( f.value, b, a ); 1687 else 1688 return f.value>bextgcdcoeff( g.value, a, b ); 1689 } 1690 //}}} 1691 1493 1692 //{{{ input/output 1494 1693 #ifndef NOSTREAMIO 
factory/canonicalform.h
r05d0b3 r77aa42 1 1 /* emacs edit mode for this file is * C++ * */ 2 /* $Id: canonicalform.h,v 1. 19 19971217 08:57:49schmidt Exp $ */2 /* $Id: canonicalform.h,v 1.20 19980122 10:56:22 schmidt Exp $ */ 3 3 4 4 #ifndef INCL_CANONICALFORM_H … … 140 140 friend bool divremt ( const CanonicalForm&, const CanonicalForm&, CanonicalForm&, CanonicalForm& ); 141 141 142 friend CanonicalForm bgcd ( const CanonicalForm &, const CanonicalForm & ); 143 friend CanonicalForm bextgcd ( const CanonicalForm &, const CanonicalForm &, CanonicalForm &, CanonicalForm & ); 144 145 // input/output 142 146 #ifndef NOSTREAMIO 143 147 void print( ostream&, char * ) const; … … 155 159 //}}} 156 160 157 // some useful functions158 159 161 //{{{ function declarations from canonicalform.cc 160 162 CanonicalForm power ( const CanonicalForm & f, int n ); 161 163 162 164 CanonicalForm power ( const Variable & v, int n ); 163 164 bool divides ( const CanonicalForm & f, const CanonicalForm & g );165 165 //}}} 166 166 … … 243 243 level ( const CanonicalForm & f ) { return f.level(); } 244 244 245 inline CanonicalForm245 inline Variable 246 246 mvar ( const CanonicalForm & f ) { return f.mvar(); } 247 247
Note: See TracChangeset
for help on using the changeset viewer.