Changeset 7514:f160b84bfb0d
- Timestamp:
- 12/02/07 12:25:42 (5 years ago)
- Branch:
- default
- Parents:
- 7512:d5a382d783b4 (diff), 7513:c52f4c723299 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent. - Location:
- sage/rings
- Files:
-
- 12 edited
-
fraction_field_element.py (modified) (1 diff)
-
fraction_field_element.py (modified) (2 diffs)
-
ideal.py (modified) (1 diff)
-
ideal.py (modified) (4 diffs)
-
polynomial/multi_polynomial_ideal.py (modified) (1 diff)
-
polynomial/multi_polynomial_ideal.py (modified) (3 diffs)
-
polynomial/multi_polynomial_libsingular.pyx (modified) (3 diffs)
-
polynomial/multi_polynomial_libsingular.pyx (modified) (13 diffs)
-
polynomial/polynomial_element.pyx (modified) (4 diffs)
-
polynomial/polynomial_element.pyx (modified) (26 diffs)
-
polynomial/polynomial_integer_dense_ntl.pyx (modified) (2 diffs)
-
polynomial/polynomial_integer_dense_ntl.pyx (modified) (3 diffs)
Legend:
- Unmodified
- Added
- Removed
-
sage/rings/fraction_field_element.py
r7473 r7514 99 99 def denominator(self): 100 100 return self.__denominator 101 101 102 def __hash__(self): 103 """ 104 This function hashes in a special way to ensure that generators of a ring R 105 and generators of a fraction field of R have the same hash. This enables them 106 to be used as keys interchangably in a dictionary (since \code{==} will claim them equal). 107 This is particularly useful for methods like subs on \code{ParentWithGens} if you 108 are passing a dictionary of substitutions. 109 110 EXAMPLES: 111 sage: R.<x>=ZZ[] 112 sage: hash(R.0)==hash(FractionField(R).0) 113 True 114 sage: ((x+1)/(x^2+1)).subs({x:1}) 115 1 116 sage: d={x:1} 117 sage: d[FractionField(R).0] 118 1 119 sage: R.<x>=QQ[] # this probably has a separate implementation from ZZ[] 120 sage: hash(R.0)==hash(FractionField(R).0) 121 True 122 sage: d={x:1} 123 sage: d[FractionField(R).0] 124 1 125 sage: R.<x,y,z>=ZZ[] # this probably has a separate implementation from ZZ[] 126 sage: hash(R.0)==hash(FractionField(R).0) 127 True 128 sage: d={x:1} 129 sage: d[FractionField(R).0] 130 1 131 sage: R.<x,y,z>=QQ[] # this probably has a separate implementation from ZZ[] 132 sage: hash(R.0)==hash(FractionField(R).0) 133 True 134 sage: ((x+1)/(x^2+1)).subs({x:1}) 135 1 136 sage: d={x:1} 137 sage: d[FractionField(R).0] 138 1 139 sage: hash(R(1)/R(2))==hash(1/2) 140 True 141 """ 142 # This is same algorithm as used for members of QQ 143 #cdef long n, d 144 n = hash(self.__numerator) 145 d = hash(self.__denominator) 146 if d == 1: 147 return n 148 n = n ^ d 149 if n == -1: 150 return -2 151 return n 152 102 153 def partial_fraction_decomposition(self): 103 154 """ -
sage/rings/fraction_field_element.py
r7513 r7514 157 157 158 158 The sum will be equal to the original fraction. 159 159 AUTHOR: 160 -- Robert Bradshaw (2007-05-31) 160 161 EXAMPLES: 161 162 sage: S.<t> = QQ[] … … 177 178 (1.0000*x^4 + 4.0000*x^2 + 1.0000*x + 3.0000)/(1.0000*x^5 - 1.0000*x^4 + 4.0000*x^3 - 4.0000*x^2 + 4.0000*x - 4.0000) 178 179 sage: whole, parts = q.partial_fraction_decomposition(); parts 179 [(- 0.0000076294*x^2 + 1.0000)/(1.0000*x^4 + 4.0000*x^2 + 4.0000), 1.0000/(1.0000*x - 1.0000)]180 [(-7.6294e-6*x^2 + 1.0000)/(1.0000*x^4 + 4.0000*x^2 + 4.0000), 1.0000/(1.0000*x - 1.0000)] 180 181 sage: sum(parts) 181 (1.0000*x^4 - 0.0000076294*x^3 + 4.0000*x^2 + 1.0000*x + 3.0000)/(1.0000*x^5 - 1.0000*x^4 + 4.0000*x^3 - 4.0000*x^2 + 4.0000*x - 4.0000) 182 183 AUTHOR: 184 -- Robert Bradshaw (2007-05-31) 182 (1.0000*x^4 - 7.6294e-6*x^3 + 4.0000*x^2 + 1.0000*x + 3.0000)/(1.0000*x^5 - 1.0000*x^4 + 4.0000*x^3 - 4.0000*x^2 + 4.0000*x - 4.0000) 185 183 """ 186 184 denom = self.denominator() -
sage/rings/ideal.py
r7454 r7514 77 77 sage: i = ideal(1,t,t^2) 78 78 sage: i 79 Ideal (t , 1, t^2) of Univariate Polynomial Ring in t over Integer Ring79 Ideal (t^2, 1, t) of Univariate Polynomial Ring in t over Integer Ring 80 80 sage: ideal(1/2,t,t^2) 81 81 Principal ideal (1) of Univariate Polynomial Ring in t over Rational Field -
sage/rings/ideal.py
r7513 r7514 187 187 188 188 def __nonzero__(self): 189 return self.gens() != [self.ring()(0)] 189 r"""Return True if this ideal is not (0). 190 191 TESTS: 192 193 sage: I = ZZ.ideal(5) 194 sage: bool(I) 195 True 196 197 sage: I = ZZ['x'].ideal(0) 198 sage: bool(I) 199 False 200 201 sage: I = ZZ['x'].ideal(ZZ['x'].gen()^2) 202 sage: bool(I) 203 True 204 205 sage: I = QQ['x', 'y'].ideal(0) 206 sage: bool(I) 207 False 208 """ 209 for g in self.gens(): 210 if not g.is_zero(): 211 return True 212 return False 190 213 191 214 def base_ring(self): … … 260 283 261 284 def is_trivial(self): 285 r"""Return True if this ideal is (0) or (1). 286 287 TESTS: 288 289 sage: I = ZZ.ideal(5) 290 sage: I.is_trivial() 291 False 292 293 sage: I = ZZ['x'].ideal(-1) 294 sage: I.is_trivial() 295 True 296 297 sage: I = ZZ['x'].ideal(ZZ['x'].gen()^2) 298 sage: I.is_trivial() 299 False 300 301 sage: I = QQ['x', 'y'].ideal(-5) 302 sage: I.is_trivial() 303 True 304 305 sage: I = CC['x'].ideal(0) 306 sage: I.is_trivial() 307 True 308 """ 262 309 if self.is_zero(): 263 310 return True 264 elif self.is_principal(): 265 return self.gen().is_unit() 311 # If self is principal, can give a complete answer 312 if self.is_principal(): 313 return self.gens()[0].is_unit() 314 # If self is not principal, can only give an affirmative answer 315 for g in self.gens(): 316 if g.is_unit(): 317 return True 266 318 raise NotImplementedError 267 319 … … 313 365 314 366 def __contains__(self, x): 367 """ 368 Returns True if x is in the ideal self. 369 370 EXAMPLES: 371 sage: P.<x> = PolynomialRing(ZZ) 372 sage: I = P.ideal(x^2-2) 373 sage: x^2 in I 374 False 375 sage: x^2-2 in I 376 True 377 sage: x^2-3 in I 378 False 379 """ 315 380 if self.gen().is_zero(): 316 381 return x.is_zero() … … 339 404 """ 340 405 Returns True if self divides other. 406 407 EXAMPLES: 408 sage: P.<x> = PolynomialRing(QQ) 409 sage: I = P.ideal(x) 410 sage: J = P.ideal(x^2) 411 sage: I.divides(J) 412 True 413 sage: J.divides(I) 414 False 341 415 """ 342 416 if isinstance(other, Ideal_principal): -
sage/rings/polynomial/multi_polynomial_ideal.py
r7397 r7514 1288 1288 sage: I = sage.rings.ideal.Katsura(P,3) # regenerate to prevent caching 1289 1289 sage: I.groebner_basis('toy:buchberger') 1290 [-30*c^4 + 100/7*c^3 - 5/14*c^2 - 5/14*c, -2*b^2 - b*c + 1/2*b, -7/125*b - 42/25*c^3 + 79/125*c^2 - 3/125*c, 1291 a + 2*b + 2*c - 1, a^2 - a + 2*b^2 + 2*c^2, -5*b*c + 1/2*b - 6*c^2 + 2*c, 2*a*b + 2*b*c - b] 1292 1290 [a + 2*b + 2*c - 1, -6*b^2 - 8*b*c + 2*b - 6*c^2 + 2*c, 2*a*b + 2*b*c - b, 7/250*b + 21/25*c^3 - 79/250*c^2 + 3/250*c, a^2 - a + 2*b^2 + 2*c^2, -5/3*b*c + 1/6*b - 2*c^2 + 2/3*c, -30*c^4 + 100/7*c^3 - 5/14*c^2 - 5/14*c] 1291 1293 1292 sage: I = sage.rings.ideal.Katsura(P,3) # regenerate to prevent caching 1294 1293 sage: I.groebner_basis('toy:buchberger2') 1295 [30*c^4 - 100/7*c^3 + 5/14*c^2 + 5/14*c, a + 2*b + 2*c - 1, 1296 7/125*b + 42/25*c^3 - 79/125*c^2 + 3/125*c, a^2 - a + 2*b^2 + 2*c^2] 1294 [a + 2*b + 2*c - 1, a^2 - a + 2*b^2 + 2*c^2, 30*c^4 - 100/7*c^3 + 5/14*c^2 + 5/14*c, -7/250*b - 21/25*c^3 + 79/250*c^2 - 3/250*c] 1297 1295 1298 1296 sage: I = sage.rings.ideal.Katsura(P,3) # regenerate to prevent caching -
sage/rings/polynomial/multi_polynomial_ideal.py
r7513 r7514 375 375 sage: GB = Ideal(I.groebner_basis('singular:stdfglm')) 376 376 sage: GB.triangular_decomposition('singular:triangLfak') 377 [Ideal (a - 1, b - 1, c - 1, d^2 + 3*d + 1, e + d + 3) of 378 Multivariate Polynomial Ring in e, d, c, b, a over 379 Rational Field, 380 Ideal (a - 1, b - 1, c^2 + 3*c + 1, d + c + 3, e - 1) of 381 Multivariate Polynomial Ring in e, d, c, b, a over 382 Rational Field, 383 Ideal (a - 1, b^4 + b^3 + b^2 + b + 1, c - b^2, d - b^3, e 384 + b^3 + b^2 + b + 1) of Multivariate Polynomial Ring in e, 385 d, c, b, a over Rational Field, 386 Ideal (a - 1, b^2 + 3*b + 1, c + b + 3, d - 1, e - 1) of 387 Multivariate Polynomial Ring in e, d, c, b, a over 388 Rational Field, 389 Ideal (a^4 + a^3 + a^2 + a + 1, b - 1, c + a^3 + a^2 + a + 390 1, d - a^3, e - a^2) of Multivariate Polynomial Ring in e, 391 d, c, b, a over Rational Field, Ideal (a^4 + a^3 + a^2 + a 392 + 1, b - a, c - a, d^2 + 3*d*a + a^2, e + d + 3*a) of 393 Multivariate Polynomial Ring in e, d, c, b, a over 394 Rational Field, 395 Ideal (a^4 + a^3 + a^2 + a + 1, b - a, c^2 + 3*c*a + a^2, 396 d + c + 3*a, e - a) of Multivariate Polynomial Ring in e, 397 d, c, b, a over Rational Field, 398 Ideal (a^4 + a^3 + a^2 + a + 1, b^3 + b^2*a + b^2 + b*a^2 399 + b*a + b + a^3 + a^2 + a + 1, c + b^2*a^3 + b^2*a^2 + 400 b^2*a + b^2, d - b^2*a^2 - b^2*a - b^2 - b*a^2 - b*a - 401 a^2, e - b^2*a^3 + b*a^2 + b*a + b + a^2 + a) of 402 Multivariate Polynomial Ring in e, d, c, b, a over 403 Rational Field, 404 Ideal (a^4 + a^3 + a^2 + a + 1, b^2 + 3*b*a + a^2, c + b + 405 3*a, d - a, e - a) of Multivariate Polynomial Ring in e, 406 d, c, b, a over Rational Field, 407 Ideal (a^4 + a^3 + 6*a^2 - 4*a + 1, 11*b^2 - 6*b*a^3 - 408 10*b*a^2 - 39*b*a - 2*b - 16*a^3 - 23*a^2 - 104*a + 24, 409 11*c + 3*a^3 + 5*a^2 + 25*a + 1, 11*d + 3*a^3 + 5*a^2 + 410 25*a + 1, 11*e + 11*b - 6*a^3 - 10*a^2 - 39*a - 2) of 411 Multivariate Polynomial Ring in e, d, c, b, a over 412 Rational Field, 413 Ideal (a^4 - 4*a^3 + 6*a^2 + a + 1, 11*b^2 - 6*b*a^3 + 414 26*b*a^2 - 41*b*a + 4*b + 8*a^3 - 31*a^2 + 40*a + 24, 11*c 415 + 3*a^3 - 13*a^2 + 26*a - 2, 11*d + 3*a^3 - 13*a^2 + 26*a 416 - 2, 11*e + 11*b - 6*a^3 + 26*a^2 - 41*a + 4) of 417 Multivariate Polynomial Ring in e, d, c, b, a over 418 Rational Field, 419 Ideal (a^2 + 3*a + 1, b - 1, c - 1, d - 1, e + a + 3) of 420 Multivariate Polynomial Ring in e, d, c, b, a over 421 Rational Field, Ideal (a^2 + 3*a + 1, b + a + 3, c - 1, d 422 - 1, e - 1) of Multivariate Polynomial Ring in e, d, c, b, 423 a over Rational Field] 377 [Ideal (a - 1, b - 1, c - 1, d^2 + 3*d + 1, e + d + 3) of Multivariate Polynomial Ring in e, d, c, b, a over Rational Field, 378 Ideal (a - 1, b - 1, c^2 + 3*c + 1, d + c + 3, e - 1) of Multivariate Polynomial Ring in e, d, c, b, a over Rational Field, 379 Ideal (a - 1, b^2 + 3*b + 1, c + b + 3, d - 1, e - 1) of Multivariate Polynomial Ring in e, d, c, b, a over Rational Field, 380 Ideal (a - 1, b^4 + b^3 + b^2 + b + 1, c - b^2, d - b^3, e + b^3 + b^2 + b + 1) of Multivariate Polynomial Ring in e, d, c, b, a over Rational Field, 381 Ideal (a^2 + 3*a + 1, b - 1, c - 1, d - 1, e + a + 3) of Multivariate Polynomial Ring in e, d, c, b, a over Rational Field, 382 Ideal (a^2 + 3*a + 1, b + a + 3, c - 1, d - 1, e - 1) of Multivariate Polynomial Ring in e, d, c, b, a over Rational Field, 383 Ideal (a^4 - 4*a^3 + 6*a^2 + a + 1, 11*b^2 - 6*b*a^3 + 26*b*a^2 - 41*b*a + 4*b + 8*a^3 - 31*a^2 + 40*a + 24, 11*c + 3*a^3 - 13*a^2 + 26*a - 2, 11*d + 3*a^3 - 13*a^2 + 26*a - 2, 11*e + 11*b - 6*a^3 + 26*a^2 - 41*a + 4) of Multivariate Polynomial Ring in e, d, c, b, a over Rational Field, 384 Ideal (a^4 + a^3 + a^2 + a + 1, b - 1, c + a^3 + a^2 + a + 1, d - a^3, e - a^2) of Multivariate Polynomial Ring in e, d, c, b, a over Rational Field, 385 Ideal (a^4 + a^3 + a^2 + a + 1, b - a, c - a, d^2 + 3*d*a + a^2, e + d + 3*a) of Multivariate Polynomial Ring in e, d, c, b, a over Rational Field, 386 Ideal (a^4 + a^3 + a^2 + a + 1, b - a, c^2 + 3*c*a + a^2, d + c + 3*a, e - a) of Multivariate Polynomial Ring in e, d, c, b, a over Rational Field, 387 Ideal (a^4 + a^3 + a^2 + a + 1, b^2 + 3*b*a + a^2, c + b + 3*a, d - a, e - a) of Multivariate Polynomial Ring in e, d, c, b, a over Rational Field, 388 Ideal (a^4 + a^3 + a^2 + a + 1, b^3 + b^2*a + b^2 + b*a^2 + b*a + b + a^3 + a^2 + a + 1, c + b^2*a^3 + b^2*a^2 + b^2*a + b^2, d - b^2*a^2 - b^2*a - b^2 - b*a^2 - b*a - a^2, e - b^2*a^3 + b*a^2 + b*a + b + a^2 + a) of Multivariate Polynomial Ring in e, d, c, b, a over Rational Field, 389 Ideal (a^4 + a^3 + 6*a^2 - 4*a + 1, 11*b^2 - 6*b*a^3 - 10*b*a^2 - 39*b*a - 2*b - 16*a^3 - 23*a^2 - 104*a + 24, 11*c + 3*a^3 + 5*a^2 + 25*a + 1, 11*d + 3*a^3 + 5*a^2 + 25*a + 1, 11*e + 11*b - 6*a^3 - 10*a^2 - 39*a - 2) of Multivariate Polynomial Ring in e, d, c, b, a over Rational Field] 424 390 """ 425 391 … … 472 438 473 439 T = Sequence([ MPolynomialIdeal(Q,[f._sage_(Q) for f in t]) for t in Tbar ]) 440 441 def f(x,y): return cmp(x.gens(), y.gens()) 442 T.sort(f) 474 443 475 444 return T … … 1088 1057 48 1089 1058 1059 TESTS: 1060 sage: K.<w> = GF(27) 1061 sage: P.<x, y> = PolynomialRing(K, 2, order='lex') 1062 sage: I = Ideal([ x^8 + y + 2, y^6 + x*y^5 + x^2 ]) 1063 1064 Testing the robustness of the Singular interface 1065 1066 sage: T = I.triangular_decomposition('singular:triangLfak') 1067 sage: I.variety() 1068 [{y: w^2 + 2, x: 2*w}, {y: w^2 + w, x: 2*w + 1}, {y: w^2 + 2*w, x: 2*w + 2}] 1069 1090 1070 ALGORITHM: Uses triangular decomposition. 1091 1071 """ -
sage/rings/polynomial/multi_polynomial_libsingular.pyx
r7414 r7514 1427 1427 else: 1428 1428 return co.new_MP(parent, res) 1429 1429 1430 # you may have to replicate this boilerplate code in derived classes if you override 1431 # __richcmp__. The python documentation at http://docs.python.org/api/type-structs.html 1432 # explains how __richcmp__, __hash__, and __cmp__ are tied together. 1433 def __hash__(self): 1434 return self._hash_c() 1435 1430 1436 def __richcmp__(left, right, int op): 1431 1437 return (<Element>left)._richcmp(right, op) … … 2171 2177 p = pNext(p) 2172 2178 return pd 2173 2179 2180 cdef long _hash_c(self): 2181 """ 2182 This hash incorporates the variable name in an effort to respect the obvious inclusions 2183 into multi-variable polynomial rings. 2184 2185 The tuple algorithm is borrowed from http://effbot.org/zone/python-hash.htm. 2186 2187 EXAMPLES: 2188 sage: R.<x>=QQ[] 2189 sage: S.<x,y>=QQ[] 2190 sage: hash(S(1/2))==hash(1/2) # respect inclusions of the rationals 2191 True 2192 sage: hash(S.0)==hash(R.0) # respect inclusions into mpoly rings 2193 True 2194 sage: # the point is to make for more flexible dictionary look ups 2195 sage: d={S.0:12} 2196 sage: d[R.0] 2197 12 2198 """ 2199 cdef poly *p 2200 cdef ring *r 2201 cdef int n 2202 cdef int v 2203 r = (<MPolynomialRing_libsingular>self._parent)._ring 2204 if r!=currRing: rChangeCurrRing(r) 2205 base = (<MPolynomialRing_libsingular>self._parent)._base 2206 p = self._poly 2207 cdef long result = 0 # store it in a c-int and just let the overflowing additions wrap 2208 cdef long result_mon 2209 var_name_hash = [hash(vn) for vn in self._parent.variable_names()] 2210 cdef long c_hash 2211 while p: 2212 c_hash = hash(co.si2sa(p_GetCoeff(p, r), r, base)) 2213 if c_hash != 0: # this is always going to be true, because we are sparse (correct?) 2214 # Hash (self[i], gen_a, exp_a, gen_b, exp_b, gen_c, exp_c, ...) as a tuple according to the algorithm. 2215 # I omit gen,exp pairs where the exponent is zero. 2216 result_mon = c_hash 2217 for v from 1 <= v <= r.N: 2218 n = p_GetExp(p,v,r) 2219 if n!=0: 2220 result_mon = (1000003 * result_mon) ^ var_name_hash[v-1] 2221 result_mon = (1000003 * result_mon) ^ n 2222 result += result_mon 2223 2224 p = pNext(p) 2225 if result == -1: 2226 return -2 2227 return result 2228 2174 2229 def __iter__(self): 2175 2230 """ … … 2845 2900 cdef int is_constant_c(self): 2846 2901 return p_IsConstant(self._poly, (<MPolynomialRing_libsingular>self._parent)._ring) 2847 2848 def __hash__(self):2849 """2850 """2851 s = p_String(self._poly, (<MPolynomialRing_libsingular>self._parent)._ring, (<MPolynomialRing_libsingular>self._parent)._ring)2852 return hash(s)2853 2902 2854 2903 def lm(MPolynomial_libsingular self): -
sage/rings/polynomial/multi_polynomial_libsingular.pyx
r7513 r7514 200 200 self._has_singular = True 201 201 202 _names = <char**>omAlloc0(sizeof(char*)*(len(self._names)+1)) 202 assert(n == len(self._names)) 203 204 _names = <char**>omAlloc0(sizeof(char*)*(len(self._names))) 203 205 204 206 for i from 0 <= i < n: … … 290 292 """ 291 293 """ 292 rChangeCurrRing(self._ring) 294 cdef ring *oldRing = NULL 295 if currRing != self._ring: 296 oldRing = currRing 297 rChangeCurrRing(self._ring) 293 298 rDelete(self._ring) 299 if oldRing != NULL: 300 rChangeCurrRing(oldRing) 294 301 295 302 cdef _coerce_c_impl(self, element): … … 548 555 p_Setm(mon, _ring) 549 556 _p = p_Add_q(_p, mon, _ring) 557 550 558 return co.new_MP(self, _p) 551 559 … … 662 670 663 671 """ 672 coerce = kwds.get('coerce', True) 664 673 if len(gens) == 1: 665 674 gens = gens[0] … … 793 802 if self.base_ring().is_finite(): 794 803 R.set_ring() #sorry for that, but needed for minpoly 795 if singular.eval('minpoly') != self.__minpoly:804 if singular.eval('minpoly') != "(" + self.__minpoly + ")": 796 805 singular.eval("minpoly=%s"%(self.__minpoly)) 806 self.__minpoly = singular.eval('minpoly')[1:-1] # store in correct format 797 807 return R 798 808 except (AttributeError, ValueError): … … 860 870 gen = str(self.base_ring().gen()) 861 871 r = singular.ring( "(%s,%s)"%(self.characteristic(),gen), _vars, order=order) 862 self.__minpoly = "("+(str(self.base_ring().modulus()).replace("x",gen)).replace(" ","")+")" 863 singular.eval("minpoly=%s"%(self.__minpoly) ) 864 872 self.__minpoly = (str(self.base_ring().modulus()).replace("x",gen)).replace(" ","") 873 if singular.eval('minpoly') != "(" + self.__minpoly + ")": 874 singular.eval("minpoly=%s"%(self.__minpoly) ) 875 self.__minpoly = singular.eval('minpoly')[1:-1] 865 876 self.__singular = r 866 877 else: … … 1545 1556 _p= p_Add_q(_l, _r, _ring) 1546 1557 1547 p_Normalize(_p,_ring)1548 1549 1558 return co.new_MP((<MPolynomialRing_libsingular>left._parent),_p) 1550 1559 … … 1573 1582 _p= p_Add_q(_l, _r, _ring) 1574 1583 1575 p_Normalize(_p,_ring)1576 1584 left._poly = _p 1577 1585 return left … … 1624 1632 if(_ring != currRing): rChangeCurrRing(_ring) 1625 1633 _p= p_Add_q(_l, p_Neg(_r, _ring), _ring) 1626 p_Normalize(_p,_ring)1627 1634 left._poly = _p 1628 1635 return left … … 1775 1782 1776 1783 if(_ring != currRing): rChangeCurrRing(_ring) 1777 1778 1784 _p = pPower( p_Copy(self._poly,_ring),_exp) 1779 1780 1785 return co.new_MP((<MPolynomialRing_libsingular>self._parent),_p) 1781 1782 1786 1783 1787 def __neg__(self): … … 2359 2363 Multivariate Polynomial Ring in x, y over Finite Field of size 389 2360 2364 """ 2365 cdef ring *r = (<MPolynomialRing_libsingular>self._parent)._ring 2366 if r != currRing: rChangeCurrRing(r) 2367 2361 2368 cdef poly *p = self._poly 2362 2369 cdef poly *m = mon._poly 2363 cdef ring *r = (<MPolynomialRing_libsingular>self._parent)._ring2364 cdef poly *res = p_ISet(0,r)2365 2370 cdef poly *t 2366 2371 cdef int exactly_divisible, i 2367 if(r != currRing): rChangeCurrRing(r) 2372 cdef poly *res = p_ISet(0,r) 2373 2368 2374 2369 2375 if not mon._parent is self._parent: 2370 2376 raise TypeError, "mon must have same parent as self" 2371 2377 2372 while (p):2378 while p: 2373 2379 exactly_divisible = 1 2374 2380 for i from 1 <= i <= r.N: … … 2377 2383 break 2378 2384 if exactly_divisible: 2379 t = pDivide(p, m)2385 t = pDivide(p, m) 2380 2386 p_SetCoeff(t, n_Div( p_GetCoeff(p, r) , p_GetCoeff(m, r), r), r) 2381 2387 res = p_Add_q(res, t , r ) … … 3059 3065 ptemp = p_Copy(self._poly,_ring) 3060 3066 iv = NULL 3067 _sig_on 3061 3068 I = singclap_factorize ( ptemp, &iv , int(param)) #delete iv at some point 3069 _sig_off 3062 3070 3063 3071 if param==1: -
sage/rings/polynomial/polynomial_element.pyx
r7509 r7514 62 62 63 63 from sage.rings.integral_domain import is_IntegralDomain 64 from sage.structure.parent_gens cimport ParentWithGens 64 65 65 66 import polynomial_fateman … … 495 496 def __iter__(self): 496 497 return iter(self.list()) 497 498 499 # you may have to replicate this boilerplate code in derived classes if you override 500 # __richcmp__. The python documentation at http://docs.python.org/api/type-structs.html 501 # explains how __richcmp__, __hash__, and __cmp__ are tied together. 498 502 def __hash__(self): 499 if self.degree() >= 1: 500 return hash(tuple(self.list())) 501 else: 502 return hash(self[0]) 503 503 return self._hash_c() 504 505 cdef long _hash_c(self): 506 """ 507 This hash incorporates the variable name in an effort to respect the obvious inclusions 508 into multi-variable polynomial rings. 509 510 The tuple algorithm is borrowed from http://effbot.org/zone/python-hash.htm. 511 512 EXAMPLES: 513 sage: R.<x>=ZZ[] 514 sage: hash(R(1))==hash(1) # respect inclusions of the integers 515 True 516 sage: hash(R.0)==hash(FractionField(R).0) # respect inclusions into the fraction field 517 True 518 sage: R.<x>=QQ[] 519 sage: hash(R(1/2))==hash(1/2) # respect inclusions of the rationals 520 True 521 sage: hash(R.0)==hash(FractionField(R).0) # respect inclusions into the fraction field 522 True 523 sage: R.<x>=IntegerModRing(11)[] 524 sage: hash(R.0)==hash(FractionField(R).0) # respect inclusions into the fraction field 525 True 526 """ 527 cdef long result = 0 # store it in a c-int and just let the overflowing additions wrap 528 cdef long result_mon 529 cdef long c_hash 530 cdef long var_name_hash 531 cdef int i 532 for i from 0<= i <= self.degree(): 533 if i == 1: 534 # we delay the hashing until now to not waste it one a constant poly 535 var_name_hash = hash((<ParentWithGens>self._parent)._names[0]) 536 # I'm assuming (incorrectly) that hashes of zero indicate that the element is 0. 537 # This assumption is not true, but I think it is true enough for the purposes and it 538 # it allows us to write fast code that omits terms with 0 coefficients. This is 539 # important if we want to maintain the '==' relationship with sparse polys. 540 c_hash = hash(self[i]) 541 if c_hash != 0: 542 if i == 0: 543 result += c_hash 544 else: 545 # Hash (self[i], generator, i) as a tuple according to the algorithm. 546 result_mon = c_hash 547 result_mon = (1000003 * result_mon) ^ var_name_hash 548 result_mon = (1000003 * result_mon) ^ i 549 result += result_mon 550 if result == -1: 551 return -2 552 return result 553 504 554 def __float__(self): 505 555 if self.degree() > 0: … … 3385 3435 def __nonzero__(self): 3386 3436 return len(self.__coeffs) > 0 3387 3388 def __hash__(self): 3389 if len(self.__coeffs) > 1: 3390 return hash(tuple(self.__coeffs)) 3391 elif len(self.__coeffs) == 1: 3392 return hash(self[0]) 3393 else: 3394 return 0 3395 3437 3396 3438 cdef void __normalize(self): 3397 3439 x = self.__coeffs … … 3401 3443 del x[n] 3402 3444 n -= 1 3403 3445 3446 # you may have to replicate this boilerplate code in derived classes if you override 3447 # __richcmp__. The python documentation at http://docs.python.org/api/type-structs.html 3448 # explains how __richcmp__, __hash__, and __cmp__ are tied together. 3449 def __hash__(self): 3450 return self._hash_c() 3451 3404 3452 def __richcmp__(left, right, int op): 3405 3453 return (<Element>left)._richcmp(right, op) -
sage/rings/polynomial/polynomial_element.pyx
r7513 r7514 36 36 import sage.rings.complex_field 37 37 import sage.rings.fraction_field_element 38 from sage.rings.infinity importinfinity38 import sage.rings.infinity as infinity 39 39 #import sage.misc.misc as misc 40 40 from sage.misc.sage_eval import sage_eval … … 75 75 76 76 cdef object is_AlgebraicRealField 77 cdef object is_AlgebraicField 78 cdef object is_AlgebraicField_common 79 cdef object NumberField_quadratic 80 cdef object is_ComplexIntervalField 77 81 78 82 cdef void late_import(): 79 83 # A hack to avoid circular imports. 80 84 global is_AlgebraicRealField 85 global is_AlgebraicField 86 global is_AlgebraicField_common 87 global NumberField_quadratic 88 global is_ComplexIntervalField 81 89 82 90 if is_AlgebraicRealField is not None: 83 91 return 84 92 85 import sage.rings.algebraic_real 86 is_AlgebraicRealField = sage.rings.algebraic_real.is_AlgebraicRealField 93 import sage.rings.qqbar 94 is_AlgebraicRealField = sage.rings.qqbar.is_AlgebraicRealField 95 is_AlgebraicField = sage.rings.qqbar.is_AlgebraicField 96 is_AlgebraicField_common = sage.rings.qqbar.is_AlgebraicField_common 97 import sage.rings.number_field.number_field 98 NumberField_quadratic = sage.rings.number_field.number_field.NumberField_quadratic 99 import sage.rings.complex_interval_field 100 is_ComplexIntervalField = sage.rings.complex_interval_field.is_ComplexIntervalField 87 101 88 102 cdef class Polynomial(CommutativeAlgebraElement): … … 575 589 576 590 def _integer_(self): 591 r""" 592 EXAMPLES: 593 sage: k = GF(47) 594 sage: R.<x> = PolynomialRing(k) 595 sage: ZZ(R(45)) 596 45 597 sage: ZZ(3*x + 45) 598 Traceback (most recent call last): 599 ... 600 TypeError: cannot coerce nonconstant polynomial 601 """ 577 602 if self.degree() > 0: 578 603 raise TypeError, "cannot coerce nonconstant polynomial" 579 604 return sage.rings.integer.Integer(self[0]) 605 606 def _rational_(self): 607 r""" 608 EXAMPLES: 609 sage: R.<x> = PolynomialRing(QQ) 610 sage: QQ(R(45/4)) 611 45/4 612 sage: QQ(3*x + 45) 613 Traceback (most recent call last): 614 ... 615 TypeError: cannot coerce nonconstant polynomial 616 """ 617 if self.degree() > 0: 618 raise TypeError, "cannot coerce nonconstant polynomial" 619 return sage.rings.rational.Rational(self[0]) 580 620 581 621 def __invert__(self): … … 1092 1132 sage: f = y^10 - 1.393493*y + 0.3 1093 1133 sage: f._mul_karatsuba(f) 1094 1.00000000000000*y^20 - 2.78698600000000*y^11 + 0.600000000000000*y^10 + 0.000000000000000111022302462516*y^8 - 0.000000000000000111022302462516*y^6 - 0.000000000000000111022302462516*y^3 + 1.94182274104900*y^2 - 0.836095800000000*y + 0.09000000000000001134 1.00000000000000*y^20 - 2.78698600000000*y^11 + 0.600000000000000*y^10 + 1.11022302462516e-16*y^8 - 1.11022302462516e-16*y^6 - 1.11022302462516e-16*y^3 + 1.94182274104900*y^2 - 0.836095800000000*y + 0.0900000000000000 1095 1135 sage: f._mul_fateman(f) 1096 1136 1.00000000000000*y^20 - 2.78698600000000*y^11 + 0.600000000000000*y^10 + 1.94182274104900*y^2 - 0.836095800000000*y + 0.0900000000000000 … … 1533 1573 sage: expand(F) 1534 1574 T^6 + 10/7*T^5 + (-867/49)*T^4 + (-76/245)*T^3 + 3148/35*T^2 + (-25944/245)*T + 48771/1225 1575 1576 sage: f = x^2 - 1/3 ; K.<a> = NumberField(f) ; A.<T> = K[] ; g = A(x^2-1) 1577 sage: g.factor() 1578 (T - 1) * (T + 1) 1579 1580 sage: h = A(3*x^2-1) ; h.factor() 1581 (3) * (T - a) * (T + a) 1582 1583 sage: h = A(x^2-1/3) ; h.factor() 1584 (T - a) * (T + a) 1535 1585 1536 1586 Over the real double field: … … 1603 1653 G = None 1604 1654 1605 from sage.rings.number_field.all import is_NumberField, is_RelativeNumberField 1655 from sage.rings.number_field.all import is_NumberField, \ 1656 is_RelativeNumberField, NumberField 1606 1657 from sage.rings.finite_field import is_FiniteField 1607 1658 … … 1626 1677 return Factorization(v, from_M(F.unit())) 1627 1678 1628 1629 elif is_NumberField(R) or is_FiniteField(R): 1679 elif is_FiniteField(R): 1630 1680 v = [x._pari_("a") for x in self.list()] 1631 1681 f = pari(v).Polrev() 1632 1682 G = list(f.factor()) 1683 1684 1685 elif is_NumberField(R): 1686 if (R.defining_polynomial().denominator() == 1): 1687 1688 if (self.leading_coefficient() == 1): 1689 unit = None 1690 v = [ x._pari_("a") for x in self.list() ] 1691 else: 1692 unit = self.leading_coefficient() 1693 temp_f = self * 1/unit 1694 v = [ x._pari_("a") for x in temp_f.list() ] 1695 f = pari(v).Polrev() 1696 Rpari = R.pari_nf() 1697 if (Rpari.variable() != "a"): 1698 Rpari = Rpari.copy() 1699 Rpari[0] = Rpari[0]("a") 1700 Rpari[6] = [ x("a") for x in Rpari[6] ] 1701 G = list(Rpari.nffactor(f)) 1702 return self._factor_pari_helper(G, unit=unit) 1703 1704 else: 1705 1706 Rdenom = R.defining_polynomial().denominator() 1707 1708 new_Rpoly = (R.defining_polynomial() * Rdenom).change_variable_name("a") 1709 1710 Rpari, Rdiff = new_Rpoly._pari_().nfinit(3) 1711 1712 AZ = polynomial_ring.PolynomialRing(QQ,'z') 1713 Raux = NumberField(AZ(Rpari[0]),'alpha') 1714 1715 S, gSRaux, fRauxS = Raux.change_generator(Raux(Rdiff)) 1716 1717 phi_RS = R.Hom(S)([S.gen(0)]) 1718 phi_SR = S.Hom(R)([R.gen(0)]) 1719 1720 unit = self.leading_coefficient() 1721 temp_f = self * 1/unit 1722 1723 v = [ gSRaux(phi_RS(x))._pari_("a") for x in temp_f.list() ] 1724 f = pari(v).Polrev() 1725 1726 pari_factors = Rpari.nffactor(f) 1727 1728 factors = [ ( self.parent([ phi_SR(fRauxS(Raux(pari_factors[0][i][j]))) 1729 for j in range(len(pari_factors[0][i])) ]) , 1730 int(pari_factors[1][i]) ) 1731 for i in range(pari_factors.nrows()) ] 1732 1733 return Factorization(factors, unit) 1734 1633 1735 1634 1736 elif is_RealField(R): … … 1959 2061 +Infinity 1960 2062 """ 1961 return infinity 2063 return infinity.infinity 1962 2064 1963 2065 def padded_list(self, n=None): … … 2345 2447 at the end of the docstring about this. 2346 2448 2347 If the output ring is a RealIntervalField of a given 2348 precision, then the answer will always be correct (or an 2349 exception will be raised, if a case is not implemented). Each 2350 root will be contained in one of the returned intervals, 2351 and the intervals will be disjoint. (The returned intervals 2352 may be of higher precision than the specified output ring.) 2449 If the output ring is a RealIntervalField or 2450 ComplexIntervalField of a given precision, then the answer 2451 will always be correct (or an exception will be raised, if a 2452 case is not implemented). Each root will be contained in one 2453 of the returned intervals, and the intervals will be disjoint. 2454 (The returned intervals may be of higher precision than the 2455 specified output ring.) 2353 2456 2354 2457 At the end of this docstring (after the examples) is a description … … 2362 2465 sage: f.roots() 2363 2466 [(1, 1)] 2364 sage: f.roots(ring=CC) 2365 [(1.00000000000000, 1), (-0.500000000000000 + 0.86602540378443 8*I, 1), (-0.500000000000000 - 0.866025403784438*I, 1)]2467 sage: f.roots(ring=CC) # note -- low order bits slightly different on ppc. 2468 [(1.00000000000000, 1), (-0.500000000000000 + 0.86602540378443...*I, 1), (-0.500000000000000 - 0.86602540378443...*I, 1)] 2366 2469 sage: f = (x^3 - 1)^2 2367 2470 sage: f.roots() … … 2420 2523 sage: f = x^10 - 2*(5*x-1)^2 2421 2524 sage: f.roots(multiplicities=False) 2422 [-1.6772670339941..., 0.19995479628 5..., 0.200045306115..., 1.5763035161844...]2525 [-1.6772670339941..., 0.19995479628..., 0.200045306115..., 1.5763035161844...] 2423 2526 2424 2527 sage: x = CC['x'].0 … … 2435 2538 [(I, 3), (-2^(1/4), 1), (2^(1/4), 1), (1, 1)] 2436 2539 2437 A n example where the base ring doesn't have a factorization2438 algorithm (yet). Note that this is currently done via naive2439 enumeration, so could be very slow:2540 A couple of examples where the base ring doesn't have a 2541 factorization algorithm (yet). Note that this is currently 2542 done via naive enumeration, so could be very slow: 2440 2543 sage: R = Integers(6) 2441 2544 sage: S.<x> = R['x'] … … 2447 2550 sage: p.roots(multiplicities=False) 2448 2551 [1, 5] 2552 sage: R = Integers(9) 2553 sage: A = PolynomialRing(R, 'y') 2554 sage: y = A.gen() 2555 sage: f = 10*y^2 - y^3 - 9 2556 sage: f.roots(multiplicities=False) 2557 [0, 1, 3, 6] 2449 2558 2450 2559 An example over the complex double field (where root finding … … 2506 2615 sage: f.roots(ring=RIF, multiplicities=False) 2507 2616 [[-0.618033988749894848204586834365642 .. -0.618033988749894848204586834365629], [0.999999999999999999999999999999987 .. 1.00000000000000000000000000000003], [1.61803398874989484820458683436561 .. 1.61803398874989484820458683436565]] 2617 2618 Examples using complex root isolation: 2619 sage: x = polygen(ZZ) 2620 sage: p = x^5 - x - 1 2621 sage: p.roots() 2622 [] 2623 sage: p.roots(ring=CIF) 2624 [([1.1673039782614185 .. 1.1673039782614188], 1), ([0.18123244446987518 .. 0.18123244446987558] + [1.0839541013177103 .. 1.0839541013177110]*I, 1), ([0.181232444469875... .. 0.1812324444698755...] - [1.083954101317710... .. 1.0839541013177110]*I, 1), ([-0.76488443360058489 .. -0.76488443360058455] + [0.35247154603172609 .. 0.35247154603172643]*I, 1), ([-0.76488443360058489 .. -0.76488443360058455] - [0.35247154603172609 .. 0.35247154603172643]*I, 1)] 2625 sage: p.roots(ring=ComplexIntervalField(200)) 2626 [([1.1673039782614186842560458998548421807205603715254890391400816 .. 1.1673039782614186842560458998548421807205603715254890391400829], 1), ([0.18123244446987538390180023778112063996871646618462304743773153 .. 0.18123244446987538390180023778112063996871646618462304743773341] + [1.0839541013177106684303444929807665742736402431551156543011306 .. 1.0839541013177106684303444929807665742736402431551156543011344]*I, 1), ([0.18123244446987538390180023778112063996871646618462304743773153 .. 0.18123244446987538390180023778112063996871646618462304743773341] - [1.0839541013177106684303444929807665742736402431551156543011306 .. 1.0839541013177106684303444929807665742736402431551156543011344]*I, 1), ([-0.76488443360058472602982318770854173032899665194736756700777454 .. -0.76488443360058472602982318770854173032899665194736756700777...] + [0.35247154603172624931794709140258105439420648082424733283769... .. 0.35247154603172624931794709140258105439420648082424733283769...]*I, 1), ([-0.76488443360058472602982318770854173032899665194736756700777454 .. -0.76488443360058472602982318770854173032899665194736756700777204] - [0.35247154603172624931794709140258105439420648082424733283769122 .. 0.35247154603172624931794709140258105439420648082424733283769341]*I, 1)] 2627 sage: rts = p.roots(ring=QQbar); rts 2628 [([1.1673039782614185 .. 1.1673039782614188], 1), ([0.18123244446987538 .. 0.18123244446987541] + [1.0839541013177105 .. 1.0839541013177108]*I, 1), ([0.18123244446987538 .. 0.18123244446987541] - [1.0839541013177105 .. 1.0839541013177108]*I, 1), ([-0.76488443360058478 .. -0.76488443360058466] + [0.35247154603172620 .. 0.35247154603172626]*I, 1), ([-0.76488443360058478 .. -0.76488443360058466] - [0.35247154603172620 .. 0.35247154603172626]*I, 1)] 2629 sage: p.roots(ring=AA) 2630 [([1.1673039782614185 .. 1.1673039782614188], 1)] 2631 sage: p = (x - rts[1][0])^2 * (x^2 + x + 1) 2632 sage: p.roots(ring=QQbar) 2633 [([-0.50000000000000012 .. -0.49999999999999994] + [0.86602540378443859 .. 0.86602540378443871]*I, 1), ([-0.50000000000000000 .. -0.50000000000000000] - [0.86602540378443859 .. 0.86602540378443871]*I, 1), ([0.18123244446987538 .. 0.18123244446987541] + [1.0839541013177105 .. 1.0839541013177108]*I, 2)] 2634 sage: p.roots(ring=CIF) 2635 [([-0.50000000000000012 .. -0.49999999999999994] + [0.86602540378443859 .. 0.86602540378443871]*I, 1), ([-0.50000000000000000 .. -0.50000000000000000] - [0.86602540378443859 .. 0.86602540378443871]*I, 1), ([0.18123244446987538 .. 0.18123244446987541] + [1.0839541013177105 .. 1.0839541013177108]*I, 2)] 2636 2637 Note that coefficients in a number field with defining polynomial 2638 x^2 + 1 are considered to be Gaussian rationals (with the generator 2639 mapping to +I), if you ask for complex roots. 2640 2641 sage: K.<im> = NumberField(x^2 + 1) 2642 sage: y = polygen(K) 2643 sage: p = y^4 - 2 - im 2644 sage: p.roots(ring=CC) 2645 [(-1.2146389322441... - 0.14142505258239...*I, 1), (-0.14142505258239... + 1.2146389322441...*I, 1), (0.14142505258239... - 1.2146389322441...*I, 1), (1.2146389322441... + 0.14142505258239...*I, 1)] 2646 sage: p = p^2 * (y^2 - 2) 2647 sage: p.roots(ring=CIF) 2648 [([-1.4142135623730952 .. -1.4142135623730949], 1), ([1.4142135623730949 .. 1.4142135623730952], 1), ([-1.2146389322441827 .. -1.2146389322441821] - [0.1414250525823937... .. 0.1414250525823939...]*I, 2), ([-0.14142505258239399 .. -0.14142505258239376] + [1.2146389322441821 .. 1.2146389322441827]*I, 2), ([0.14142505258239376 .. 0.14142505258239399] - [1.2146389322441821 .. 1.2146389322441827]*I, 2), ([1.2146389322441821 .. 1.2146389322441827] + [0.14142505258239376 .. 0.14142505258239399]*I, 2)] 2508 2649 2509 2650 There are many combinations of floating-point input and output … … 2537 2678 2538 2679 Note that we can find the roots of a polynomial with 2539 algebraic realcoefficients:2680 algebraic coefficients: 2540 2681 2541 2682 sage: rt2 = sqrt(AA(2)) … … 2553 2694 Algorithms used: 2554 2695 2555 For brevity, we will use RR to mean any RealField of any precision; 2556 similarly for CC and CIF. 2696 For brevity, we will use RR to mean any RealField of any 2697 precision; similarly for RIF, CC, and CIF. Since Sage has no 2698 specific implementation of Gaussian rationals (or of number 2699 fields with embedding, at all), when we refer to Gaussian 2700 rationals below we will accept any number field with defining 2701 polynomial x^2+1, mapping the field generator to +I. 2557 2702 2558 2703 We call the base ring of the polynomial K, and the ring given … … 2573 2718 this method gives.) 2574 2719 2575 If L is floating-point and K is not, then we attempt to 2576 change the polynomial ring to L (using .change_ring()) 2577 (or, if L is complex, to the corresponding real field). 2578 Then we use either Pari or numpy as specified above. 2720 If L is QQbar or CIF, and K is ZZ, QQ, AA, QQbar, or the 2721 Gaussian rationals, then the root isolation algorithm 2722 sage.rings.polynomial.complex_roots.complex_roots() is used. 2723 (You can call complex_roots() directly to get more control 2724 than this method gives.) 2725 2726 If L is AA and K is QQbar or the Gaussian rationals, then 2727 complex_roots() is used (as above) to find roots in QQbar, 2728 then these roots are filtered to select only the real roots. 2729 2730 If L is floating-point and K is not, then we attempt to change 2731 the polynomial ring to L (using .change_ring()) (or, if L is 2732 complex and K is not, to the corresponding real field). Then 2733 we use either Pari or numpy as specified above. 2579 2734 2580 2735 For all other cases where K is different than L, we just use 2581 2736 .change_ring(L) and proceed as below. 2582 2737 2583 The next method is to attempt to factor the polynomial. 2584 If this succeeds, then for every degree-one factor a*x+b, we 2585 add -b/a as a root. 2586 2587 If factoring over K is not implemented, and K is finite, then 2588 we find the roots by enumerating all elements of K and checking 2589 whether the polynomial evaluates to zero at that value. 2738 The next method, which is used if K is an integral domain, is 2739 to attempt to factor the polynomial. If this succeeds, then 2740 for every degree-one factor a*x+b, we add -b/a as a root (as 2741 long as this quotient is actually in the desired ring). 2742 2743 If factoring over K is not implemented (or K is not an 2744 integral domain), and K is finite, then we find the roots by 2745 enumerating all elements of K and checking whether the 2746 polynomial evaluates to zero at that value. 2590 2747 2591 2748 … … 2613 2770 if L is None: L = K 2614 2771 2772 late_import() 2773 2615 2774 input_fp = (is_RealField(K) 2616 2775 or is_ComplexField(K) … … 2625 2784 output_complex = (is_ComplexField(L) 2626 2785 or is_ComplexDoubleField(L)) 2786 input_gaussian = (isinstance(K, NumberField_quadratic) 2787 and list(K.polynomial()) == [1, 0, 1]) 2627 2788 2628 2789 if input_fp and output_fp: … … 2684 2845 return rts 2685 2846 2686 late_import() 2687 2688 if L != K or is_AlgebraicRealField(L): 2689 # So far, the only "special" implementation is for K exact 2690 # and L either AA or a real interval field. 2847 if L != K or is_AlgebraicField_common(L): 2848 # So far, the only "special" implementations are for real 2849 # and complex root isolation. 2691 2850 if (is_IntegerRing(K) or is_RationalField(K) 2692 2851 or is_AlgebraicRealField(K)) and \ … … 2719 2878 return [rt for (rt, mult) in rts] 2720 2879 2721 if output_fp and output_complex: 2880 if (is_IntegerRing(K) or is_RationalField(K) 2881 or is_AlgebraicField_common(K) or input_gaussian) and \ 2882 (is_ComplexIntervalField(L) or is_AlgebraicField_common(L)): 2883 2884 from sage.rings.polynomial.complex_roots import complex_roots 2885 2886 if is_ComplexIntervalField(L): 2887 rts = complex_roots(self, min_prec=L.prec()) 2888 elif is_AlgebraicField(L): 2889 rts = complex_roots(self, retval='algebraic') 2890 else: 2891 rts = complex_roots(self, retval='algebraic_real') 2892 2893 if multiplicities: 2894 return rts 2895 else: 2896 return [rt for (rt, mult) in rts] 2897 2898 if output_fp and output_complex and not input_gaussian: 2722 2899 # If we want the complex roots, and the input is not 2723 # floating point, we convert to a real polynomial. 2724 # I think this works for now, because there are no 2725 # non-floating-point complex types in Sage. Hopefully 2726 # someday we will have Gaussian integers and rationals, 2727 # and this will have to change then. 2900 # floating point, we convert to a real polynomial 2901 # (except when the input coefficients are Gaussian rationals). 2728 2902 if is_ComplexDoubleField(L): 2729 2903 real_field = RDF … … 2736 2910 2737 2911 try: 2738 rts = self.factor() 2912 if K.is_integral_domain(): 2913 rts = self.factor() 2914 else: 2915 raise NotImplementedError 2739 2916 except NotImplementedError: 2740 2917 if K.is_finite(): … … 2797 2974 EXAMPLES: 2798 2975 sage: x = polygen(ZZ) 2799 sage: (x^3 - 1).complex_roots() 2800 [1.00000000000000, -0.500000000000000 + 0.86602540378443 8*I, -0.500000000000000 - 0.866025403784438*I]2976 sage: (x^3 - 1).complex_roots() # note: low order bits slightly different on ppc. 2977 [1.00000000000000, -0.500000000000000 + 0.86602540378443...*I, -0.500000000000000 - 0.86602540378443...*I] 2801 2978 2802 2979 TESTS: … … 2870 3047 2871 3048 if not self: 2872 return infinity 2873 2874 if p is infinity :3049 return infinity.infinity 3050 3051 if p is infinity.infinity: 2875 3052 return -self.degree() 2876 3053 … … 2966 3143 sage: R(4).is_irreducible() 2967 3144 True 3145 3146 TESTS: 3147 sage: F.<t> = NumberField(x^2-5) 3148 sage: Fx.<xF> = PolynomialRing(F) 3149 sage: f = Fx([2*t - 5, 5*t - 10, 3*t - 6, -t, -t + 2, 1]) 3150 sage: f.is_irreducible() 3151 False 3152 sage: f = Fx([2*t - 3, 5*t - 10, 3*t - 6, -t, -t + 2, 1]) 3153 sage: f.is_irreducible() 3154 True 2968 3155 """ 2969 3156 if self.is_zero(): … … 3111 3298 3112 3299 coeffs = self.coeffs() 3113 if p == infinity :3300 if p == infinity.infinity: 3114 3301 return RR(max([abs(i) for i in coeffs])) 3115 3302 -
sage/rings/polynomial/polynomial_integer_dense_ntl.pyx
r7467 r7514 18 18 19 19 include "../../ext/stdsage.pxi" 20 21 20 22 21 from sage.rings.polynomial.polynomial_element cimport Polynomial … … 218 217 (self.parent(), self.list(), False, self.is_gen()) 219 218 220 221 219 def __getitem__(self, long n): 222 220 r""" -
sage/rings/polynomial/polynomial_integer_dense_ntl.pyx
r7513 r7514 315 315 def quo_rem(self, right): 316 316 r""" 317 Returns a tuple (quotient, remainder) where 318 self = quotient*other + remainder. 319 320 If the quotient and remainder are not integral, 321 an exception is raised. 322 317 Attempts to divide self by right, and return a quotient and remainder. 318 319 If right is monic, then it returns (q, r) where 320 self = q * right + r 321 and deg(r) < deg(right). 322 323 If right is not monic, then it returns (q, 0) where q = self/right 324 if right exactly divides self, otherwise it raises an exception. 325 323 326 EXAMPLES: 324 327 sage: R.<x> = PolynomialRing(ZZ) … … 329 332 sage: q*g + r == f 330 333 True 334 335 sage: f = x^2 336 sage: f.quo_rem(0) 337 Traceback (most recent call last): 338 ... 339 ArithmeticError: division by zero polynomial 340 341 sage: f = (x^2 + 3) * (2*x - 1) 342 sage: f.quo_rem(2*x - 1) 343 (x^2 + 3, 0) 344 345 sage: f = x^2 346 sage: f.quo_rem(2*x - 1) 347 Traceback (most recent call last): 348 ... 349 ArithmeticError: division not exact in Z[x] (consider coercing to Q[x] first) 350 331 351 """ 332 352 if not isinstance(right, Polynomial_integer_dense_ntl): … … 335 355 raise TypeError 336 356 337 # ugggh this isn't pretty. Lots of unnecessary copies. 338 cdef ZZX_c *r, *q 339 ZZX_quo_rem(&self.__poly, &(<Polynomial_integer_dense_ntl>right).__poly, &r, &q) 357 cdef Polynomial_integer_dense_ntl _right = <Polynomial_integer_dense_ntl> right 358 359 if ZZX_IsZero(_right.__poly): 360 raise ArithmeticError, "division by zero polynomial" 361 362 cdef ZZX_c *q, *r 363 cdef Polynomial_integer_dense_ntl qq = self._new() 340 364 cdef Polynomial_integer_dense_ntl rr = self._new() 341 cdef Polynomial_integer_dense_ntl qq = self._new() 342 rr.__poly = r[0] 343 qq.__poly = q[0] 344 ZZX_delete(&r[0]) 345 ZZX_delete(&q[0]) 346 return (qq, rr) 365 cdef int divisible 366 367 if ZZ_IsOne(ZZX_LeadCoeff(_right.__poly)): 368 # divisor is monic. Just do the division and remainder 369 ZZX_quo_rem(&self.__poly, &_right.__poly, &r, &q) 370 ZZX_swap(qq.__poly, q[0]) 371 ZZX_swap(rr.__poly, r[0]) 372 ZZX_delete(q) 373 ZZX_delete(r) 374 else: 375 # Non-monic divisor. Check whether it divides exactly. 376 q = ZZX_div(&self.__poly, &_right.__poly, &divisible) 377 if divisible: 378 # exactly divisible 379 ZZX_swap(q[0], qq.__poly) 380 ZZX_delete(q) 381 else: 382 # division failed: clean up and raise exception 383 ZZX_delete(q) 384 raise ArithmeticError, "division not exact in Z[x] (consider coercing to Q[x] first)" 385 386 return qq, rr 387 347 388 348 389
Note: See TracChangeset
for help on using the changeset viewer.
