[2dd068] | 1 | // emacs edit mode for this file is -*- C++ -*- |
---|
[173e86] | 2 | // $Id: fac_sqrfree.cc,v 1.4 1997-04-08 10:32:03 schmidt Exp $ |
---|
| 3 | |
---|
| 4 | #include <config.h> |
---|
[2dd068] | 5 | |
---|
| 6 | #include "assert.h" |
---|
[173e86] | 7 | |
---|
[2dd068] | 8 | #include "cf_defs.h" |
---|
| 9 | #include "canonicalform.h" |
---|
| 10 | |
---|
| 11 | /* |
---|
| 12 | $Log: not supported by cvs2svn $ |
---|
[173e86] | 13 | Revision 1.3 1996/12/05 18:24:55 schmidt |
---|
| 14 | ``Unconditional'' check-in. |
---|
| 15 | Now it is my turn to develop factory. |
---|
| 16 | |
---|
[e074407] | 17 | Revision 1.2 1996/06/26 13:15:28 stobbe |
---|
| 18 | "sqrFreeZ: Now handles the sign of the argument right. |
---|
| 19 | " |
---|
| 20 | |
---|
[36652d8] | 21 | Revision 1.1 1996/05/20 13:39:48 stobbe |
---|
| 22 | "sqrFree: Now the product of all factors found by sqrFree is equal to the |
---|
| 23 | parameter of sqrFree. The bug resulted from an incorrect handling |
---|
| 24 | of the leading coefficient of the argument of sqrFree. |
---|
| 25 | " |
---|
| 26 | |
---|
[d6b072c] | 27 | // Revision 1.0 1996/05/17 10:59:45 stobbe |
---|
| 28 | // Initial revision |
---|
| 29 | // |
---|
[2dd068] | 30 | */ |
---|
| 31 | |
---|
| 32 | static int divexp = 1; |
---|
| 33 | |
---|
| 34 | static void divexpfunc ( CanonicalForm &, int & e ) |
---|
| 35 | { |
---|
| 36 | e /= divexp; |
---|
| 37 | } |
---|
| 38 | |
---|
| 39 | CFFList sqrFreeFp ( const CanonicalForm & f ) |
---|
| 40 | { |
---|
| 41 | CanonicalForm t0 = f, t, v, w, h; |
---|
[d6b072c] | 42 | CanonicalForm leadcf = t0.lc(); |
---|
[2dd068] | 43 | Variable x = f.mvar(); |
---|
| 44 | CFFList F; |
---|
| 45 | int p = getCharacteristic(); |
---|
| 46 | int k, e = 1; |
---|
| 47 | |
---|
[d6b072c] | 48 | if ( ! leadcf.isOne() ) |
---|
| 49 | t0 /= leadcf; |
---|
| 50 | |
---|
[2dd068] | 51 | divexp = p; |
---|
| 52 | while ( t0.degree(x) > 0 ) { |
---|
| 53 | t = gcd( t0, t0.deriv() ); |
---|
| 54 | v = t0 / t; |
---|
| 55 | k = 0; |
---|
| 56 | while ( v.degree(x) > 0 ) { |
---|
| 57 | k = k+1; |
---|
| 58 | if ( k % p == 0 ) { |
---|
| 59 | t /= v; |
---|
| 60 | k = k+1; |
---|
| 61 | } |
---|
| 62 | w = gcd( t, v ); |
---|
| 63 | h = v / w; |
---|
| 64 | v = w; |
---|
| 65 | t /= v; |
---|
| 66 | if ( h.degree(x) > 0 ) |
---|
[d6b072c] | 67 | F.append( CFFactor( h/h.lc(), e*k ) ); |
---|
[2dd068] | 68 | } |
---|
| 69 | t0 = apply( t, divexpfunc ); |
---|
| 70 | e = p * e; |
---|
| 71 | } |
---|
[d6b072c] | 72 | if ( ! leadcf.isOne() ) { |
---|
| 73 | if ( F.getFirst().exp() == 1 ) { |
---|
| 74 | leadcf = F.getFirst().factor() * leadcf; |
---|
| 75 | F.removeFirst(); |
---|
| 76 | } |
---|
| 77 | F.insert( CFFactor( leadcf, 1 ) ); |
---|
| 78 | } |
---|
[2dd068] | 79 | return F; |
---|
| 80 | } |
---|
| 81 | |
---|
| 82 | bool isSqrFreeFp( const CanonicalForm & f ) |
---|
| 83 | { |
---|
| 84 | CFFList F = sqrFreeFp( f ); |
---|
| 85 | return ( F.length() == 1 && F.getFirst().exp() == 1 ); |
---|
| 86 | } |
---|
| 87 | |
---|
| 88 | int isSqrFreeZ ( const CanonicalForm & f ) |
---|
| 89 | { |
---|
| 90 | return gcd( f, f.deriv() ).degree() == 0; |
---|
| 91 | } |
---|
| 92 | |
---|
| 93 | /* |
---|
| 94 | |
---|
| 95 | CFFList sqrFreeZ ( const CanonicalForm & a ) |
---|
| 96 | { |
---|
| 97 | CanonicalForm b = a.deriv(), c = gcd( a, b ); |
---|
| 98 | CanonicalForm y, z, w = a / c; |
---|
| 99 | int i = 1; |
---|
| 100 | CFFList F; |
---|
| 101 | |
---|
| 102 | while ( ! c.degree() == 0 ) { |
---|
| 103 | y = gcd( w, c ); z = w / y; |
---|
| 104 | if ( degree( z ) > 0 ) |
---|
| 105 | if ( lc( z ).sign() < 0 ) |
---|
| 106 | F.append( CFFactor( -z, i ) ); |
---|
| 107 | else |
---|
| 108 | F.append( CFFactor( z, i ) ); |
---|
| 109 | i++; |
---|
| 110 | w = y; c = c / y; |
---|
| 111 | } |
---|
| 112 | if ( degree( w ) > 0 ) |
---|
| 113 | if ( lc( w ).sign() < 0 ) |
---|
| 114 | F.append( CFFactor( -w, i ) ); |
---|
| 115 | else |
---|
| 116 | F.append( CFFactor( w, i ) ); |
---|
| 117 | return F; |
---|
| 118 | } |
---|
| 119 | */ |
---|
| 120 | |
---|
| 121 | CFFList sqrFreeZ ( const CanonicalForm & a ) |
---|
| 122 | { |
---|
| 123 | if ( a.inCoeffDomain() ) |
---|
| 124 | return CFFactor( a, 1 ); |
---|
| 125 | CanonicalForm cont = content( a ); |
---|
| 126 | CanonicalForm aa = a / cont; |
---|
| 127 | CanonicalForm b = aa.deriv(), c = gcd( aa, b ); |
---|
| 128 | CanonicalForm y, z, w = aa / c; |
---|
| 129 | int i = 1; |
---|
| 130 | CFFList F; |
---|
| 131 | Variable v = aa.mvar(); |
---|
| 132 | while ( ! c.degree(v) == 0 ) { |
---|
| 133 | y = gcd( w, c ); z = w / y; |
---|
| 134 | if ( degree( z, v ) > 0 ) |
---|
| 135 | if ( lc( z ).sign() < 0 ) |
---|
| 136 | F.append( CFFactor( -z, i ) ); |
---|
| 137 | else |
---|
| 138 | F.append( CFFactor( z, i ) ); |
---|
| 139 | i++; |
---|
| 140 | w = y; c = c / y; |
---|
| 141 | } |
---|
| 142 | if ( degree( w,v ) > 0 ) |
---|
| 143 | if ( lc( w ).sign() < 0 ) |
---|
| 144 | F.append( CFFactor( -w, i ) ); |
---|
| 145 | else |
---|
| 146 | F.append( CFFactor( w, i ) ); |
---|
[e074407] | 147 | if ( ! cont.isOne() ) |
---|
[36652d8] | 148 | F = Union( F, sqrFreeZ( cont ) ); |
---|
| 149 | if ( lc( a ).sign() < 0 ) { |
---|
| 150 | if ( F.getFirst().exp() == 1 ) { |
---|
| 151 | CanonicalForm f = F.getFirst().factor(); |
---|
| 152 | CFFListIterator(F).getItem() = CFFactor( -f, 1 ); |
---|
| 153 | } |
---|
| 154 | else |
---|
| 155 | F.insert( CFFactor( -1, 1 ) ); |
---|
| 156 | } |
---|
| 157 | return F; |
---|
[2dd068] | 158 | } |
---|