# source:sage/rings/polynomial/polynomial_element.pyx@5476:bcc88b84dabf

Revision 5476:bcc88b84dabf, 77.8 KB checked in by Robert Bradshaw <robertwb@…>, 6 years ago (diff)

action model, most doctests pass

Line
1"""
2Univariate Polynomial Base Class
3
4AUTHORS:
5    -- William Stein: first version
6    -- Martin Albrecht: Added singular coercion.
7    -- Robert Bradshaw: Move Polynomial_generic_dense to SageX
8
9TESTS:
10     sage: R.<x> = ZZ[]
11     sage: f = x^5 + 2*x^2 + (-1)
13     True
14
15"""
16
17################################################################################
18#       Copyright (C) 2007 William Stein <wstein@gmail.com>
19#
21#
23################################################################################
24
25import operator
26
27import copy
28
29import sage.rings.rational
30import sage.rings.integer
31import polynomial_ring
32import sage.rings.arith
33#import sage.rings.ring_element
34import sage.rings.integer_ring
35import sage.rings.rational_field
36import sage.rings.integer_mod_ring
37import sage.rings.complex_field
38import sage.rings.fraction_field_element
39from sage.rings.infinity import infinity
40#import sage.misc.misc as misc
41from sage.misc.sage_eval import sage_eval
42from sage.misc.latex import latex
43from sage.structure.factorization import Factorization
44
45from sage.interfaces.all import singular as singular_default, is_SingularElement
46from sage.libs.all import pari, pari_gen, PariError
47
48from sage.rings.real_mpfr import RealField, is_RealNumber, is_RealField
49RR = RealField()
50
51from sage.structure.element import RingElement
52from sage.structure.element cimport Element, RingElement, ModuleElement, MonoidElement
53
54from sage.rings.rational_field import QQ
55from sage.rings.integer_ring import ZZ
56
57from sage.rings.integral_domain import is_IntegralDomain
58
59
60import polynomial_fateman
61
62def is_Polynomial(f):
63    return PY_TYPE_CHECK(f, Polynomial)
64
65from polynomial_compiled cimport CompiledPolynomialFunction
66
67cdef class Polynomial(CommutativeAlgebraElement):
68    """
69    A polynomial.
70
71    EXAMPLE:
72        sage: R.<y> = QQ['y']
73        sage: S.<x> = R['x']
74        sage: f = x*y; f
75        y*x
76        sage: type(f)
77        <type 'sage.rings.polynomial.polynomial_element.Polynomial_generic_dense'>
78    """
79    def __init__(self, parent, is_gen = False, construct=False):
80        """
81        The following examples illustrate creation of elements of
82        polynomial rings, and some basic arithmetic.
83
84        First we make a polynomial over the integers and do some arithmetic:
85            sage: R.<x> = ZZ[]
86            sage: f = x^5 + 2*x^2 + (-1); f
87            x^5 + 2*x^2 - 1
88            sage: f^2
89            x^10 + 4*x^7 - 2*x^5 + 4*x^4 - 4*x^2 + 1
90
91        Next we do arithmetic in a sparse polynomial ring over the integers:
92            sage: R.<x> = ZZ[ ]; R
93            Univariate Polynomial Ring in x over Integer Ring
94            sage: S.<Z> = R[ ]; S
95            Univariate Polynomial Ring in Z over Univariate Polynomial Ring in x over Integer Ring
96            sage: f = Z^3 + (x^2-2*x+1)*Z - 3; f
97            Z^3 + (x^2 - 2*x + 1)*Z + -3
98            sage: f*f
99            Z^6 + (2*x^2 - 4*x + 2)*Z^4 + (-6)*Z^3 + (x^4 - 4*x^3 + 6*x^2 - 4*x + 1)*Z^2 + (-6*x^2 + 12*x - 6)*Z + 9
100            sage: f^3 == f*f*f
101            True
102        """
103        CommutativeAlgebraElement.__init__(self, parent)
104        self._is_gen = is_gen
105
106    cdef ModuleElement _add_c_impl(self, ModuleElement right):
107        cdef Py_ssize_t i, min
108        x = self.list()
109        y = right.list()
110
111        if len(x) > len(y):
112            min = len(y)
113            high = x[min:]
114        elif len(x) < len(y):
115            min = len(x)
116            high = y[min:]
117        else:
118            min = len(x)
119            high = []
120
121        low = [x[i] + y[i] for i from 0 <= i < min]
122        return self.polynomial(low + high)
123
124    cdef ModuleElement _neg_c_impl(self):
125        return self.polynomial([-x for x in self.list()])
126
127    def plot(self, xmin=0, xmax=1, *args, **kwds):
128        """
129        Return a plot of this polynomial.
130
131        INPUT:
132            xmin -- float
133            xmax -- float
134            *args, **kwds -- passed to either point or point
135
136        OUTPUT:
137            returns a graphic object.
138
139        EXAMPLES:
140            sage: x = polygen(GF(389))
141            sage: plot(x^2 + 1, rgbcolor=(0,0,1)).save()
142            sage: x = polygen(QQ)
143            sage: plot(x^2 + 1, rgbcolor=(1,0,0)).save()
144        """
145        R = self.base_ring()
146        from sage.plot.plot import plot, point, line
147        if R.characteristic() == 0:
148            return plot(self.__call__, xmin=xmin, xmax=xmax, *args, **kwds)
149        else:
150            if R.is_finite():
151                v = list(R)
152                v.sort()
153                w = dict([(v[i],i) for i in range(len(v))])
154                z = [(i, w[self(v[i])]) for i in range(len(v))]
155                return point(z, *args, **kwds)
156        raise NotImplementedError, "plotting of polynomials over %s not implemented"%R
157
158    def _lmul_(self, left):
159        """
160        Multiply self on the left by a scalar.
161
162        EXAMPLE:
163            sage: R.<x> = ZZ[]
164            sage: f = (x^3 + x + 5)
165            sage: f._lmul_(7)
166            7*x^3 + 7*x + 35
167            sage: 7*f
168            7*x^3 + 7*x + 35
169        """
170        # todo -- should multiply individual coefficients??
171        #         that could be in derived class.
172        #         Note that we are guaranteed that right is in the base ring, so this could be fast.
173        if left == 0:
174            return self.parent()(0)
175        return self.parent()(left) * self
176
177    def _rmul_(self, right):
178        """
179        Multiply self on the right by a scalar.
180
181        EXAMPLE:
182            sage: R.<x> = ZZ[]
183            sage: f = (x^3 + x + 5)
184            sage: f._rmul_(7)
185            7*x^3 + 7*x + 35
186            sage: f*7
187            7*x^3 + 7*x + 35
188        """
189        # todo -- Should multiply individual coefficients??
190        #         that could be in derived class.
191        #         Note that we are guaranteed that right is in the base ring, so this could be fast.
192        if right == 0:
193            return self.parent()(0)
194        return self * self.parent()(right)
195
196    def __call__(self, *x):
197        """
198        Evaluate polynomial at x=a using Horner's rule
199
200        INPUT:
201            a -- ring element a; need not be in the coefficient
202                 ring of the polynomial.
203
204        OUTPUT:
205            the value of f at a.
206
207        EXAMPLES:
208            sage: R.<x> = QQ[]
209            sage: f = x/2 - 5
210            sage: f(3)
211            -7/2
212            sage: R.<x> = ZZ[]
213            sage: f = (x-1)^5
214            sage: f(2/3)
215            -1/243
216
217        We evaluate a polynomial over a quaternion algebra:
218            sage: A.<i,j,k> = QuaternionAlgebra(QQ, -1,-1)
219            sage: R.<w> = PolynomialRing(A,sparse=True)
220            sage: f = i*j*w^5 - 13*i*w^2 + (i+j)*w + i
221            sage: f(i+j+1)
222            24 + 26*i - 10*j - 25*k
223            sage: w = i+j+1; i*j*w^5 - 13*i*w^2 + (i+j)*w + i
224            24 + 26*i - 10*j - 25*k
225
226        The parent ring of the answer always "starts" with the parent
227        of the object at which we are evaluating.  Thus, e.g., if
228        we input a matrix, we are guaranteed to get a matrix out,
229        though the base ring of that matrix may change depending on
230        the base of the polynomial ring.
231            sage: R.<x> = QQ[]
232            sage: f = R(2/3)
233            sage: a = matrix(ZZ,2)
234            sage: b = f(a); b
235            [2/3   0]
236            [  0 2/3]
237            sage: b.parent()
238            Full MatrixSpace of 2 by 2 dense matrices over Rational Field
239            sage: f = R(1)
240            sage: b = f(a); b
241            [1 0]
242            [0 1]
243            sage: b.parent()
244            Full MatrixSpace of 2 by 2 dense matrices over Rational Field
245
246        Nested polynomial ring elements can be called like multi-variate polynomials.
247            sage: R.<x> = QQ[]
248            sage: S.<y> = R[]
249            sage: f = x+y*x+y^2
250            sage: f.parent()
251            Univariate Polynomial Ring in y over Univariate Polynomial Ring in x over Rational Field
252            sage: f(2)
253            3*x + 4
254            sage: f(2,4)
255            16
256            sage: R.<t> = PowerSeriesRing(QQ, 't'); S.<x> = R[]
257            sage: f = 1 + x*t^2 + 3*x*t^4
258            sage: f(2)
259            1 + 2*t^2 + 6*t^4
260            sage: f(2, 1/2)
261            15/8
262
263        AUTHORS:
264            -- David Joyner, 2005-04-10
265            -- William Stein, 2006-01-22; change so parent
266               is determined by the arithmetic
267            -- William Stein, 2007-03-24: fix parent being determined in the constant case!
269            -- Tom Boothby, 2007-05-01: evaluation done by CompiledPolynomialFunction
270        """
271        if isinstance(x[0], tuple):
272            x = x[0]
273        a = x[0]
274        cdef long i, d = self.degree()
275
276        result = self[d]
277        if len(x) > 1:
278            other_args = x[1:]
279            if hasattr(result, '__call__'):
280                result = result(other_args)
281            else:
282                raise TypeError, "Wrong number of arguments"
283
284        if d == 0:
285            try:
286                return a.parent()(1) * result
287            except AttributeError:
288                return result
289
290        i = d - 1
291        if len(x) > 1:
292            while i >= 0:
293                result = result * a + self[i](other_args)
294                i -= 1
295        elif 1 or d < 4 and self._compiled is None:
296            while i >= 0:
297                result = result * a + self[i]
298                i -= 1
299        else:
300            if self._compiled is None:
301                self._compiled = CompiledPolynomialFunction(self.list())
302            result = self._compiled.eval(a)
303        return result
304
305    def _compile(self):
306        # For testing
307        self._compiled = CompiledPolynomialFunction(self.list())
308        return self._compiled
309
310    cdef int _cmp_c_impl(self, Element other) except -2:
311        """
312        Compare the two polynomials self and other.
313
314        We order polynomials first by degree, then in dictionary order
315        starting with the coefficient of largest degree.
316
317        EXAMPLES:
318            sage: R.<x> = QQ['x']
319            sage: 3*x^3  + 5 > 10*x^2 + 19
320            True
321            sage: x^2 - 2*x - 1 < x^2 - 1
322            True
323            sage: x^2 - 2*x - 1 > x^2 - 1
324            False
325            sage: R(-1) < 0
326            False
327            sage: x^3 - 3 > 393939393
328            True
329        """
330        d1 = self.degree(); d2 = other.degree()
331        c = cmp(d1, d2)
332        if c: return c
333        for i in reversed(xrange(d1+1)):
334            c = cmp(self[i], other[i])
335            if c: return c
336        return 0
337
338    def __richcmp__(left, right, int op):
339        return (<Element>left)._richcmp(right, op)
340
341    def __nonzero__(self):
342        """
343        EXAMPLES:
344            sage: P = PolynomialRing(ZZ,'x')(0)
345            sage: bool(P)
346            False
347            sage: P = PolynomialRing(ZZ, 'x')([1,2,3])
348            sage: bool(P)
349            True
350        """
351        return self.degree() >= 0
352
353    def __getitem__(self, n):
354        raise NotImplementedError
355
356    def __iter__(self):
357        return iter(self.list())
358
359    def __hash__(self):
360        if self.degree() >= 1:
361            return hash(tuple(self.list()))
362        else:
363            return hash(self[0])
364
365    def __float__(self):
366         if self.degree() > 0:
367             raise TypeError, "cannot coerce nonconstant polynomial to float"
368         return float(self[0])
369
370    def __int__(self):
371        if self.degree() > 0:
372            raise TypeError, "cannot coerce nonconstant polynomial to int"
373        return int(self[0])
374
375    def _im_gens_(self, codomain, im_gens):
376        """
377        EXAMPLES:
378            sage: R.<x> = ZZ[]
379            sage: H = Hom(R, QQ); H
380            Set of Homomorphisms from Univariate Polynomial Ring in x over Integer Ring to Rational Field
381            sage: f = H([5]); f
382            Ring morphism:
383              From: Univariate Polynomial Ring in x over Integer Ring
384              To:   Rational Field
385              Defn: x |--> 5
386            sage: f(x)
387            5
388            sage: f(x^2 + 3)
389            28
390        """
391        a = im_gens[0]
392        P = a.parent()
393        d = self.degree()
394        result = P._coerce_(self[d])
395        i = d - 1
396        while i >= 0:
397            result = result * a + P._coerce_(self[i])
398            i -= 1
399        return result
400
401    def _integer_(self):
402        if self.degree() > 0:
403            raise TypeError, "cannot coerce nonconstant polynomial"
404        return sage.rings.integer.Integer(self[0])
405
406    def __invert__(self):
407        """
408        EXAMPLES:
409            sage: R.<x> = QQ[]
410            sage: f = x - 90283
411            sage: f.__invert__()
412            1/(x - 90283)
413            sage: ~f
414            1/(x - 90283)
415        """
416        return self.parent()(1)/self
417
418    def inverse_of_unit(self):
419        """
420        EXAMPLES:
421            sage: R.<x> = QQ[]
422            sage: f = x - 90283
423            sage: f.inverse_of_unit()
424            Traceback (most recent call last):
425            ...
426            ValueError: self is not a unit.
427            sage: f = R(-90283); g = f.inverse_of_unit(); g
428            -1/90283
429            sage: parent(g)
430            Univariate Polynomial Ring in x over Rational Field
431        """
432        if self.degree() > 0:
433            if not self.is_unit():
434                raise ValueError, "self is not a unit."
435            else:
436                raise NotImplementedError, "polynomial inversion over non-integral domains not implemented"
437        return self.parent()(~(self[0]))
438
439    def inverse_mod(a, m):
440        """
441        Inverts the polynomial a with respect to m, or throw a
442        ValueError if no such inverse exists.
443
444        EXAMMPLES:
445            sage: S.<t> = QQ[]
446            sage: f = inverse_mod(t^2 + 1, t^3 + 1); f
447            -1/2*t^2 - 1/2*t + 1/2
448            sage: f * (t^2 + 1) % (t^3 + 1)
449            1
450            sage: f = t.inverse_mod((t+1)^7); f
451            -t^6 - 7*t^5 - 21*t^4 - 35*t^3 - 35*t^2 - 21*t - 7
452            sage: (f * t) + (t+1)^7
453            1
454
455        It also works over in-exact rings, but note that due to rounding
456        error the product is only guerenteed to be withing epsilon of the
457        constant polynomial 1.
458            sage: R.<x> = RDF[]
459            sage: f = inverse_mod(x^2 + 1, x^5 + x + 1); f
460            0.4*x^4 - 0.2*x^3 - 0.4*x^2 + 0.2*x + 0.8
461            sage: f * (x^2 + 1) % (x^5 + x + 1)
462            -5.55111512313e-17*x^3 - 5.55111512313e-17*x^2 - 5.55111512313e-17*x + 1.0
463            sage: f = inverse_mod(x^3 - x + 1, x - 2); f
464            0.142857142857
465            sage: f * (x^3 - x + 1) % (x - 2)
466            1.0
467
468        ALGORITHM:
469            Solve the system as + mt = 1, returning s as the inverse
470            of a mod m.
471
472            Uses the Euclidean algorithm for exact rings, and solves a
473            linear system for the coefficients of s and t for inexact rings
474            (as the Euclidean algorithm may not converge in that case).
475
476        AUTHOR:
478        """
479        if m.degree() == 1 and m[1].is_unit():
480            # a(x) mod (x-r) = a(r)
481            r = -m[0]
482            if not m[1].is_one():
483                r *= m.base_ring()(~m[1])
484            u = a(r)
485            if u.is_unit():
486                return a.parent()(~u)
487        if a.parent().is_exact():
488            # use xgcd
489            g, s, _ = a.xgcd(m)
490            if g == 1:
491                return s
492            elif g.is_unit():
493                return g.inverse_of_unit() * s
494            else:
495                raise ValueError, "Impossible inverse modulo"
496        else:
497            # xgcd may not converge for inexact rings.
498            # Instead solve for the coefficients of
499            # s (degree n-1) and t (degree n-2) in
500            #               as + mt = 1
501            # as a linear system.
502            from sage.matrix.constructor import matrix
503            from sage.modules.free_module_element import vector
504            a %= m
505            n = m.degree()
506            R = a.parent().base_ring()
507            M = matrix(R, 2*n-1)
508            # a_i s_j x^{i+j} terms
509            for i in range(n):
510                for j in range(n):
511                    M[i+j, j] = a[i]
512            # m_i t_j x^{i+j} terms
513            for i in range(n+1):
514                for j in range(n-1):
515                    M[i+j, j+n] = m[i]
516            v = vector(R, [R(1)] + [R(0)]*(2*n-2)) # the constant polynomial 1
517            if M.is_invertible():
518                x = ~M*v # there has to be a better way to solve
519                return a.parent()(list(x)[0:n])
520            else:
521                raise ValueError, "Impossible inverse modulo"
522
523
524    def __long__(self):
525        """
526        EXAMPLES:
527            sage: R.<x> = ZZ[]
528            sage: f = x - 902384
529            sage: long(f)
530            Traceback (most recent call last):
531            ...
532            TypeError: cannot coerce nonconstant polynomial to long
533            sage: long(R(939392920202))
534            939392920202L
535        """
536        if self.degree() > 0:
537            raise TypeError, "cannot coerce nonconstant polynomial to long"
538        return long(self[0])
539
540    cdef RingElement _mul_c_impl(self, RingElement right):
541        """
542        EXAMPLES:
543            sage: R.<x> = ZZ[]
544            sage: (x - 4)*(x^2 - 8*x + 16)
545            x^3 - 12*x^2 + 48*x - 64
546        """
547        if right == 0 or self == 0:
548            return self.polynomial(0)
549        return self._mul_karatsuba(right)
550
551    def square(self):
552        """
553        Returns the square of this polynomial.
554
555        TODO:
556          -- This is just a placeholder; for now it just uses ordinary
557          multiplication. But generally speaking, squaring is faster than
558          ordinary multiplication, and it's frequently used, so subclasses
559          may choose to provide a specialised squaring routine.
560
561          -- Perhaps this even belongs at a lower level? ring_element
562          or something?
563
564        AUTHOR:
565          -- David Harvey (2006-09-09)
566
567        """
568        return self * self
569
570    def __div__(self, right):
571        """
572        EXAMPLES:
573            sage: x = QQ['x'].0
574            sage: f = (x^3 + 5)/3; f
575            1/3*x^3 + 5/3
576            sage: f.parent()
577            Univariate Polynomial Ring in x over Rational Field
578
579        If we do the same over $\ZZ$ the result is in the polynomial
580        ring over $\QQ$.
581
582            sage: x  = ZZ['x'].0
583            sage: f = (x^3 + 5)/3; f
584            1/3*x^3 + 5/3
585            sage: f.parent()
586            Univariate Polynomial Ring in x over Rational Field
587
588        Divides can make elements of the fraction field:
589
590            sage: R.<x> = QQ['x']
591            sage: f = x^3 + 5
592            sage: g = R(3)
593            sage: h = f/g; h
594            1/3*x^3 + 5/3
595            sage: h.parent()
596            Fraction Field of Univariate Polynomial Ring in x over Rational Field
597
598        This is another example over a non-prime finite field
599        (submited by a student of Jon Hanke).  It illustrates
600        cancellation between the numerator and denominator
601        over a non-prime finite field.
602            sage: R.<x> = PolynomialRing(GF(5^2, 'a'), 'x')
603            sage: f = x^3 + 4*x
604            sage: f / (x - 1)
605            x^2 + x
606        """
607        try:
608            if not isinstance(right, Element) or right.parent() != self.parent():
609                R = self.parent().base_ring()
610                x = R(right)
611                return ~x * self
612        except (TypeError, ValueError, ZeroDivisionError):
613            pass
614        return RingElement.__div__(self, right)
615
616
617    def __pow__(self, right, dummy):
618        """
619        EXAMPLES:
620            sage: R.<x> = ZZ[]
621            sage: f = x - 1
622            sage: f._pow(3)
623            x^3 - 3*x^2 + 3*x - 1
624            sage: f^3
625            x^3 - 3*x^2 + 3*x - 1
626        """
627        if self.degree() <= 0:
628            return self.parent()(self[0]**right)
629        if right < 0:
630            return (~self)**(-right)
631        if (<Polynomial>self)._is_gen:   # special case x**n should be faster!
632            R = self.parent().base_ring()
633            v = [R(0)]*right + [R(1)]
634            return self.parent()(v, check=False)
635        return sage.rings.arith.generic_power(self, right, self.parent()(1))
636
637    def _pow(self, right):
638        # TODO: fit __pow__ into the arithmatic structure
639        if self.degree() <= 0:
640            return self.parent()(self[0]**right)
641        if right < 0:
642            return (~self)**(-right)
643        if (<Polynomial>self)._is_gen:   # special case x**n should be faster!
644            v = [0]*right + [1]
645            return self.parent()(v, check=True)
646        return sage.rings.arith.generic_power(self, right, self.parent()(1))
647
648    def _repr(self, name=None):
649        s = " "
650        m = self.degree() + 1
651        r = reversed(xrange(m))
652        if name is None:
653            name = self.parent().variable_name()
654        atomic_repr = self.parent().base_ring().is_atomic_repr()
655        coeffs = self.list()
656        for n in reversed(xrange(m)):
657            x = coeffs[n]
658            if x != 0:
659                if n != m-1:
660                    s += " + "
661                x = repr(x)
662                if not atomic_repr and n > 0 and (x.find("+") != -1 or x.find("-") != -1):
663                    x = "(%s)"%x
664                if n > 1:
665                    var = "*%s^%s"%(name,n)
666                elif n==1:
667                    var = "*%s"%name
668                else:
669                    var = ""
670                s += "%s%s"%(x,var)
671        if atomic_repr:
672            s = s.replace(" + -", " - ")
673        s = s.replace(" 1*"," ")
674        s = s.replace(" -1*", " -")
675        if s==" ":
676            return "0"
677        return s[1:]
678
679    def _repr_(self):
680        r"""
681        EXAMPLES:
682            sage: x = polygen(QQ)
683            sage: f = x^3+2/3*x^2 - 5/3
684            sage: f._repr_()
685            'x^3 + 2/3*x^2 - 5/3'
686            sage: f.rename('vaughn')
687            sage: f
688            vaughn
689        """
690        return self._repr()
691
692    def _latex_(self, name=None):
693        r"""
694        EXAMPLES:
695                        sage: x = polygen(QQ)
696            sage: latex(x^3+2/3*x^2 - 5/3)
697             x^{3} + \frac{2}{3}x^{2} - \frac{5}{3}
698        """
699        s = " "
700        m = self.degree() + 1
701        r = reversed(xrange(m))
702        if name is None:
703            name = self.parent().variable_name()
704        atomic_repr = self.parent().base_ring().is_atomic_repr()
705        coeffs = self.list()
706        for n in reversed(xrange(m)):
707            x = coeffs[n]
708            if x != 0:
709                if n != m-1:
710                    s += " + "
711                x = latex(x)
712                if not atomic_repr and n > 0 and (x.find("+") != -1 or x.find("-") != -1):
713                    x = "\\left(%s\\right)"%x
714                if n > 1:
715                    var = "|%s^{%s}"%(name,n)
716                elif n==1:
717                    var = "|%s"%name
718                else:
719                    var = ""
720                s += "%s%s"%(x,var)
721        if atomic_repr:
722            s = s.replace(" + -", " - ")
723        s = s.replace(" 1|"," ")
724        s = s.replace(" -1|", " -")
725        s = s.replace("|","")
726        if s==" ":
727            return "0"
728        return s[1:]
729
730
731    def __setitem__(self, n, value):
732        raise IndexError, "polynomials are immutable"
733
734
735    def __floordiv__(self,right):
736        """
737        Quotient of division of self by other.  This is denoted //.
738        """
739        Q, _ = self.quo_rem(right)
740        return Q
741
742    def div(self,right):
743        """
744        Quotient of division of self by other.
745        """
746        Q, _ = self.quo_rem(right)
747        return Q
748
749    def __mod__(self, other):
750        """
751        Remainder of division of self by other.
752        EXAMPLES:
753            sage: R.<x> = ZZ[]
754            sage: x % (x+1)
755            -1
756            sage: (x^3 + x - 1) % (x^2 - 1)
757            2*x - 1
758        """
759        _, R = self.quo_rem(other)
760        return R
761
762    def _is_atomic(self):
763        return self.degree() == self.valuation()
764
765    def _mul_generic(self, right):
766        if self is right:
767            return self._square_generic()
768        x = self.list()
769        y = right.list()
770        cdef Py_ssize_t i, k, start, end
771        cdef Py_ssize_t d1 = len(x)-1, d2 = len(y)-1
772        if d1 == -1:
773            return self
774        elif d2 == -1:
775            return right
776        elif d1 == 0:
777            c = x[0]
778            return self._parent([c*a for a in y])
779        elif d2 == 0:
780            c = y[0]
781            return self._parent([a*c for a in x])
782        coeffs = []
783        for k from 0 <= k <= d1+d2:
784            start = 0 if k <= d2 else k-d2 # max(0, k-d2)
785            end =   k if k <= d1 else d1    # min(k, d1)
786            sum = x[start] * y[k-start]
787            for i from start < i <= end:
788                sum += x[i] * y[k-i]
789            coeffs.append(sum)
790        return self._parent(coeffs)
791
792    def _square_generic(self):
793        x = self.list()
794        cdef Py_ssize_t i, j
795        cdef Py_ssize_t d = len(x)-1
796        zero = self._parent.base_ring()(0)
797        two = self._parent.base_ring()(2)
798        coeffs = [zero] * (2 * d + 1)
799        for i from 0 <= i <= d:
800            coeffs[2*i] = x[i] * x[i]
801            for j from 0 <= j < i:
802                coeffs[i+j] += two * x[i] * x[j]
803        return self._parent(coeffs)
804
805    def _mul_fateman(self, right):
806        r"""
807        Returns the product of two polynomials using Kronecker's trick
808        to do the multiplication.  This could be used used over a
809        generic base ring.
810
811        NOTES:
812        \begin{itemize}
813          \item Since this is implemented in interpreted Python, it
814                could be hugely sped up by reimplementing it in Pyrex.
815          \item Over the reals there is precision loss, at least in
816                the current implementation.
817        \end{itemize}
818
819        INPUT:
820           self -- Polynomial
821           right -- Polynomial (over same base ring as self)
822
823        OUTPUT: Polynomial
824           The product self*right.
825
826        ALGORITHM:
827        Based on a paper by R. Fateman
828
829          {\tt http://www.cs.berkeley.edu/~fateman/papers/polysbyGMP.pdf}
830
831        The idea is to encode dense univariate polynomials as big
832        integers, instead of sequences of coefficients. The paper
833        argues that because integer multiplication is so cheap, that
834        encoding 2 polynomials to big numbers and then decoding the
835        result might be faster than popular multiplication algorithms.
836        This seems true when the degree is larger than 200.
837
838        EXAMPLES:
839            sage: S.<y> = PolynomialRing(RR)
840            sage: f = y^10 - 1.393493*y + 0.3
841            sage: f._mul_karatsuba(f)
842            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.0900000000000000
843            sage: f._mul_fateman(f)
844            1.00000000000000*y^20 - 2.78698600000000*y^11 + 0.600000000000000*y^10 + 1.94182274104900*y^2 - 0.836095800000000*y + 0.0900000000000000
845
847
848        \begin{itemize}
849
850        \item Faster than Karatsuba over $\Q$ and $\Z$
851             (but much slower still than calling NTL's
852             optimized C++ implementation, which is the
853             default over $\Z$)
854
855        \item Potentially less complicated.
856
857        \end{itemize}
858
859        Drawbacks:
860        \begin{itemize}
861        \item Slower over R when the degree of both of polynomials is less
862              than 250 (roughly).
863        \item Over R, results may not be as accurate as the Karatsuba
864              case. This is because we represent coefficients of
865              polynomials over R as fractions, then convert them back to
866              floating-point numbers.
867        \end{itemize}
868
869        AUTHOR:
870           -- Didier Deshommes (2006-05-25)
871        """
872        return self.parent()(polynomial_fateman._mul_fateman_mul(self,right))
873
874    def _mul_karatsuba(self, right):
875        r"""
876        Returns the product of two polynomials using the Karatsuba
877        divide and conquer multiplication algorithm.  This is only
878        used over a generic base ring.  (Special libraries like NTL
879        are used, e.g., for the integers and rationals, which are much
880        faster.)
881
882        INPUT:
883           self: Polynomial
884           right: Polynomial (over same base ring as self)
885
886        OUTPUT: Polynomial
887           The product self*right.
888
889        ALGORITHM:
890           The basic idea is to use that
891           $$892 (aX + b) (cX + d) = acX^2 + ((a+b)(c+d)-ac-bd)X + bd 893$$
894           where ac=a*c and bd=b*d, which requires three
895           multiplications instead of the naive four.  (In my examples,
896           strangely just doing the above with four multiplications
897           does tend to speed things up noticeably.)
898           Given f and g of arbitrary degree bigger than one, let e
899           be min(deg(f),deg(g))/2.  Write
900           $$901 f = a X^e + b \text{ and } g = c X^e + d 902$$
903           and use the identity
904           $$905 (aX^e + b) (cX^e + d) = ac X^{2e} +((a+b)(c+d) - ac - bd)X^e + bd 906$$
907           to recursively compute $fg$.
908
909        TIMINGS:
910        On a Pentium M 1.8Ghz laptop:
911           f=R.random(1000,bound=100)
912           g=R.random(1000,bound=100)
913           time h=f._mul_karatsuba(g)
914           Time: 0.42 seconds
915           The naive multiplication algorithm takes 14.58 seconds.
916           In contrast, MAGMA does this sort of product almost
917           instantly, and can easily deal with degree 5000.  Basically
918           MAGMA is 100 times faster at polynomial multiplication.
919
920           Over Z using NTL, multiplying two polynomials constructed
921           using R.random(10000,bound=100) takes 0.10 seconds.  Using
922           MAGMA V2.11-10 the same takes 0.14 seconds.  So in this
923           case NTL is somewhat faster than MAGMA.
924
925           Over Q using PARI, multiplying two polynomials constructed
926           using R.random(10000,bound=100) takes 1.23 seconds.  Not
927           good!  TODO: use NTL polynomials over Z with a denominator
929
930        NOTES:
931         * Karatsuba multiplication of polynomials is also implemented in PARI in
932                src/basemath/polarit3.c
933         * The MAGMA documentation appears to give no information about how
934           polynomial multiplication is implemented.
935        """
936        return self._parent(do_karatsuba(self.list(), right.list()))
937
938    def base_ring(self):
939        """
940        Return the base ring of the parent of self.
941
942        EXAMPLES:
943            sage: R.<x> = ZZ[]
944            sage: x.base_ring()
945            Integer Ring
946            sage: (2*x+3).base_ring()
947            Integer Ring
948        """
949        return self.parent().base_ring()
950
951    def base_extend(self, R):
952        """
953        Return a copy of this polynomial but with coefficients in R, if there
954        is a natural map from coefficient ring of self to R.
955
956        EXAMPLES:
957            sage: R.<x> = QQ[]
958            sage: f = x^3 - 17*x + 3
959            sage: f.base_extend(GF(7))
960            Traceback (most recent call last):
961            ...
962            TypeError: no such base extension
963            sage: f.change_ring(GF(7))
964            x^3 + 4*x + 3
965        """
966        S = self.parent().base_extend(R)
967        return S(self)
968
969    def change_ring(self, R):
970        """
971        Return a copy of this polynomial but with coefficients in R, if at
972        all possible.
973
974        EXAMPLES:
975            sage: K.<z> = CyclotomicField(3)
976            sage: f = K.defining_polynomial()
977            sage: f.change_ring(GF(7))
978            x^2 + x + 1
979        """
980        S = self.parent().change_ring(R)
981        return S(self)
982
983    def __copy__(self):
984        """
985        Return a "copy" of self.  This is just self, since in SAGE polynomials are
986        immutable this just returns self again.
987
988        EXAMPLES:
989        We create the polynomial $f=x+3$, then note that the copy is just
990        the same polynomial again, which is fine since polynomials are immutable.
991
992            sage: x = ZZ['x'].0
993            sage: f = x + 3
994            sage: g = copy(f)
995            sage: g is f
996            True
997        """
998        return self
999
1000    def degree(self):
1001        """
1002        Return the degree of this polynomial.  The zero polynomial
1003        has degree -1.
1004
1005        EXAMPLES:
1006            sage: x = ZZ['x'].0
1007            sage: f = x^93 + 2*x + 1
1008            sage: f.degree()
1009            93
1010            sage: x = PolynomialRing(QQ, 'x', sparse=True).0
1011            sage: f = x^100000
1012            sage: f.degree()
1013            100000
1014
1015            sage: x = QQ['x'].0
1016            sage: f = 2006*x^2006 - x^2 + 3
1017            sage: f.degree()
1018            2006
1019            sage: f = 0*x
1020            sage: f.degree()
1021            -1
1022            sage: f = x + 33
1023            sage: f.degree()
1024            1
1025
1026        AUTHORS:
1027            -- Naqi Jaffery (2006-01-24): examples
1028        """
1029        raise NotImplementedError
1030
1031    def denominator(self):
1032        """
1033        Return the least common multiple of the denominators of
1034        the entries of self, when this makes sense, i.e., when the
1035        coefficients have a denominator function.
1036
1037        WARNING: This is not the denominator of the rational function
1038        defined by self, which would always be 1 since self is a polynomial.
1039
1040        EXAMPLES:
1041        First we compute the denominator of a polynomial with integer
1042        coefficients, which is of course 1.
1043            sage: R.<x> = ZZ[]
1044            sage: f = x^3 + 17*x + 1
1045            sage: f.denominator()
1046            1
1047
1048        Next we compute the denominator of a polynomial with rational coefficients.
1049            sage: R.<x> = PolynomialRing(QQ)
1050            sage: f = (1/17)*x^19 - (2/3)*x + 1/3; f
1051            1/17*x^19 - 2/3*x + 1/3
1052            sage: f.denominator()
1053            51
1054
1055        Finally, we try to compute the denominator of a polynomial with
1056        coefficients in the real numbers, which is a ring whose elements
1057        do not have a denominator method.
1058            sage: R.<x> = RR[]
1059            sage: f = x + RR('0.3'); f
1060            1.00000000000000*x + 0.300000000000000
1061            sage: f.denominator()
1062            Traceback (most recent call last):
1063            ...
1064            AttributeError: 'sage.rings.real_mpfr.RealNumber' object has no attribute 'denominator'
1065        """
1066        if self.degree() == -1:
1067            return 1
1068        R = self.base_ring()
1069        x = self.list()
1070        d = x[0].denominator()
1071        for y in x:
1072            d = d.lcm(y.denominator())
1073        return d
1074
1075    def derivative(self):
1076        if self.is_zero():
1077            return self
1078        cdef Py_ssize_t n, degree = self.degree()
1079        if degree == 0:
1080            return self.parent()(0)
1081        coeffs = self.list()
1082        return self.polynomial([n*coeffs[n] for n from 1 <= n <= degree])
1083
1084    def integral(self):
1085        try:
1086            return self.polynomial([0] + [self[n]/(n+1) for n in xrange(0,self.degree()+1)])
1087        except TypeError:
1088            raise ArithmeticError, "coefficients of integral cannot be coerced into the base ring"
1089
1090
1091    def dict(self):
1092        X = {}
1093        Y = self.list()
1094        for i in xrange(len(Y)):
1095            X[i] = Y[i]
1096        return X
1097
1098    def factor(self):
1099        r"""
1100        Return the factorization of self.
1101
1102        INPUT:
1103            a polynomial
1104
1105        OUTPUT:
1106            Factorization -- the factorization of self, which is
1107            a product of a unit with a product of powers of irreducible
1108            factors.
1109
1110        Over a field the irreducible factors are all monic.
1111
1112        EXAMPLES:
1113        We factor some polynomials over $\Q$.
1114            sage: x = QQ['x'].0
1115            sage: f = (x^3 - 1)^2
1116            sage: f.factor()
1117            (x - 1)^2 * (x^2 + x + 1)^2
1118
1119        Notice that over the field $\Q$ the irreducible factors are monic.
1120            sage: f = 10*x^5 - 1
1121            sage: f.factor()
1122            (10) * (x^5 - 1/10)
1123            sage: f = 10*x^5 - 10
1124            sage: f.factor()
1125            (10) * (x - 1) * (x^4 + x^3 + x^2 + x + 1)
1126
1127        Over $\Z$ the irreducible factors need not be monic:
1128            sage: x = ZZ['x'].0
1129            sage: f = 10*x^5 - 1
1130            sage: f.factor()
1131            10*x^5 - 1
1132
1133
1134        We factor a non-monic polynomial over the finite field $F_{25}$.
1135            sage: k.<a> = GF(25)
1136            sage: R.<x> = k[]
1137            sage: f = 2*x^10 + 2*x + 2*a
1138            sage: F = f.factor(); F
1139            (2) * (x + a + 2) * (x^2 + 3*x + 4*a + 4) * (x^2 + (a + 1)*x + a + 2) * (x^5 + (3*a + 4)*x^4 + (3*a + 3)*x^3 + 2*a*x^2 + (3*a + 1)*x + 3*a + 1)
1140
1141        Notice that the unit factor is included when we multiply $F$ back out.
1142            sage: expand(F)
1143            2*x^10 + 2*x + 2*a
1144
1145        Factorization also works even if the variable of the finite field is nefariously
1146        labeled "x".
1147            sage: x = GF(3^2, 'a')['x'].0
1148            sage: f = x^10 +7*x -13
1149            sage: G = f.factor(); G
1150            (x + a) * (x + 2*a + 1) * (x^4 + (a + 2)*x^3 + (2*a + 2)*x + 2) * (x^4 + 2*a*x^3 + (a + 1)*x + 2)
1151            sage: prod(G) == f
1152            True
1153
1154            sage: f.parent().base_ring()._assign_names(['a'])
1155            sage: f.factor()
1156            (x + a) * (x + 2*a + 1) * (x^4 + (a + 2)*x^3 + (2*a + 2)*x + 2) * (x^4 + 2*a*x^3 + (a + 1)*x + 2)
1157
1158            sage: k = GF(9,'x')    # purposely calling it x to test robustness
1159            sage: x = PolynomialRing(k,'x0').gen()
1160            sage: f = x^3 + x + 1
1161            sage: f.factor()
1162            (x0 + 2) * (x0 + x) * (x0 + 2*x + 1)
1163            sage: f = 0*x
1164            sage: f.factor()
1165            Traceback (most recent call last):
1166            ...
1167            ValueError: factorization of 0 not defined
1168
1169            sage: f = x^0
1170            sage: f.factor()
1171            1
1172
1173        Arbitrary precision real and complex factorization:
1174            sage: R.<x> = RealField(100)[]
1175            sage: F = factor(x^2-3); F
1176            (1.0000000000000000000000000000*x + 1.7320508075688772935274463415) * (1.0000000000000000000000000000*x - 1.7320508075688772935274463415)
1177            sage: expand(F)
1178            1.0000000000000000000000000000*x^2 - 3.0000000000000000000000000000
1179            sage: factor(x^2 + 1)
1180            1.0000000000000000000000000000*x^2 + 1.0000000000000000000000000000
1181            sage: C = ComplexField(100)
1182            sage: R.<x> = C[]
1183            sage: F = factor(x^2+3); F
1184            (1.0000000000000000000000000000*x + -1.7320508075688772935274463415*I) * (1.0000000000000000000000000000*x + 1.7320508075688772935274463415*I)
1185            sage: expand(F)
1186            1.0000000000000000000000000000*x^2 + 3.0000000000000000000000000000
1187            sage: factor(x^2+1)
1188            (1.0000000000000000000000000000*x + -1.0000000000000000000000000000*I) * (1.0000000000000000000000000000*x + 1.0000000000000000000000000000*I)
1189            sage: f = C.0 * (x^2 + 1) ; f
1190            1.0000000000000000000000000000*I*x^2 + 1.0000000000000000000000000000*I
1191            sage: F = factor(f); F
1192            (1.0000000000000000000000000000*I) * (1.0000000000000000000000000000*x + -1.0000000000000000000000000000*I) * (1.0000000000000000000000000000*x + 1.0000000000000000000000000000*I)
1193            sage: expand(F)
1194            1.0000000000000000000000000000*I*x^2 + 1.0000000000000000000000000000*I
1195
1196        Over a complicated number field:
1197            sage: x = polygen(QQ, 'x')
1198            sage: f = x^6 + 10/7*x^5 - 867/49*x^4 - 76/245*x^3 + 3148/35*x^2 - 25944/245*x + 48771/1225
1199            sage: K.<a> = NumberField(f)
1200            sage: S.<T> = K[]
1201            sage: ff = S(f); ff
1202            T^6 + 10/7*T^5 + (-867/49)*T^4 + (-76/245)*T^3 + 3148/35*T^2 + (-25944/245)*T + 48771/1225
1203            sage: F = ff.factor()
1204            sage: len(F)
1205            4
1206            sage: F[:2]
1207            [(T + -a, 1), (T + -40085763200/924556084127*a^5 - 145475769880/924556084127*a^4 + 527617096480/924556084127*a^3 + 1289745809920/924556084127*a^2 - 3227142391585/924556084127*a - 401502691578/924556084127, 1)]
1208            sage: expand(F)
1209            T^6 + 10/7*T^5 + (-867/49)*T^4 + (-76/245)*T^3 + 3148/35*T^2 + (-25944/245)*T + 48771/1225
1210        """
1211
1212        # PERFORMANCE NOTE:
1213        #     In many tests with SMALL degree PARI is substantially
1214        #     better than NTL.  (And magma is better yet.)  And the
1215        #     timing difference has nothing to do with moving Python
1216        #     data to NTL and back.
1217        #     For large degree ( > 1500) in the one test I tried, NTL was
1218        #     *much* better than MAGMA, and far better than PARI.  So probably
1219        #     NTL's implementation is asymptotically better.  I could use
1220        #     PARI for smaller degree over other rings besides Z, and use
1221        #     NTL in general.
1222
1223        R = self.parent().base_ring()
1224        if self.degree() < 0:
1225            raise ValueError, "factorization of 0 not defined"
1226        G = None
1227
1228        from sage.rings.number_field.all import is_NumberField
1229        from sage.rings.finite_field import is_FiniteField
1230
1231        n = None
1232        if sage.rings.integer_mod_ring.is_IntegerModRing(R) or \
1233              sage.rings.integer_ring.is_IntegerRing(R) or \
1234              sage.rings.rational_field.is_RationalField(R):
1235
1236            try:
1237                G = list(self._pari_('x').factor())
1238            except PariError:
1239                raise NotImplementedError
1240
1241        elif is_NumberField(R) or is_FiniteField(R):
1242
1243            v = [x._pari_("a") for x in self.list()]
1244            f = pari(v).Polrev()
1245            G = list(f.factor())
1246
1247        elif is_RealField(R):
1248            n = pari.set_real_precision(int(3.5*R.prec()) + 1)
1249            G = list(self._pari_('x').factor())
1250
1251        elif sage.rings.complex_field.is_ComplexField(R):
1252            # This is a hack to make the polynomial have complex coefficients, since
1253            # otherwise PARI will factor over RR.
1254            n = pari.set_real_precision(int(3.5*R.prec()) + 1)
1256                G = list((pari(R.gen())*self._pari_('x')).factor())
1257            else:
1258                G = self._pari_('x').factor()
1259
1261        #    G = list(self._pari_('x').factorpadic(R.prime(), R.prec()))
1262
1263        if G is None:
1264            raise NotImplementedError
1265
1266        return self._factor_pari_helper(G, n)
1267
1268    def _factor_pari_helper(self, G, n=None, unit=None):
1269        pols = G[0]
1270        exps = G[1]
1271        F = []
1272        R = self.parent()
1273        c = R.base_ring()(1)
1274        for i in xrange(len(pols)):
1275            f = R(pols[i])
1276            e = int(exps[i])
1277            if unit is None:
1279            F.append((f,e))
1280
1281        if unit is None:
1282
1284
1285        if not unit.is_unit():
1286
1287            F.append((R(unit), 1))
1288            unit = R.base_ring()(1)
1289
1290        elif R.base_ring().is_field():
1291            # When the base ring is a field we normalize
1292            # the irreducible factors so they have leading
1293            # coefficient 1.
1294            one = R.base_ring()(1)
1295            for i in range(len(F)):
1297                if c != 1:
1298                    unit *= c
1299                    F[i] = (F[i][0].monic(), F[i][1])
1300
1301        if not n is None:
1302            pari.set_real_precision(n)  # restore precision
1303        return Factorization(F, unit)
1304
1305    def _lcm(self, other):
1306        """
1307        Let f and g be two polynomials.  Then this function
1308        returns the monic least common multiple of f and g.
1309        """
1310        f = self*other
1311        g = self.gcd(other)
1312        q = f//g
1313        return ~(q.leading_coefficient())*q  # make monic  (~ is inverse in python)
1314
1315    def is_constant(self):
1316        return self.degree() <= 0
1317
1318    def root_field(self, names, check_irreducible=True):
1319        """
1320        Return the field generated by the roots of self.  The output
1321        is either a number field, relative number field, a quotient of
1322        a polynomial ring over a field, or the fraction field of the
1323        base ring.
1324
1325        EXAMPLES:
1326            sage: R.<x> = QQ['x']
1327            sage: f = x^3 + x + 17
1328            sage: f.root_field('a')
1329            Number Field in a with defining polynomial x^3 + x + 17
1330
1331            sage: R.<x> = QQ['x']
1332            sage: f = x - 3
1333            sage: f.root_field('b')
1334            Rational Field
1335
1336            sage: R.<x> = ZZ['x']
1337            sage: f = x^3 + x + 17
1338            sage: f.root_field('b')
1339            Number Field in b with defining polynomial x^3 + x + 17
1340
1341            sage: y = QQ['x'].0
1342            sage: L.<a> = NumberField(y^3-2)
1343            sage: R.<x> = L['x']
1344            sage: f = x^3 + x + 17
1345            sage: f.root_field('c')
1346            Extension by x^3 + x + 17 of the Number Field in a with defining polynomial x^3 - 2
1347
1348            sage: R.<x> = PolynomialRing(GF(9,'a'))
1349            sage: f = x^3 + x^2 + 8
1350            sage: K.<alpha> = f.root_field(); K
1351            Univariate Quotient Polynomial Ring in alpha over Finite Field in a of size 3^2 with modulus x^3 + x^2 + 2
1352            sage: alpha^2 + 1
1353            alpha^2 + 1
1354            sage: alpha^3 + alpha^2
1355            1
1356        """
1357        from sage.rings.number_field.number_field import is_NumberField, NumberField
1358
1359        R = self.base_ring()
1360        if not is_IntegralDomain(R):
1361            raise ValueError, "the base ring must be a domain"
1362
1363        if self.degree() <= 1:
1364            return R.fraction_field()
1365
1366        if sage.rings.integer_ring.is_IntegerRing(R):
1367            return NumberField(self, names)
1368
1369
1370        if sage.rings.rational_field.is_RationalField(R) or is_NumberField(R):
1371            return NumberField(self, names)
1372
1373        if check_irreducible and not self.is_irreducible():
1374            raise ValueError, "polynomial must be irreducible"
1375
1376        return polynomial_ring.PolynomialRing(R.fraction_field(),
1377                              self.parent().variable_name()).quotient(self, names)
1378
1379
1380    def constant_coefficient(self):
1381        return self[0]
1382
1383    def is_monic(self):
1384        """
1385        Returns True if this polynomial is monic.  The zero
1386        polynomial is by definition not monic.
1387
1388        EXAMPLES:
1389            sage: x = QQ['x'].0
1390            sage: f = x + 33
1391            sage: f.is_monic()
1392            True
1393            sage: f = 0*x
1394            sage: f.is_monic()
1395            False
1396            sage: f = 3*x^3 + x^4 + x^2
1397            sage: f.is_monic()
1398            True
1399            sage: f = 2*x^2 + x^3 + 56*x^5
1400            sage: f.is_monic()
1401            False
1402
1403        AUTHORS:
1404            -- Naqi Jaffery (2006-01-24): examples
1405        """
1406        return not self.is_zero() and self[self.degree()] == 1
1407
1408    def is_unit(self):
1409        r"""
1410        Return True if this polynomial is a unit.
1411
1412        EXAMPLES:
1413            sage: a = Integers(90384098234^3)
1414            sage: b = a(2*191*236607587)
1415            sage: b.is_nilpotent()
1416            True
1417            sage: R.<x> = a[]
1418            sage: f = 3 + b*x + b^2*x^2
1419            sage: f.is_unit()
1420            True
1421            sage: f = 3 + b*x + b^2*x^2 + 17*x^3
1422            sage: f.is_unit()
1423            False
1424
1425        EXERCISE (Atiyah-McDonald, Ch 1): Let $A[x]$ be a polynomial
1426        ring in one variable.  Then $f=\sum a_i x^i \in A[x]$ is a
1427        unit if and only if $a_0$ is a unit and $a_1,\ldots, a_n$ are
1428        nilpotent.
1429        """
1430        if self.degree() > 0:
1431            for i in range(1,self.degree()+1):
1432                if not self[i].is_nilpotent():
1433                    return False
1434        return self[0].is_unit()
1435
1436    def is_nilpotent(self):
1437        r"""
1438        Return True if this polynomial is nilpotent.
1439
1440        EXAMPLES:
1441            sage: R = Integers(12)
1442            sage: S.<x> = R[]
1443            sage: f = 5 + 6*x
1444            sage: f.is_nilpotent()
1445            False
1446            sage: f = 6 + 6*x^2
1447            sage: f.is_nilpotent()
1448            True
1449            sage: f^2
1450            0
1451
1452        EXERCISE (Atiyah-McDonald, Ch 1): Let $A[x]$ be a polynomial
1453        ring in one variable.  Then $f=\sum a_i x^i \in A[x]$ is
1454        nilpotent if and only if every $a_i$ is nilpotent.
1455        """
1456        for i in range(self.degree()+1):
1457            if not self[i].is_nilpotent():
1458                return False
1459        return True
1460
1461    def is_gen(self):
1462        return bool(self._is_gen)
1463
1465        return self[self.degree()]
1466
1467    def monic(self):
1468        """
1469        Return this polynomial divided by its leading coefficient.
1470        Does not change this polynomial.
1471
1472        EXAMPLES:
1473            sage: x = QQ['x'].0
1474            sage: f = 2*x^2 + x^3 + 56*x^5
1475            sage: f.monic()
1476            x^5 + 1/56*x^3 + 1/28*x^2
1477            sage: f = (1/4)*x^2 + 3*x + 1
1478            sage: f.monic()
1479            x^2 + 12*x + 4
1480
1481    The following happens because $f = 0$ cannot be made into a monic polynomial
1482            sage: f = 0*x
1483            sage: f.monic()
1484            Traceback (most recent call last):
1485            ...
1486            ZeroDivisionError: rational division by zero
1487
1488        Notice that the monic version of a polynomial over the
1489        integers is defined over the rationals.
1490            sage: x = ZZ['x'].0
1491            sage: f = 3*x^19 + x^2 - 37
1492            sage: g = f.monic(); g
1493            x^19 + 1/3*x^2 - 37/3
1494            sage: g.parent()
1495            Univariate Polynomial Ring in x over Rational Field
1496
1497
1498        AUTHORS:
1499            -- Naqi Jaffery (2006-01-24): examples
1500        """
1501        if self.is_monic():
1502            return self
1504        R = self.parent()
1505        if a.parent() != R.base_ring():
1506            S = R.base_extend(a.parent())
1507            return a*S(self)
1508        else:
1509            return a*self
1510
1511
1512    def list(self):
1513        """
1514        Return a new copy of the list of the underlying
1515        elements of self.
1516        """
1517        raise NotImplementedError
1518
1519    def coeffs(self):
1520        r"""
1521        Returns \code{self.list()}.
1522
1523        (It potentially slightly faster better to use
1524        \code{self.list()} directly.)
1525
1526        EXAMPLES:
1527            sage: x = QQ['x'].0
1528            sage: f = 10*x^3 + 5*x + 2/17
1529            sage: f.coeffs()
1530            [2/17, 5, 0, 10]
1531        """
1532        return self.list()
1533
1534    def newton_raphson(self, n, x0):
1535        """
1536        Return a list of n iterative approximations to a root of this
1537        polynomial, computed using the Newton-Raphson method.
1538
1539        The Newton-Raphson method is an iterative root-finding algorithm.
1540        For f(x) a polynomial, as is the case here, this is essentially
1541        the same as Horner's method.
1542
1543        INPUT:
1544           n -- an integer (=the number of iterations),
1545           x0 -- an initial guess x0.
1546
1547        OUTPUT:
1548           A list of numbers hopefully approximating a root of f(x)=0.
1549
1550           ** If one of the iterates is a critical point of f then
1551              a ZeroDivisionError exception is raised.
1552
1553        EXAMPLES:
1554            sage: x = PolynomialRing(RealField(), 'x').gen()
1555            sage: f = x^2 - 2
1556            sage: f.newton_raphson(4, 1)
1557            [1.50000000000000, 1.41666666666667, 1.41421568627451, 1.41421356237469]
1558
1559        AUTHORS: David Joyner and William Stein (2005-11-28)
1560        """
1561        n = sage.rings.integer.Integer(n)
1562        df = self.derivative()
1563        K = self.parent().base_ring()
1564        a = K(x0)
1565        L = []
1566        for i in range(n):
1567            a -= self(a) / df(a)
1568            L.append(a)
1569        return L
1570
1571    def polynomial(self, *args, **kwds):
1572        return self._parent(*args, **kwds)
1573
1574    def newton_slopes(self, p):
1575        """
1576        Return the $p$-adic slopes of the Newton polygon of self,
1577        when this makes sense.
1578
1579        OUTPUT:
1580            -- list of rational numbers
1581
1582        EXAMPLES:
1583            sage: x = QQ['x'].0
1584            sage: f = x^3 + 2
1585            sage: f.newton_slopes(2)
1586            [1/3, 1/3, 1/3]
1587
1588        ALGORITHM: Uses PARI.
1589        """
1590        f = self._pari_()
1591        v = list(f.newtonpoly(p))
1592        return [sage.rings.rational.Rational(x) for x in v]
1593
1594
1595    #####################################################################
1596    # Conversions to other systems
1597    #####################################################################
1598    def _pari_(self, variable=None):
1599        """
1600        Return polynomial as a PARI object.
1601
1602        EXAMPLES:
1603            sage: f = PolynomialRing(QQ, 'X')([0,1,2/3,3])
1604            sage: pari(f)
1605            3*X^3 + 2/3*X^2 + X
1606        """
1607        try:
1608            return self.__pari
1609        except AttributeError:
1610            K = self.base_ring()
1611            n = None
1612            if is_RealField(K) or sage.rings.complex_field.is_ComplexField(K):
1613                n = pari.get_real_precision()
1614                pari.set_real_precision(int(K.prec()*3.5)+1)
1615            v = self.list()
1616            try:
1617                v = [x._pari_() for x in v]
1618            except AttributeError:
1619                pass
1620            if variable is None:
1621                variable = self.parent().variable_name()
1622            self.__pari = pari(v).Polrev(variable)
1623            if not n is None:
1624                pari.set_real_precision(n)
1625            return self.__pari
1626
1627    def _pari_init_(self):
1628        return repr(self._pari_())
1629
1630    def _magma_init_(self):
1631        """
1632        Return a string that evaluates in Magma to this polynomial.
1633
1634        EXAMPLES:
1635            sage: R.<y> = ZZ[]
1636            sage: f = y^3 - 17*y + 5
1637            sage: f._magma_init_()
1638            'Polynomial(IntegerRing(), [5,-17,0,1])'
1639        """
1640        return 'Polynomial(%s, [%s])'%(self.base_ring()._magma_init_(), ','.join([a._magma_init_() for a in self.list()]))
1641
1642    def _magma_(self, G=None):
1643        """
1644        Return the Magma version of this polynomial.
1645
1646        EXAMPLES:
1647            sage: R.<y> = ZZ[]
1648            sage: f = y^3 - 17*y + 5
1649            sage: g = magma(f); g              # optional -- requires Magma
1650            y^3 - 17*y + 5
1651
1652        Note that in Magma there is only one polynomial ring over each base,
1653        so if we make the polynomial ring over ZZ with variable $z$, then
1654        this changes the variable name of the polynomial we already defined:
1655            sage: R.<z> = ZZ[]
1656            sage: magma(R)                     # optional -- requires Magma
1657            Univariate Polynomial Ring in z over Integer Ring
1658            sage: g                            # optional -- requires Magma
1659            z^3 - 17*z + 5
1660
1661        In SAGE the variable name does not change:
1662            sage: f
1663            y^3 - 17*y + 5
1664        """
1665        if G is None:
1666            import sage.interfaces.magma
1667            G = sage.interfaces.magma.magma
1668        self.parent()._magma_(G)  # defines the variable name
1669        f = G(self._magma_init_())
1670        return f
1671
1672    def _gap_init_(self):
1673        return repr(self)
1674
1675    def _gap_(self, G):
1676        """
1677        EXAMPLES:
1678            sage: R.<y> = ZZ[]
1679            sage: f = y^3 - 17*y + 5
1680            sage: g = gap(f); g
1681            y^3-17*y+5
1682            sage: f._gap_init_()
1683            'y^3 - 17*y + 5'
1684            sage: R.<z> = ZZ[]
1685            sage: gap(R)
1686            PolynomialRing(..., [ z ])
1687            sage: g
1688            y^3-17*y+5
1689            sage: gap(z^2 + z)
1690            z^2+z
1691
1692        We coerce a polynomial with coefficients in a finite field:
1693
1694            sage: R.<y> = GF(7)[]
1695            sage: f = y^3 - 17*y + 5
1696            sage: g = gap(f); g
1697            y^3+Z(7)^4*y+Z(7)^5
1698            sage: g.Factors()
1699            [ y+Z(7)^0, y+Z(7)^0, y+Z(7)^5 ]
1700            sage: f.factor()
1701            (y + 5) * (y + 1)^2
1702        """
1703        if G is None:
1704            import sage.interfaces.gap
1705            G = sage.interfaces.gap.gap
1706        self.parent()._gap_(G)
1707        return G(self._gap_init_())
1708
1709    ######################################################################
1710
1711
1712    def resultant(self, other, flag=0):
1713        raise NotImplementedError
1714
1715        ## This should be switched to use NTL, which can apparently compute
1716        ## resultants!
1717        ##        void XGCD(ZZ& r, ZZX& s, ZZX& t, const ZZX& a, const ZZX& b,
1718        ##          long deterministic=0);
1719        ##// r = resultant of a and b; if r != 0, then computes s and t such
1720        ##// that: a*s + b*t = r; otherwise s and t not affected.  if
1721        ##// !deterministic, then resultant computation may use a randomized
1722        ##// strategy that errs with probability no more than 2^{-80}.
1723        #m = magma.Magma()
1724        #cmd = "R<%s> := PolynomialRing(RationalField()); "%self.parent().variable_name() + \
1725        #      "Resultant(%s, %s);"%(self,other)
1726        #s = m.cmd(cmd)
1727        #i = s.find("\r")
1728        #return eval(s[:i])
1729
1730    def reverse(self):
1731        v = list(self.list())
1732        v.reverse()
1733        return self.parent()(v)
1734
1735    def roots(self, multiplicities=True):
1736        """
1737        Return all roots of this polynomial.
1738
1739        INPUT:
1740            multiplicities -- bool (default: True, except over RR or CC)
1741                              if True return list of pairs (r, n), where r is
1742                              the root and n is the multiplicity.
1743
1744        If the polynomial is over RR or CC returns all roots in CC
1745        with multiplicities all set to 1.
1746
1747        Over all other rings it just returns the roots that lie in the
1748        base ring.
1749
1750        EXAMPLES:
1751            sage: x = QQ['x'].0
1752            sage: f = x^3 - 1
1753            sage: f.roots()
1754            [(1, 1)]
1755            sage: f = (x^3 - 1)^2
1756            sage: f.roots()
1757            [(1, 2)]
1758
1759            sage: f = -19*x + 884736
1760            sage: f.roots()
1761            [(884736/19, 1)]
1762            sage: (f^20).roots()
1763            [(884736/19, 20)]
1764
1765            sage: K.<z> = CyclotomicField(3)
1766            sage: f = K.defining_polynomial()
1767            sage: g = f.change_ring(GF(7))
1768            sage: g.roots()
1769            [(4, 1), (2, 1)]
1770            sage: g.roots(multiplicities=False)
1771            [4, 2]
1772
1773            sage: x = RR['x'].0
1774            sage: f = x^2 - 1e100
1775            sage: f.roots()
1776            [-1.00000000000000e50, 1.00000000000000e50]
1777            sage: f = x^10 - 2*(5*x-1)^2
1778            sage: f.roots()
1779            [-1.67726703399418, 0.199954796285057, 0.200045306115242, 1.57630351618444, 1.10042307611716 + 1.15629902427493*I, 1.10042307611716 - 1.15629902427493*I, -1.20040047425969 + 1.15535958549432*I, -1.20040047425969 - 1.15535958549432*I, -0.0495408941527470 + 1.63445468021367*I, -0.0495408941527470 - 1.63445468021367*I]
1780
1781            sage: x = CC['x'].0
1782            sage: i = CC.0
1783            sage: f = (x - 1)*(x - i)
1784            sage: f.roots()
1785            [1.00000000000000*I, 1.00000000000000]
1786
1787        A purely symbolic roots example:
1788            sage: f = expand((X-1)*(X-I)^3*(X^2 - sqrt(2))); f
1789            X^6 - 3*I*X^5 - X^5 + 3*I*X^4 - sqrt(2)*X^4 - 3*X^4 + 3*sqrt(2)*I*X^3 + I*X^3 + sqrt(2)*X^3 + 3*X^3 - 3*sqrt(2)*I*X^2 - I*X^2 + 3*sqrt(2)*X^2 - sqrt(2)*I*X - 3*sqrt(2)*X + sqrt(2)*I
1790            sage: print f.roots()
1791            [(I, 3), (-2^(1/4), 1), (2^(1/4), 1), (1, 1)]
1792
1793        An example where the base ring doesn't have a factorization algorithm (yet).  Note
1794        that this is currently done via nave enumeration, so could be very slow:
1795            sage: R = Integers(6)
1796            sage: S.<x> = R['x']
1797            sage: p = x^2-1
1798            sage: p.roots()
1799            Traceback (most recent call last):
1800            ...
1801            NotImplementedError: root finding with multiplicities for this polynomial not implemented (try the multiplicities=False option)
1802            sage: p.roots(multiplicities=False)
1803            [1, 5]
1804        """
1805        seq = []
1806
1807        K = self.parent().base_ring()
1808
1809        if is_RealField(K) or sage.rings.complex_field.is_ComplexField(K):
1810            if is_RealField(K):
1811                K = K.complex_field()
1812            n = pari.get_real_precision()
1813            pari.set_real_precision(int(K.prec()/3.2)+1)
1814            r = pari(self).polroots()
1815            seq = [K(root) for root in r]
1816            pari.set_real_precision(n)
1817            return seq
1818
1819        try:
1820            rts = self.factor()
1821        except NotImplementedError:
1822            if K.is_finite():
1823                if multiplicities:
1824                    raise NotImplementedError, "root finding with multiplicities for this polynomial not implemented (try the multiplicities=False option)"
1825                else:
1826                    return [a for a in K if not self(a)]
1827
1828            raise NotImplementedError, "root finding for this polynomial not implemented"
1829        for fac in rts:
1830            g = fac[0]
1831            if g.degree() == 1:
1832                if multiplicities:
1833                    seq.append((-g[0]/g[1],fac[1]))
1834                else:
1835                    seq.append(-g[0]/g[1])
1836        return seq
1837
1838    def valuation(self, p=None):
1839        r"""
1840        If $f = a_r x^r + a_{r+1}x^{r+1} + \cdots$, with $a_r$ nonzero,
1841        then the valuation of $f$ is $r$.  The valuation of the zero
1842        polynomial is $\infty$.
1843
1844        If a prime (or non-prime) $p$ is given, then the valuation is
1845        the largest power of $p$ which divides self.
1846
1847        The valuation at $\infty$ is -self.degree().
1848
1849        EXAMPLES:
1850        sage: P,x=PolynomialRing(ZZ,'x').objgen()
1851        sage: (x^2+x).valuation()
1852        1
1853        sage: (x^2+x).valuation(x+1)
1854        1
1855        sage: (x^2+1).valuation()
1856        0
1857        sage: (x^3+1).valuation(infinity)
1858        -3
1859        sage: P(0).valuation()
1860        +Infinity
1861        """
1862        cdef int k
1863        if self.is_zero():
1864            return infinity
1865        if p == infinity:
1866            return -self.degree()
1867        if p is None:
1868            p = self.parent().gen()
1869        if not isinstance(p, Polynomial) or not p.parent() is self.parent():
1870            raise TypeError, "The polynomial, p, must have the same parent as self."
1871        if p is None or p == self.parent().gen():
1872            for i in xrange(self.degree()+1):
1873                if self[i] != 0:
1874                    return ZZ(i)
1875        else:
1876            if p.degree() == 0:
1877                raise ArithmeticError, "The polynomial, p, must have positive degree."
1878            k = 0
1879            while self % p == 0:
1880                k = k + 1
1881                self = self.__floordiv__(p)
1882            return sage.rings.integer.Integer(k)
1883        raise RuntimeError, "bug in computing valuation of polynomial"
1884
1885    def ord(self, p=None):
1886        """Synonym for valuation
1887
1888        EXAMPLES:
1889        sage: P,x=PolynomialRing(ZZ,'x').objgen()
1890        sage: (x^2+x).ord(x+1)
1891        1
1892        """
1893        return self.valuation(p)
1894
1895    def name(self):
1896        return self.parent().variable_name()
1897
1898    def _xgcd(self, other):
1899        r"""
1900        Extended gcd of self and polynomial other.
1901
1902        Returns g, u, and v such that
1903              \code{g = u*self + v*other.}
1904
1905        EXAMPLES:
1906            sage: P.<x> = QQ[]
1907            sage: F = (x^2 + 2)*x^3; G = (x^2+2)*(x-3)
1908            sage: g, u, v = F.xgcd(G)
1909            sage: g, u, v
1910            (27*x^2 + 54, 1, -x^2 - 3*x - 9)
1911            sage: u*F + v*G
1912            27*x^2 + 54
1913            sage: x.xgcd(P(0))
1914            (1, 0, x)
1915            sage: f = P(0)
1916            sage: f.xgcd(x)
1917            (x, 0, 1)
1918        """
1919        if other.is_zero():
1920            R = self.parent()
1921            return R(1), R(0), self
1922        # Algorithm 3.2.2 of Cohen, GTM 138
1923        R = self.parent()
1924        A = self
1925        B = other
1926        U = R(1)
1927        G = A
1928        V1 = R(0)
1929        V3 = B
1930        while not V3.is_zero():
1931            Q, R = G.quo_rem(V3)
1932            T = U - V1*Q
1933            U = V1
1934            G = V3
1935            V1 = T
1936            V3 = R
1937        V = (G-A*U)//B
1938        return G, U, V
1939
1940    def is_irreducible(self):
1941        """
1942        EXAMPLES:
1943            sage: R.<x> = ZZ[]
1944            sage: (x^3 + 1).is_irreducible()
1945            False
1946            sage: (x^2 - 1).is_irreducible()
1947            False
1948            sage: (x^3 + 2).is_irreducible()
1949            True
1950            sage: R(0).is_irreducible()
1951            Traceback (most recent call last):
1952            ...
1953            ValueError: self must be nonzero
1954
1955        $4$ is irreducible as a polynomial, since as a polynomial
1956        it doesn't factor:
1957            sage: R(4).is_irreducible()
1958            True
1959        """
1960        if self.is_zero():
1961            raise ValueError, "self must be nonzero"
1962        if self.degree() == 0:
1963            return True
1964
1965        F = self.factor()
1966        if len(F) > 1 or F[0][1] > 1:
1967            return False
1968        return True
1969
1970    def shift(self, n):
1971        r"""
1972        Returns this polynomial multiplied by the power $x^n$. If $n$ is negative,
1973        terms below $x^n$ will be discarded. Does not change this polynomial (since
1974        polynomials are immutable).
1975
1976        EXAMPLES:
1977            sage: R.<x> = PolynomialRing(PolynomialRing(QQ,'w'),'x')
1978            sage: p = x^2 + 2*x + 4
1979            sage: p.shift(0)
1980             x^2 + 2*x + 4
1981            sage: p.shift(-1)
1982             x + 2
1983            sage: p.shift(-5)
1984             0
1985            sage: p.shift(2)
1986             x^4 + 2*x^3 + 4*x^2
1987
1988        One can also use the infix shift operator:
1989            sage: f = x^3 + x
1990            sage: f >> 2
1991            x
1992            sage: f << 2
1993            x^5 + x^3
1994
1995        AUTHOR:
1996            -- David Harvey (2006-08-06)
1998        """
1999        if n == 0:
2000            return self   # safe because immutable.
2001        if n > 0:
2002            output = [self.base_ring()(0)] * n
2003            output.extend(self.coeffs())
2004            return self.polynomial(output, check=False)
2005        if n < 0:
2006            if n > self.degree():
2007                return self.polynomial([])
2008            else:
2009                return self.polynomial(self.coeffs()[-int(n):], check=False)
2010
2011    def __lshift__(self, k):
2012        return self.shift(k)
2013
2014    def __rshift__(self, k):
2015        return self.shift(-k)
2016
2017
2018    def truncate(self, n):
2019        r"""
2020        Returns the polynomial of degree $< n$ which is equivalent to self
2021        modulo $x^n$.
2022        """
2023        return self.parent()(self[:int(n)], check=False)
2024
2026        """
2027        Returns the radical of self; over a field, this is the product of the
2028        distinct irreducible factors of self. (This is also sometimes called the
2029        "square-free part" of self, but that term is ambiguous; it is sometimes used
2030        to mean the quotient of self by its maximal square factor.)
2031
2032        EXAMPLES:
2033            sage: P.<x> = ZZ[]
2034            sage: t = (x^2-x+1)^3 * (3*x-1)^2
2036            3*x^3 - 4*x^2 + 4*x - 1
2037        """
2038        return self // self.gcd(self.derivative())
2039
2040
2041# ----------------- inner functions -------------
2042# Sagex can't handle function definitions inside other function
2043
2044
2045cdef _karatsuba_sum(v,w):
2046    if len(v)>=len(w):
2047        x = list(v)
2048        y = w
2049    else:
2050        x = list(w)
2051        y = v
2052    for i in range(len(y)):
2053        x[i] = x[i] + y[i]
2054    return x
2055
2056cdef _karatsuba_dif(v,w):
2057    if len(v)>=len(w):
2058        x = list(v)
2059        y = w
2060    else:
2061        x = list(w)
2062        y = v
2063    for i in range(len(y)):
2064        x[i] -= y[i]
2065    return x
2066
2067cdef do_karatsuba(left, right):
2068    if len(left) == 0 or len(right) == 0:
2069        return []
2070    if len(left) == 1:
2071        c = left[0]
2072        return [c*a for a in right]
2073    if len(right) == 1:
2074        c = right[0]
2075        return [c*a for a in left]
2076    if len(left) == 2 and len(right) == 2:
2077        b = left[0]
2078        a = left[1]
2079        d = right[0]
2080        c = right[1]
2081        ac = a*c
2082        bd = b*d
2083        return [bd,(a+b)*(c+d)-ac-bd,ac]
2084    e = min(len(left), len(right))/2
2085    assert e>=1, "bug in karatsuba"
2086    a, b = left[e:], left[:e]
2087    c, d = right[e:], right[:e]
2088    ac = do_karatsuba(a,c)
2089    bd = do_karatsuba(b,d)
2090    zeros = [0] * e
2091    t2 = zeros + zeros + ac
2092    t1 = zeros + _karatsuba_dif(do_karatsuba(_karatsuba_sum(a,b),_karatsuba_sum(c,d)),_karatsuba_sum(ac,bd))
2093    t0 = bd
2094    return _karatsuba_sum(t0,_karatsuba_sum(t1,t2))
2095
2096
2097
2098cdef class Polynomial_generic_dense(Polynomial):
2099    """
2100    A generic dense polynomial.
2101
2102    EXAMPLES:
2103        sage: R.<x> = PolynomialRing(PolynomialRing(QQ,'y'))
2104        sage: f = x^3 - x + 17
2105        sage: type(f)
2106        <type 'sage.rings.polynomial.polynomial_element.Polynomial_generic_dense'>
2108        True
2109    """
2110    def __init__(self, parent, x=None, int check=1, is_gen=False, int construct=0, absprec=None):
2111        Polynomial.__init__(self, parent, is_gen=is_gen)
2112
2113        if x is None:
2114            self.__coeffs = []
2115            return
2116        R = parent.base_ring()
2117
2118        if sage.rings.fraction_field_element.is_FractionFieldElement(x):
2119            if x.denominator() != 1:
2120                raise TypeError, "denominator must be 1"
2121            else:
2122                x = x.numerator()
2123
2124        if PY_TYPE_CHECK(x, Polynomial):
2125            if (<Element>x)._parent is self._parent:
2126                x = list(x.list())
2127            elif (<Element>x)._parent is R or (<Element>x)._parent == R:
2128                x = [x]
2129            elif absprec is None:
2130                x = [R(a) for a in x.list()]
2131                check = 0
2132            else:
2133                x = [R(a, absprec = absprec) for a in x.list()]
2134                check = 0
2135
2136        elif PY_TYPE_CHECK(x, list):
2137            pass
2138
2139        elif PY_TYPE_CHECK(x, int) and x == 0:
2140            self.__coeffs = []
2141            return
2142
2143        elif isinstance(x, dict):
2144            zero = R(0)
2145            n = max(x.keys())
2146            v = [zero for _ in xrange(n+1)]
2147            for i, z in x.iteritems():
2148                v[i] = z
2149            x = v
2150        elif isinstance(x, pari_gen):
2151            if absprec is None:
2152                x = [R(w) for w in x.Vecrev()]
2153            else:
2154                x = [R(w, absprec = absprec) for w in x.Vecrev()]
2155            check = 1
2156        elif not isinstance(x, list):
2157            x = [x]   # constant polynomials
2158        if check:
2159            if absprec is None:
2160                self.__coeffs = [R(z) for z in x]
2161            else:
2162                self.__coeffs = [R(z, absprec=absprec) for z in x]
2163        else:
2164            self.__coeffs = x
2165        if check:
2166            self.__normalize()
2167
2168    def __reduce__(self):
2169        return make_generic_polynomial, (self._parent, self.__coeffs)
2170
2171    def __nonzero__(self):
2172        return len(self.__coeffs) > 0
2173
2174    def __hash__(self):
2175        if len(self.__coeffs) > 1:
2176            return hash(tuple(self.__coeffs))
2177        elif len(self.__coeffs) == 1:
2178            return hash(self[0])
2179        else:
2180            return 0
2181
2182    cdef void __normalize(self):
2183        x = self.__coeffs
2184        cdef Py_ssize_t n = len(x) - 1
2185        while n >= 0 and x[n].is_zero():
2186#        while n > 0 and x[n] == 0:
2187            del x[n]
2188            n -= 1
2189
2190    def __richcmp__(left, right, int op):
2191        return (<Element>left)._richcmp(right, op)
2192
2193    def __getitem__(self, Py_ssize_t n):
2194        """
2195        EXAMPLES:
2196            sage: R.<x> = ZZ[]
2197            sage: f = (1+2*x)^5; f
2198            32*x^5 + 80*x^4 + 80*x^3 + 40*x^2 + 10*x + 1
2199            sage: f[-1]
2200            0
2201            sage: f[2]
2202            40
2203            sage: f[6]
2204            0
2205        """
2206        if n < 0 or n >= len(self.__coeffs):
2207            return self.base_ring()(0)
2208        return self.__coeffs[n]
2209
2210    def __getslice__(self, Py_ssize_t i, j):
2211        """
2212        EXAMPLES:
2213            sage: R.<x> = RDF[]
2214            sage: f = (1+2*x)^5; f
2215            32.0*x^5 + 80.0*x^4 + 80.0*x^3 + 40.0*x^2 + 10.0*x + 1.0
2216            sage: f[:3]
2217            40.0*x^2 + 10.0*x + 1.0
2218            sage: f[2:5]
2219            80.0*x^4 + 80.0*x^3 + 40.0*x^2
2220            sage: f[2:]
2221            32.0*x^5 + 80.0*x^4 + 80.0*x^3 + 40.0*x^2
2222        """
2223        if i <= 0:
2224            i = 0
2225            zeros = []
2226        elif i > 0:
2227            zeros = [self._parent.base_ring()(0)] * i
2228        return self._parent(zeros + self.__coeffs[i:j])
2229
2230    def _unsafe_mutate(self, n, value):
2231        """
2232        Never use this unless you really know what you are doing.
2233
2234        WARNING: This could easily introduce subtle bugs, since SAGE
2235        assumes everywhere that polynomials are immutable.  It's OK to
2236        use this if you really know what you're doing.
2237
2238        EXAMPLES:
2239            sage: R.<x> = ZZ[]
2240            sage: f = (1+2*x)^2; f
2241            4*x^2 + 4*x + 1
2242            sage: f._unsafe_mutate(1, -5)
2243            sage: f
2244            4*x^2 - 5*x + 1
2245        """
2246        n = int(n)
2247        value = self.base_ring()(value)
2248        if n >= 0 and n < len(self.__coeffs):
2249            self.__coeffs[n] = value
2250            if n == len(self.__coeffs) and value == 0:
2251                self.__normalize()
2252        elif n < 0:
2253            raise IndexError, "polynomial coefficient index must be nonnegative"
2254        elif value != 0:
2255            zero = self.base_ring()(0)
2256            for _ in xrange(len(self.__coeffs), n):
2257                self.__coeffs.append(zero)
2258            self.__coeffs.append(value)
2259
2260    def __floordiv__(self, right):
2261        """
2262        Return the quotient upon division (no remainder).
2263
2264        EXAMPLES:
2265            sage: R.<x> = QQ[]
2266            sage: f = (1+2*x)^3 + 3*x; f
2267            8*x^3 + 12*x^2 + 9*x + 1
2268            sage: g = f // (1+2*x); g
2269            4*x^2 + 4*x + 5/2
2270            sage: f - g * (1+2*x)
2271            -3/2
2272            sage: f.quo_rem(1+2*x)
2273            (4*x^2 + 4*x + 5/2, -3/2)
2274        """
2275        if right.parent() == self.parent():
2276            return Polynomial.__floordiv__(self, right)
2277        d = self.parent().base_ring()(right)
2278        return self.polynomial([c // d for c in self.__coeffs], check=False)
2279
2280    cdef ModuleElement _add_c_impl(self, ModuleElement right):
2281        cdef Py_ssize_t check=0, i, min
2282        x = (<Polynomial_generic_dense>self).__coeffs
2283        y = (<Polynomial_generic_dense>right).__coeffs
2284        if len(x) > len(y):
2285            min = len(y)
2286            high = x[min:]
2287        elif len(x) < len(y):
2288            min = len(x)
2289            high = y[min:]
2290        else:
2291            min = len(x)
2292        low = [x[i] + y[i] for i from 0 <= i < min]
2293        if len(x) == len(y):
2294            res = self._parent(low, check=0)
2295            (<Polynomial_generic_dense>res).__normalize()
2296            return res
2297        else:
2298            return self._parent(low + high, check=0)
2299
2300    cdef ModuleElement _sub_c_impl(self, ModuleElement right):
2301        cdef Py_ssize_t check=0, i, min
2302        x = (<Polynomial_generic_dense>self).__coeffs
2303        y = (<Polynomial_generic_dense>right).__coeffs
2304        if len(x) > len(y):
2305            min = len(y)
2306            high = x[min:]
2307        elif len(x) < len(y):
2308            min = len(x)
2309            high = [-y[i] for i from min <= i < len(y)]
2310        else:
2311            min = len(x)
2312        low = [x[i] - y[i] for i from 0 <= i < min]
2313        if len(x) == len(y):
2314            res = self._parent(low, check=0)
2315            (<Polynomial_generic_dense>res).__normalize()
2316            return res
2317        else:
2318            return self._parent(low + high, check=0)
2319
2320    def _rmul_(self, c):
2321        if len(self.__coeffs) == 0:
2322            return self
2323        v = [c * a for a in self.__coeffs]
2324        res = self._parent(v, check=0)
2325        if not v[len(v)-1]:
2326            (<Polynomial_generic_dense>res).__normalize()
2327        return res
2328
2329    def _lmul_(self, c):
2330        if len(self.__coeffs) == 0:
2331            return self
2332        v = [a * c for a in self.__coeffs]
2333        res = self._parent(v, check=0)
2334        if not v[len(v)-1]:
2335            (<Polynomial_generic_dense>res).__normalize()
2336        return res
2337
2338    def list(self):
2339        """
2340        Return a new copy of the list of the underlying
2341        elements of self.
2342
2343        EXAMPLES:
2344            sage: R.<x> = GF(17)[]
2345            sage: f = (1+2*x)^3 + 3*x; f
2346            8*x^3 + 12*x^2 + 9*x + 1
2347            sage: f.list()
2348            [1, 9, 12, 8]
2349        """
2350        return list(self.__coeffs)
2351
2352    def degree(self):
2353        """
2354        EXAMPLES:
2355            sage: R.<x> = RDF[]
2356            sage: f = (1+2*x^7)^5
2357            sage: f.degree()
2358            35
2359        """
2360        return len(self.__coeffs) - 1
2361
2362    def shift(self, Py_ssize_t n):
2363        r"""
2364        Returns this polynomial multiplied by the power $x^n$. If $n$
2365        is negative, terms below $x^n$ will be discarded. Does not
2366        change this polynomial.
2367
2368        EXAMPLES:
2369            sage: R.<x> = PolynomialRing(PolynomialRing(QQ,'y'), 'x')
2370            sage: p = x^2 + 2*x + 4
2371            sage: type(p)
2372            <type 'sage.rings.polynomial.polynomial_element.Polynomial_generic_dense'>
2373            sage: p.shift(0)
2374             x^2 + 2*x + 4
2375            sage: p.shift(-1)
2376             x + 2
2377            sage: p.shift(2)
2378             x^4 + 2*x^3 + 4*x^2
2379
2380        AUTHOR:
2381            -- David Harvey (2006-08-06)
2382        """
2383        if n == 0:
2384            return self
2385        if n > 0:
2386            output = [self.base_ring()(0)] * n
2387            output.extend(self.__coeffs)
2388            return self.polynomial(output, check=False)
2389        if n < 0:
2390            if n > len(self.__coeffs) - 1:
2391                return self.polynomial([])
2392            else:
2393                return self.polynomial(self.__coeffs[-int(n):], check=False)
2394
2395def make_generic_polynomial(parent, coeffs):
2396    return parent(coeffs)
Note: See TracBrowser for help on using the repository browser.