source: sage/ext/integer.pyx @ 1206:479103213c10

Revision 1206:479103213c10, 47.6 KB checked in by dmharvey@…, 7 years ago (diff)

[project @ Integer.exact_log -- adds Integer.exact_log() method, which computes log(n, m) without precision problems]
Line 
1r"""
2Elements of the ring $\Z$ of integers
3
4AUTHORS:
5    -- William Stein (2005): initial version
6    -- Gonzalo Tornaria (2006-03-02): vastly improved python/GMP conversion; hashing
7    -- Didier Deshommes <dfdeshom@gmail.com> (2006-03-06): numerous examples and docstrings
8    -- William Stein (2006-03-31): changes to reflect GMP bug fixes
9    -- William Stein (2006-04-14): added GMP factorial method (since it's
10                                   now very fast).
11    -- David Harvey (2006-09-15): added nth_root, exact_log
12"""
13
14#*****************************************************************************
15#       Copyright (C) 2004 William Stein <wstein@gmail.com>
16#
17#  Distributed under the terms of the GNU General Public License (GPL)
18#
19#    This code is distributed in the hope that it will be useful,
20#    but WITHOUT ANY WARRANTY; without even the implied warranty of
21#    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
22#    General Public License for more details.
23#
24#  The full text of the GPL is available at:
25#
26#                  http://www.gnu.org/licenses/
27#*****************************************************************************
28
29doc="""
30Integers
31"""
32
33import operator
34
35import sys
36
37include "gmp.pxi"
38include "interrupt.pxi"  # ctrl-c interrupt block support
39
40cdef extern from "mpz_pylong.h":
41    cdef mpz_get_pylong(mpz_t src)
42    cdef int mpz_set_pylong(mpz_t dst, src) except -1
43    cdef long mpz_pythonhash(mpz_t src)
44
45cdef class Integer(element.EuclideanDomainElement)
46
47import sage.rings.integer_ring
48import sage.rings.coerce
49import sage.rings.infinity
50import sage.rings.complex_field
51import rational as rational
52import sage.libs.pari.all
53import mpfr
54import sage.misc.functional
55
56cdef mpz_t mpz_tmp
57mpz_init(mpz_tmp)
58
59cdef public int set_mpz(Integer self, mpz_t value):
60    mpz_set(self.value, value)
61
62cdef set_from_Integer(Integer self, Integer other):
63    mpz_set(self.value, other.value)
64
65cdef set_from_int(Integer self, int other):
66    mpz_set_si(self.value, other)
67
68cdef public mpz_t* get_value(Integer self):
69    return &self.value
70
71# This crashes SAGE:
72#  s = 2003^100300000
73# The problem is related to realloc moving all the memory
74# and returning a pointer to the new block of memory, I think.
75
76cdef extern from "stdlib.h":
77    void abort()
78
79cdef void* pymem_realloc(void *ptr, size_t old_size, size_t new_size):
80    return PyMem_Realloc(ptr, new_size)
81    #print "hello-realloc: ", <long> ptr, old_size, new_size
82    #cdef void* p
83    #p = PyMem_Realloc(ptr, new_size)
84    #print "p = ", <long> p
85    #if <void*> p != <void*> ptr:
86    #    abort()
87    #return p
88
89
90cdef void pymem_free(void *ptr, size_t size):
91    PyMem_Free(ptr)
92
93cdef void* pymem_malloc(size_t size):
94    return PyMem_Malloc(size)
95
96cdef extern from "gmp.h":
97    void mp_set_memory_functions (void *(*alloc_func_ptr) (size_t), void *(*realloc_func_ptr) (void *, size_t, size_t), void (*free_func_ptr) (void *, size_t))
98
99
100def pmem_malloc():
101    """
102    Use the Python heap for GMP memory management.
103    """
104    mp_set_memory_functions(PyMem_Malloc, pymem_realloc, pymem_free)
105    #mp_set_memory_functions(pymem_malloc, pymem_realloc, pymem_free)
106
107pmem_malloc()
108
109cdef class Integer(element.EuclideanDomainElement):
110    """
111    The \\class{Integer} class represents arbitrary precision
112    integers.  It derives from the \\class{Element} class, so
113    integers can be used as ring elements anywhere in SAGE.
114
115    \\begin{notice}
116    The class \\class{Integer} is implemented in Pyrex, as a wrapper
117    of the GMP \\code{mpz_t} integer type.
118    \\end{notice}
119    """
120    def __new__(self, x=None, unsigned int base=0):
121        mpz_init(self.value)
122
123    def __pyxdoc__init__(self):
124        """
125        You can create an integer from an int, long, string literal, or
126        integer modulo N.
127
128        EXAMPLES:
129            sage: Integer(495)
130            495
131            sage: Integer('495949209809328523')
132            495949209809328523
133            sage: Integer(Mod(3,7))
134            3
135
136        Integers also support the standard arithmetic operations, such
137        as +,-,*,/,^, \code{abs}, \code{mod}, \code{float}:
138            sage: 2^3
139            8
140        """
141    def __init__(self, x=None, unsigned int base=0):
142        """
143        EXAMPLES:
144            sage: a = long(-901824309821093821093812093810928309183091832091)
145            sage: b = ZZ(a); b
146            -901824309821093821093812093810928309183091832091
147            sage: ZZ(b)
148            -901824309821093821093812093810928309183091832091
149            sage: ZZ('-901824309821093821093812093810928309183091832091')
150            -901824309821093821093812093810928309183091832091
151            sage: ZZ(int(-93820984323))
152            -93820984323
153            sage: ZZ(ZZ(-901824309821093821093812093810928309183091832091))
154            -901824309821093821093812093810928309183091832091
155            sage: ZZ(QQ(-901824309821093821093812093810928309183091832091))
156            -901824309821093821093812093810928309183091832091
157            sage: ZZ(pari('Mod(-3,7)'))
158            4
159            sage: ZZ('sage')
160            Traceback (most recent call last):
161            ...
162            TypeError: unable to convert x (=sage) to an integer
163            sage: Integer('zz',36).str(36)
164            'zz'
165            sage: ZZ('0x3b').str(16)
166            '3b'
167        """
168        if not (x is None):
169            if isinstance(x, Integer):
170                set_from_Integer(self, x)
171            elif hasattr(x, "_integer_"):
172                set_from_Integer(self, x._integer_())
173            elif isinstance(x, int):
174                mpz_set_si(self.value, x)
175
176            elif isinstance(x, long):
177                #_sig_on
178                mpz_set_pylong(self.value, x)
179                #_sig_off
180                #s = "%x"%x
181                #mpz_set_str(self.value, s, 16)
182
183            elif isinstance(x, str):
184                if base < 0 or base > 36:
185                    raise ValueError, "base (=%s) must be between 2 and 36"%base
186                if mpz_set_str(self.value, x, base) != 0:
187                    raise TypeError, "unable to convert x (=%s) to an integer"%x
188
189            elif isinstance(x, rational.Rational):
190                if x.denominator() != 1:
191                    raise TypeError, "Unable to coerce rational (=%s) to an Integer."%x
192                set_from_Integer(self, x.numer())
193               
194
195            elif isinstance(x, sage.libs.pari.all.pari_gen):
196                if x.type() == 't_INTMOD':
197                    x = x.lift()
198                # TODO: figure out how to convert to pari integer in base 16 ?
199                s = hex(x)
200                if mpz_set_str(self.value, s, 16) != 0:
201                    raise TypeError, "Unable to coerce PARI %s to an Integer."%x
202               
203            else:
204                raise TypeError, "Unable to coerce %s (of type %s) to an Integer."%(x,type(x))
205   
206
207    def __reduce__(self):
208        # This single line below took me HOURS to figure out.
209        # It is the *trick* needed to pickle pyrex extension types.
210        # The trick is that you must put a pure Python function
211        # as the first argument, and that function must return
212        # the result of unpickling with the argument in the second
213        # tuple as input. All kinds of problems happen
214        # if we don't do this.
215        return sage.rings.integer.make_integer, (self.str(32),)
216
217    def _reduce_set(self, s):
218        mpz_set_str(self.value, s, 32)
219
220    def _im_gens_(self, codomain, im_gens):
221        return codomain._coerce_(self)
222
223    #def __reduce__(self):
224    #    return sage.rings.integer_ring.Z, (long(self),)
225
226    def _xor(Integer self, Integer other):
227        cdef Integer x
228        x = Integer()
229        mpz_xor(x.value, self.value, other.value)
230        return x
231
232    def __xor__(x, y):
233        """
234        Compute the exclusive or of x and y.
235
236        EXAMPLES:
237            sage: n = ZZ(2); m = ZZ(3)
238            sage: n.__xor__(m)
239            1       
240        """
241        if isinstance(x, Integer) and isinstance(y, Integer):
242            return x._xor(y)
243        return sage.rings.coerce.bin_op(x, y, operator.xor)
244       
245       
246
247    cdef int cmp(self, Integer x):
248        cdef int i
249        i = mpz_cmp(self.value, x.value)
250        if i < 0:
251            return -1
252        elif i == 0:
253            return 0
254        else:
255            return 1
256
257    def __richcmp__(Integer self, right, int op):
258        cdef int n
259        if not isinstance(right, Integer):
260            try:
261                n = sage.rings.coerce.cmp(self, right)
262            except TypeError:
263                n = -1
264        else:
265            n = self.cmp(right)
266        return self._rich_to_bool(op, n)
267
268    def __cmp__(self, x):
269        return self.cmp(x)
270
271   
272    def copy(self):
273        """
274        Return a copy of the integer.
275        """
276        cdef Integer z
277        z = Integer()
278        set_mpz(z,self.value)
279        return z
280
281
282    def list(self):
283        """
284        Return a list with the rational element in it, to be
285        compatible with the method for number fields.
286       
287        EXAMPLES:
288        sage: m = 5
289        sage: m.list()
290        [5]
291        """
292        return [ self ]
293
294
295    def  __dealloc__(self):
296        mpz_clear(self.value)
297       
298    def __repr__(self):
299        return self.str()
300
301    def _latex_(self):
302        return self.str()
303
304    def _mathml_(self):
305        return '<mn>%s</mn>'%self
306
307    def __str_malloc(self, int base=10):
308        """
309        Return the string representation of \\code{self} in the given
310        base.  (Uses malloc then PyMem.  This is actually slightly
311        faster than self.str() below, but it is unpythonic to use
312        malloc.)  However, self.str() below is nice because we know
313        the size of the string ahead of time, and can work around a
314        bug in GMP nicely.  There seems to be a bug in GMP, where
315        non-2-power base conversion for very large integers > 10
316        million digits (?) crashes GMP.
317        """
318        _sig_on
319        cdef char *s
320        s = mpz_get_str(NULL, base, self.value)
321        t = str(s)
322        free(s)
323        _sig_off
324        return t
325
326    def str(self, int base=10):
327        r"""
328        Return the string representation of \code{self} in the given
329        base.
330
331
332        EXAMPLES:
333            sage: Integer(2^10).str(2)
334            '10000000000'
335            sage: Integer(2^10).str(17)
336            '394'
337           
338            sage: two=Integer(2)
339            sage: two.str(1)
340            Traceback (most recent call last):
341            ...
342            ValueError: base (=1) must be between 2 and 36
343           
344            sage: two.str(37)
345            Traceback (most recent call last):
346            ...           
347            ValueError: base (=37) must be between 2 and 36
348
349            sage: big = 10^5000000
350            sage: s = big.str()                 # long (> 20 seconds)
351            sage: len(s)                        # depends on long
352            5000001
353            sage: s[:10]                        # depends on long
354            '1000000000'
355        """
356        if base < 2 or base > 36:
357            raise ValueError, "base (=%s) must be between 2 and 36"%base
358        cdef size_t n
359        cdef char *s
360        n = mpz_sizeinbase(self.value, base) + 2
361        s = <char *>PyMem_Malloc(n)
362        if s == NULL:
363            raise MemoryError, "Unable to allocate enough memory for the string representation of an integer."
364        _sig_on
365        mpz_get_str(s, base, self.value)
366        _sig_off
367        k = PyString_FromString(s)
368        PyMem_Free(s)
369        return k
370
371    def __hex__(self):
372        r"""
373        Return the hexadecimal digits of self in lower case.
374
375        \note{'0x' is \emph{not} prepended to the result like is done
376        by the corresponding Python function on int or long.  This is
377        for efficiency sake---adding and stripping the string wastes
378        time; since this function is used for conversions from
379        integers to other C-library structures, it is important that
380        it be fast.}
381
382        EXAMPLES:
383            sage: print hex(Integer(15))
384            f
385            sage: print hex(Integer(16))
386            10
387            sage: print hex(Integer(16938402384092843092843098243))
388            36bb1e3929d1a8fe2802f083
389            sage: print hex(long(16938402384092843092843098243))
390            0x36BB1E3929D1A8FE2802F083L
391        """
392        return self.str(16)
393
394    def binary(self):
395        """
396        Return the binary digits of self as a string.
397
398        EXAMPLES:
399            sage: print Integer(15).binary()
400            1111
401            sage: print Integer(16).binary()
402            10000
403            sage: print Integer(16938402384092843092843098243).binary()
404            1101101011101100011110001110010010100111010001101010001111111000101000000000101111000010000011
405        """
406        return self.str(2)
407
408       
409   
410    def set_si(self, signed long int n):
411        """
412        Coerces $n$ to a C signed integer if possible, and sets self
413        equal to $n$.
414
415        EXAMPLES:
416            sage: n= ZZ(54)
417            sage: n.set_si(-43344);n
418            -43344
419            sage: n.set_si(43344);n
420            43344
421
422        Note that an error occurs when we are not dealing with
423        integers anymore
424            sage: n.set_si(2^32);n
425            Traceback (most recent call last):      # 32-bit
426            ...                                     # 32-bit
427            OverflowError: long int too large to convert to int   # 32-bit
428            4294967296       # 64-bit
429            sage: n.set_si(-2^32);n
430            Traceback (most recent call last):      # 32-bit
431            ...                                     # 32-bit
432            OverflowError: long int too large to convert to int     # 32-bit
433            -4294967296      # 64-bit
434        """
435        mpz_set_si(self.value, n)
436
437    def set_str(self, s, base=10):
438        """
439        Set self equal to the number defined by the string $s$ in the
440        given base.
441
442        EXAMPLES:
443            sage: n=100
444            sage: n.set_str('100000',2)
445            sage: n
446            32
447
448        If the number begins with '0X' or '0x', it is converted
449        to an hex number:
450            sage: n.set_str('0x13',0)
451            sage: n
452            19
453            sage: n.set_str('0X13',0)
454            sage: n
455            19
456
457        If the number begins with a '0', it is converted to an octal
458        number:
459            sage: n.set_str('013',0)
460            sage: n
461            11
462
463        '13' is not a valid binary number so the following raises
464        an exception:
465            sage: n.set_str('13',2)
466            Traceback (most recent call last):
467            ...
468            TypeError: unable to convert x (=13) to an integer in base 2
469        """
470        valid = mpz_set_str(self.value, s, base)
471        if valid != 0:
472            raise TypeError, "unable to convert x (=%s) to an integer in base %s"%(s, base)
473
474    cdef void set_from_mpz(Integer self, mpz_t value):
475        mpz_set(self.value, value)
476
477    cdef mpz_t* get_value(Integer self):
478        return &self.value
479
480    def __add_(Integer self, Integer other):       
481        cdef Integer x
482        x = Integer()
483        mpz_add(x.value, self.value, other.value)
484        return x
485       
486    def __add__(x, y):
487        """
488        EXAMPLES:
489        Add 2 integers:
490            sage: a = Integer(3) ; b = Integer(4)
491            sage: a + b == 7
492            True
493
494        Add an integer and a real number:
495            sage: a + 4.0
496            7.0000000000000000
497
498        Add an integer and a rational number:
499            sage: a + Rational(2)/5
500            17/5
501
502        Add an integer and a complex number:
503            sage: b = ComplexField().0 + 1.5
504            sage: loads((a+b).dumps()) == a+b
505            True
506        """
507        if isinstance(x, Integer) and isinstance(y, Integer):
508            return x.__add_(y)
509        return sage.rings.coerce.bin_op(x, y, operator.add)
510
511    def __sub_(Integer self, Integer other):
512        cdef Integer x
513        x = Integer()
514        mpz_sub(x.value, self.value, other.value)
515        return x
516       
517    def __sub__(x, y):
518        """
519        EXAMPLES:
520            sage: a = Integer(5); b = Integer(3)
521            sage: b - a
522            -2
523        """
524        if isinstance(x, Integer) and isinstance(y, Integer):
525            return x.__sub_(y)
526        return sage.rings.coerce.bin_op(x, y, operator.sub)
527
528    def __mul_(Integer self, Integer other):
529        cdef Integer x
530        x = Integer()
531
532        _sig_on
533        mpz_mul(x.value, self.value, other.value)
534        _sig_off
535
536        return x
537           
538    def __mul__(x, y):
539        """
540        EXAMPLES:
541            sage: a = Integer(3) ; b = Integer(4)
542            sage: a * b == 12
543            True
544            sage: loads((a * 4.0).dumps()) == a*b
545            True
546            sage: a * Rational(2)/5
547            6/5
548            sage: b = ComplexField().0 + 1.5
549            sage: loads((a*b).dumps()) == a*b
550            True
551
552            sage: list([2,3]) * 4
553            [2, 3, 2, 3, 2, 3, 2, 3]
554
555            sage: 'sage'*Integer(3)
556            'sagesagesage'
557        """
558        if isinstance(x, Integer) and isinstance(y, Integer):
559            return x.__mul_(y)
560        if isinstance(x, (str, list)):
561            return x * int(y)
562        return sage.rings.coerce.bin_op(x, y, operator.mul)
563       
564    def __div_(Integer self, Integer other):
565        cdef Integer x
566        #if mpz_divisible_p(self.value, other.value):
567        #    x = Integer()
568        #    mpz_divexact(x.value, self.value, other.value)
569        #    return x
570        #else:
571        return rational.Rational(self)/rational.Rational(other)
572        #raise ArithmeticError, "Exact division impossible."
573       
574    def __div__(x, y):
575        """
576        Computes a \over{b}
577       
578        EXAMPLES:
579            sage: a = Integer(3) ; b = Integer(4)
580            sage: a / b == Rational(3) / 4
581            True
582            sage: Integer(32) / Integer(32)
583            1
584            sage: b = ComplexField().0 + 1.5
585            sage: loads((a/b).dumps()) == a/b
586            True
587        """
588        if isinstance(x, Integer) and isinstance(y, Integer):
589            return x.__div_(y)
590        return sage.rings.coerce.bin_op(x, y, operator.div)
591
592    def __floordiv(Integer self, Integer other):
593        cdef Integer x
594        x = Integer()
595       
596
597        _sig_on
598        mpz_fdiv_q(x.value, self.value, other.value)
599        _sig_off
600
601        return x
602
603
604    def __floordiv__(x, y):
605        r"""
606        Computes the whole part of self \over{other}
607       
608        EXAMPLES:
609            sage: a = Integer(321) ; b = Integer(10)
610            sage: a // b
611            32
612        """
613        if isinstance(x, Integer) and isinstance(y, Integer):
614            return x.__floordiv(y)
615        return sage.rings.coerce.bin_op(x, y, operator.floordiv)
616
617
618    def __pow__(self, n, dummy):
619        r"""
620        Computes $\text{self}^n$
621       
622        EXAMPLES:
623            sage: 2^-6
624            1/64
625            sage: 2^6
626            64
627            sage: 2^0
628            1
629            sage: 2^-0
630            1
631            sage: (-1)^(1/3)
632            Traceback (most recent call last):
633            ...
634            TypeError: exponent (=1/3) must be an integer.
635            Coerce your numbers to real or complex numbers first.
636        """
637        cdef Integer _self, _n
638        cdef unsigned int _nval
639        if not isinstance(self, Integer):
640            return self.__pow__(int(n))
641        try:
642            _n = Integer(n)
643        except TypeError:
644            raise TypeError, "exponent (=%s) must be an integer.\nCoerce your numbers to real or complex numbers first."%n
645        if _n < 0:
646            return Integer(1)/(self**(-_n))
647        _self = integer(self)
648        cdef Integer x
649        x = Integer()
650        _nval = _n
651
652        _sig_on
653        mpz_pow_ui(x.value, _self.value, _nval)
654        _sig_off
655
656        return x
657
658    def nth_root(self, int n, int report_exact=0):
659        r"""
660        Returns the truncated nth root of self.
661
662        INPUT:
663            n -- integer >= 1 (must fit in C int type)
664            report_exact -- boolean, whether to report if the root extraction
665                          was exact
666
667        OUTPUT:
668           If report_exact is 0 (default), then returns the truncation of the
669           nth root of self (i.e. rounded towards zero).
670
671           If report_exact is 1, then returns the nth root and a boolean
672           indicating whether the root extraction was exact.
673
674        AUTHOR:
675           -- David Harvey (2006-09-15)
676
677        EXAMPLES:
678          sage: Integer(125).nth_root(3)
679          5
680          sage: Integer(124).nth_root(3)
681          4
682          sage: Integer(126).nth_root(3)
683          5
684
685          sage: Integer(-125).nth_root(3)
686          -5
687          sage: Integer(-124).nth_root(3)
688          -4
689          sage: Integer(-126).nth_root(3)
690          -5
691
692          sage: Integer(125).nth_root(2, True)
693          (11, False)
694          sage: Integer(125).nth_root(3, True)
695          (5, True)
696
697          sage: Integer(125).nth_root(-5)
698          Traceback (most recent call last):
699          ...
700          ValueError: n (=-5) must be positive
701
702          sage: Integer(-25).nth_root(2)
703          Traceback (most recent call last):
704          ...
705          ValueError: cannot take even root of negative number
706         
707        """
708        if n < 1:
709            raise ValueError, "n (=%s) must be positive" % n
710        if (self < 0) and not (n & 1):
711            raise ValueError, "cannot take even root of negative number"
712        cdef Integer x
713        cdef int is_exact
714        x = Integer()
715        _sig_on
716        is_exact = mpz_root(x.value, self.value, n)
717        _sig_off
718
719        if report_exact:
720            return x, bool(is_exact)
721        else:
722            return x
723
724    def exact_log(self, m):
725        r"""
726        Returns the largest integer $k$ such that $m^k \leq \text{self}$.
727
728        This is guaranteed to return the correct answer even when the usual
729        log function doesn't have sufficient precision.
730
731        INPUT:
732            m -- integer >= 2
733
734        AUTHOR:
735           -- David Harvey (2006-09-15)
736
737        TODO:
738           -- Currently this is extremely stupid code (although it should
739           always work). Someone needs to think about doing this properly
740           by estimating errors in the log function etc.
741
742        EXAMPLES:
743           sage: Integer(125).exact_log(5)
744           3
745           sage: Integer(124).exact_log(5)
746           2
747           sage: Integer(126).exact_log(5)
748           3
749           sage: Integer(3).exact_log(5)
750           0
751           sage: Integer(1).exact_log(5)
752           0
753
754        This is why you don't want to use log(n, m):
755           sage: x = 3**10000000
756           sage: log(x, 3)
757           9999999.9999999981
758           sage: log(x + 100000, 3)
759           9999999.9999999981
760
761           sage: x.exact_log(3)
762           10000000
763           sage: (x+1).exact_log(3)
764           10000000
765           sage: (x-1).exact_log(3)
766           9999999
767           
768        """
769        if self <= 0:
770            raise ValueError, "self must be positive"
771        if m < 2:
772            raise ValueError, "m must be at least 2"
773
774        guess = int(sage.misc.functional.log(self, m))
775        power = m ** guess
776
777        while power > self:
778            power = power / m
779            guess = guess - 1
780
781        if power == self:
782            return guess
783
784        while power < self:
785            power = power * m
786            guess = guess + 1
787
788        if power == self:
789            return guess
790        else:
791            return guess - 1
792       
793
794    def __pos__(self):
795        """
796        EXAMPLES:
797            sage: z=43434
798            sage: z.__pos__()
799            43434
800        """
801        return self
802
803    def __neg__(self):
804        """
805        Computes $-self$
806       
807        EXAMPLES:
808            sage: z = 32
809            sage: -z
810            -32
811            sage: z = 0; -z
812            0
813            sage: z = -0; -z
814            0
815            sage: z = -1; -z
816            1
817        """
818        cdef Integer x
819        x = Integer()
820        mpz_neg(x.value, self.value)
821        return x
822
823    def __abs__(self):
824        """
825        Computes $|self|$
826       
827        EXAMPLES:
828            sage: z = -1
829            sage: abs(z)
830            1
831            sage: abs(z) == abs(1)
832            True
833        """
834        cdef Integer x
835        x = Integer()
836        mpz_abs(x.value, self.value)
837        return x
838
839    def __mod__(self, modulus):
840        r"""
841        Returns \code{self % modulus}.
842       
843        EXAMPLES:
844            sage: z = 43
845            sage: z % 2
846            1
847            sage: z % 0
848            Traceback (most recent call last):
849            ...
850            ZeroDivisionError: Integer modulo by zero
851        """
852        cdef Integer _modulus, _self
853        _modulus = integer(modulus)
854        if not _modulus:
855            raise ZeroDivisionError, "Integer modulo by zero"           
856        _self = integer(self)
857       
858        cdef Integer x
859        x = Integer()
860
861        _sig_on
862        mpz_mod(x.value, _self.value, _modulus.value)
863        _sig_off
864       
865        return x
866
867
868    def quo_rem(self, other):
869        """
870        Returns the quotient and the remainder of
871        self divided by other.
872
873        INPUT:
874            other -- the integer the divisor
875
876        OUTPUT:
877            q   -- the quotient of self/other
878            r   -- the remainder of self/other
879       
880        EXAMPLES:
881            sage: z = Integer(231)
882            sage: z.quo_rem(2)
883            (115, 1)
884            sage: z.quo_rem(-2)
885            (-115, 1)
886            sage: z.quo_rem(0)
887            Traceback (most recent call last):
888            ...
889            ZeroDivisionError: other (=0) must be nonzero
890        """
891        cdef Integer _other, _self
892        _other = integer(other)
893        if not _other:
894            raise ZeroDivisionError, "other (=%s) must be nonzero"%other
895        _self = integer(self)
896
897        cdef Integer q, r
898        q = Integer()
899        r = Integer()
900
901        _sig_on
902        mpz_tdiv_qr(q.value, r.value, _self.value, _other.value)
903        _sig_off
904       
905        return q, r
906
907       
908
909    def powermod(self, exp, mod):
910        """
911        Compute self**exp modulo mod.
912
913        EXAMPLES:
914            sage: z = Integer(2)
915            sage: z.powermod(31,31)
916            2
917            sage: z.powermod(0,31)
918            1
919            sage: z.powermod(-31,31) == 2^-31 % 31
920            True
921
922            As expected, the following is invalid:
923            sage: z.powermod(31,0)
924            Traceback (most recent call last):
925            ...
926            RuntimeError
927        """
928        cdef Integer x, _exp, _mod
929        _exp = Integer(exp); _mod = Integer(mod)
930        x = Integer()
931
932        _sig_on
933        mpz_powm(x.value, self.value, _exp.value, _mod.value)
934        _sig_off
935       
936        return x
937
938    def rational_reconstruction(self, Integer m):
939        return rational.pyrex_rational_reconstruction(self, m)
940
941    def powermodm_ui(self, exp, mod):
942        r"""
943        Computes self**exp modulo mod, where exp is an unsigned
944        long integer.
945               
946        EXAMPLES:
947            sage: z = 32
948            sage: z.powermodm_ui(2, 4)
949            0
950            sage: z.powermodm_ui(2, 14)
951            2
952            sage: z.powermodm_ui(2^31-1, 14)
953            4
954            sage: z.powermodm_ui(2^31, 14)
955            Traceback (most recent call last):                              # 32-bit
956            ...                                                             # 32-bit
957            OverflowError: exp (=2147483648) must be <= 2147483647   # 32-bit
958            2              # 64-bit
959            sage: z.powermodm_ui(2^63, 14)
960            Traceback (most recent call last):                             
961            ...                                                             
962            OverflowError: exp (=9223372036854775808) must be <= 2147483647           # 32-bit
963            OverflowError: exp (=9223372036854775808) must be <= 9223372036854775807  # 64-bit
964        """
965        if exp < 0:
966            raise ValueError, "exp (=%s) must be nonnegative"%exp
967        elif exp > sys.maxint:
968            raise OverflowError, "exp (=%s) must be <= %s"%(exp, sys.maxint)
969        cdef Integer x, _mod
970        _mod = Integer(mod)
971        x = Integer()
972
973        _sig_on
974        mpz_powm_ui(x.value, self.value, exp, _mod.value)
975        _sig_off
976       
977        return x
978
979    def __int__(self):
980        return int(mpz_get_pylong(self.value))
981
982        #cdef char *s
983        #s = mpz_get_str(NULL, 32, self.value)
984        #n = int(s,32)
985        #free(s)
986        #return n
987
988    def __long__(self):
989        return mpz_get_pylong(self.value)
990        #cdef char *s
991        #s = mpz_get_str(NULL, 32, self.value)
992        #n = long(s,32)
993        #free(s)
994        #return n
995
996    def __nonzero__(self):
997        return not self.is_zero()
998
999    def __float__(self):
1000        return mpz_get_d(self.value)
1001
1002    def __hash__(self):
1003        #return hash(int(self))
1004        return mpz_pythonhash(self.value)
1005   
1006        #cdef int n
1007        #n = mpz_get_si(self.value)
1008        #if n == -1:
1009        #    return -2     # since -1 is not an allowed Python hash for C ext -- it's an error indicator.
1010        #return n
1011
1012    def factor(self, algorithm='pari'):
1013        """
1014        Return the prime factorization of the integer as a list of
1015        pairs $(p,e)$, where $p$ is prime and $e$ is a positive integer.
1016
1017        INPUT:
1018            algorithm -- string
1019                 * 'pari' -- (default)  use the PARI c library
1020                 * 'kash' -- use KASH computer algebra system (requires
1021                             the optional kash package be installed)
1022        """
1023        return sage.rings.integer_ring.factor(self, algorithm=algorithm)
1024
1025    def coprime_integers(self, m):
1026        """
1027        Return the positive integers $< m$ that are coprime to self.
1028
1029        EXAMPLES:
1030            sage: n = 8
1031            sage: n.coprime_integers(8)
1032            [1, 3, 5, 7]
1033            sage: n.coprime_integers(11)
1034            [1, 3, 5, 7, 9]
1035            sage: n = 5; n.coprime_integers(10)
1036            [1, 2, 3, 4, 6, 7, 8, 9]
1037            sage: n.coprime_integers(5)
1038            [1, 2, 3, 4]
1039            sage: n = 99; n.coprime_integers(99)
1040            [1, 2, 4, 5, 7, 8, 10, 13, 14, 16, 17, 19, 20, 23, 25, 26, 28, 29, 31, 32, 34, 35, 37, 38, 40, 41, 43, 46, 47, 49, 50, 52, 53, 56, 58, 59, 61, 62, 64, 65, 67, 68, 70, 71, 73, 74, 76, 79, 80, 82, 83, 85, 86, 89, 91, 92, 94, 95, 97, 98]
1041
1042        AUTHORS:
1043            -- Naqi Jaffery (2006-01-24): examples
1044        """
1045        # TODO -- make VASTLY faster
1046        v = []
1047        for n in range(1,m):
1048            if self.gcd(n) == 1:
1049                v.append(Integer(n))
1050        return v
1051
1052    def divides(self, n):
1053        """
1054        Return True if self divides n.
1055
1056        EXAMPLES:
1057            sage: Z = IntegerRing()
1058            sage: Z(5).divides(Z(10))
1059            True
1060            sage: Z(0).divides(Z(5))
1061            False
1062            sage: Z(10).divides(Z(5))
1063            False
1064        """
1065        cdef int t
1066        cdef Integer _n
1067        _n = Integer(n)
1068        if mpz_cmp_si(self.value, 0) == 0:
1069            return bool(mpz_cmp_si(_n.value, 0) == 0)
1070        _sig_on
1071        t = mpz_divisible_p(_n.value, self.value)
1072        _sig_off
1073        return bool(t)
1074   
1075   
1076    def valuation(self, p):
1077        if self == 0:
1078            return sage.rings.infinity.infinity
1079        cdef int k
1080        k = 0
1081        while self % p == 0:
1082            k = k + 1
1083            self = self.__floordiv__(p)
1084        return Integer(k)
1085       
1086    def _lcm(self, Integer n):
1087        """
1088        Returns the least common multiple of self and $n$.
1089        """
1090        cdef mpz_t x
1091
1092        mpz_init(x)
1093
1094        _sig_on
1095        mpz_lcm(x, self.value, n.value)
1096        _sig_off
1097
1098       
1099        cdef Integer z
1100        z = Integer()
1101        mpz_set(z.value,x)
1102        mpz_clear(x)
1103        return z
1104       
1105    def denominator(self):
1106        """
1107        Return the denominator of this integer.
1108
1109        EXAMPLES:
1110            sage: x = 5
1111            sage: x.denominator()
1112            1
1113            sage: x = 0
1114            sage: x.denominator()
1115            1
1116        """
1117        return ONE
1118
1119    def numerator(self):
1120        """
1121        Return the numerator of this integer.
1122
1123        EXAMPLE:
1124            sage: x = 5
1125            sage: x.numerator()
1126            5
1127
1128            sage: x = 0
1129            sage: x.numerator()
1130            0
1131        """
1132        return self
1133
1134    def factorial(self):
1135        """
1136        Return the factorial $n!=1 \\cdot 2 \\cdot 3 \\cdots n$.
1137        Self must fit in an \\code{unsigned long int}.
1138
1139        EXAMPLES:
1140        """
1141        if self < 0:
1142            raise ValueError, "factorial -- self = (%s) must be nonnegative"%self
1143
1144        if mpz_cmp_ui(self.value,4294967295) > 0:
1145            raise ValueError, "factorial not implemented for n >= 2^32.\nThis is probably OK, since the answer would have billions of digits."
1146
1147        cdef unsigned int n
1148        n = self
1149
1150        cdef mpz_t x
1151        cdef Integer z
1152
1153        mpz_init(x)
1154
1155        _sig_on
1156        mpz_fac_ui(x, n)
1157        _sig_off
1158
1159        z = Integer()
1160        set_mpz(z, x)
1161        mpz_clear(x)
1162        return z
1163
1164    def is_one(self):
1165        """
1166        Returns \\code{True} if the integers is $1$, otherwise \\code{False}.
1167
1168        EXAMPLES:
1169            sage: Integer(1).is_one()
1170            True
1171            sage: Integer(0).is_one()
1172            False
1173        """
1174        return bool(mpz_cmp_si(self.value, 1) == 0)
1175
1176    def is_zero(self):
1177        """
1178        Returns \\code{True} if the integers is $0$, otherwise \\code{False}.
1179
1180        EXAMPLES:
1181            sage: Integer(1).is_zero()
1182            False
1183            sage: Integer(0).is_zero()
1184            True
1185        """
1186        return bool(mpz_cmp_si(self.value, 0) == 0)
1187
1188    def is_unit(self):
1189        """
1190        Returns \\code{true} if this integer is a unit, i.e., 1 or $-1$.
1191        """
1192        return bool(mpz_cmp_si(self.value, -1) == 0 or mpz_cmp_si(self.value, 1) == 0)
1193
1194    def is_square(self):
1195        r"""
1196        Returns \code{True} if self is a perfect square
1197
1198        EXAMPLES:
1199            sage: Integer(4).is_square()
1200            True
1201            sage: Integer(41).is_square()
1202            False
1203        """
1204        return bool(self._pari_().issquare())
1205
1206    def is_prime(self):
1207        r"""
1208        Retuns \code{True} if self is prime
1209
1210        EXAMPLES:
1211            sage: z = 2^31 - 1
1212            sage: z.is_prime()
1213            True
1214            sage: z = 2^31
1215            sage: z.is_prime()
1216            False
1217        """
1218        return bool(self._pari_().isprime())
1219
1220    def square_free_part(self):
1221        """
1222        Return the square free part of $x$, i.e., a divisor z such that $x = z y^2$,
1223        for a perfect square $y^2$.
1224
1225        EXAMPLES:
1226            sage: square_free_part(100)
1227            1
1228            sage: square_free_part(12)
1229            3
1230            sage: square_free_part(17*37*37)
1231            17
1232            sage: square_free_part(-17*32)
1233            -34
1234            sage: square_free_part(1)
1235            1
1236            sage: square_free_part(-1)
1237            -1
1238            sage: square_free_part(-2)
1239            -2
1240            sage: square_free_part(-4)
1241            -1
1242        """
1243        if self.is_zero():
1244            return self
1245        F = self.factor()
1246        n = Integer(1)
1247        for p, e in F:
1248            if e % 2 != 0:
1249                n = n * p
1250        return n * F.unit()
1251
1252    def next_prime(self):
1253        r"""
1254        Returns the next prime after self
1255
1256        EXAMPLES:
1257            sage: Integer(100).next_prime()
1258            101
1259            sage: Integer(0).next_prime()
1260            2
1261            sage: Integer(1001).next_prime()
1262            1009
1263        """
1264        return Integer( (self._pari_()+1).nextprime())
1265
1266    def additive_order(self):
1267        """
1268        Return the additive order of self.
1269
1270        EXAMPLES:
1271            sage: ZZ(0).additive_order()
1272            1
1273            sage: ZZ(1).additive_order()
1274            Infinity
1275        """
1276        import sage.rings.infinity
1277        if self.is_zero():
1278            return Integer(1)
1279        else:
1280            return sage.rings.infinity.infinity
1281
1282    def multiplicative_order(self):
1283        r"""
1284        Return the multiplicative order of self, if self is a unit, or raise
1285        \code{ArithmeticError} otherwise.
1286
1287        EXAMPLES:
1288            sage: ZZ(1).multiplicative_order()
1289            1
1290            sage: ZZ(-1).multiplicative_order()
1291            2
1292            sage: ZZ(0).multiplicative_order()
1293            Traceback (most recent call last):
1294            ...
1295            ArithmeticError: no power of 0 is a unit
1296            sage: ZZ(2).multiplicative_order()
1297            Traceback (most recent call last):
1298            ...
1299            ArithmeticError: no power of 2 is a unit
1300        """
1301        if mpz_cmp_si(self.value, 1) == 0:
1302            return Integer(1)
1303        elif mpz_cmp_si(self.value, -1) == 0:
1304            return Integer(2)
1305        else:
1306            raise ArithmeticError, "no power of %s is a unit"%self
1307
1308    def is_squarefree(self):
1309        """
1310        Returns True if this integer is not divisible by the square of
1311        any prime and False otherwise.
1312
1313        EXAMPLES:
1314            sage: Integer(100).is_squarefree()
1315            False
1316            sage: Integer(102).is_squarefree()
1317            True
1318        """
1319        return self._pari_().issquarefree()
1320
1321    def _pari_(self):
1322        if self._pari is None:
1323            # better to do in hex, but I can't figure out
1324            # how to input/output a number in hex in PARI!!
1325            # TODO: (I could just think carefully about raw bytes and make this all much faster...)
1326            self._pari = sage.libs.pari.all.pari(str(self))
1327        return self._pari
1328
1329    def _interface_init_(self):
1330        return str(self)
1331
1332    def parent(self):
1333        """
1334        Return the ring $\\Z$ of integers.
1335        """
1336        return sage.rings.integer_ring.Z
1337
1338    def isqrt(self):
1339        """
1340        Returns the integer floor of the square root of self, or raises
1341        an \\exception{ValueError} if self is negative.
1342       
1343        EXAMPLE:
1344            sage: a = Integer(5)
1345            sage: a.isqrt()
1346            2
1347
1348            sage: Integer(-102).isqrt()
1349            Traceback (most recent call last):
1350            ...
1351            ValueError: square root of negative number not defined.
1352        """
1353        if self < 0:
1354            raise ValueError, "square root of negative number not defined."
1355        cdef Integer x
1356        x = Integer()
1357
1358        _sig_on
1359        mpz_sqrt(x.value, self.value)
1360        _sig_off
1361       
1362        return x
1363
1364    def _mpfr_(self, R):
1365        return R(self.str(32), 32) 
1366       
1367   
1368    def sqrt(self, bits=None):
1369        r"""
1370        Returns the positive square root of self, possibly as a
1371        \emph{a real or complex number} if self is not a perfect
1372        integer square.
1373
1374        INPUT:
1375            bits -- number of bits of precision.
1376                    If bits is not specified, the number of
1377                    bits of precision is at least twice the
1378                    number of bits of self (the precision
1379                    is always at least 53 bits if not specified).
1380        OUTPUT:
1381            integer, real number, or complex number.
1382
1383        For the guaranteed integer square root of a perfect square
1384        (with error checking), use \code{self.square_root()}.
1385       
1386        EXAMPLE:
1387            sage: Z = IntegerRing()
1388            sage: Z(4).sqrt()
1389            2
1390            sage: Z(4).sqrt(53)
1391            2.0000000000000000
1392            sage: Z(2).sqrt(53)
1393            1.4142135623730951
1394            sage: Z(2).sqrt(100)
1395            1.4142135623730950488016887242092
1396            sage: n = 39188072418583779289; n.square_root()
1397            6260037733
1398            sage: (100^100).sqrt()
1399            10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
1400            sage: (-1).sqrt()
1401            1.0000000000000000*I
1402            sage: sqrt(-2)
1403            1.4142135623730951*I
1404            sage: sqrt(97)
1405            9.8488578017961039
1406            sage: n = 97; n.sqrt(200)
1407            9.8488578017961047217462114149176244816961362874427641717231516
1408        """
1409        if bits is None:
1410            try:
1411                return self.square_root()
1412            except ValueError:
1413                pass
1414            bits = max(53, 2*(mpz_sizeinbase(self.value, 2)+2))
1415           
1416        if self < 0:
1417            x = sage.rings.complex_field.ComplexField(bits)(self)
1418            return x.sqrt()
1419        else:
1420            R = mpfr.RealField(bits)
1421            return self._mpfr_(R).sqrt()
1422
1423    def square_root(self):
1424        """
1425        Return the positive integer square root of self, or raises a ValueError
1426        if self is not a perfect square.
1427
1428        EXAMPLES:
1429            sage: Integer(144).square_root()
1430            12
1431            sage: Integer(102).square_root()
1432            Traceback (most recent call last):
1433            ...
1434            ValueError: self (=102) is not a perfect square
1435        """
1436        n = self.isqrt()
1437        if n * n == self:
1438            return n
1439        raise ValueError, "self (=%s) is not a perfect square"%self
1440           
1441
1442    def _xgcd(self, Integer n):
1443        """
1444        Return a triple $g, s, t \\in\\Z$ such that
1445        $$
1446           g = s \\cdot \\mbox{\\rm self} + t \\cdot n.
1447        $$
1448        """
1449        cdef mpz_t g, s, t
1450        cdef object g0, s0, t0
1451       
1452        mpz_init(g)
1453        mpz_init(s)
1454        mpz_init(t)
1455
1456        _sig_on
1457        mpz_gcdext(g, s, t, self.value, n.value)
1458        _sig_off
1459       
1460        g0 = Integer()
1461        s0 = Integer()
1462        t0 = Integer()
1463        set_mpz(g0,g)
1464        set_mpz(s0,s)
1465        set_mpz(t0,t)
1466        mpz_clear(g)
1467        mpz_clear(s)
1468        mpz_clear(t)
1469        return g0, s0, t0
1470
1471    def _lshift(self, unsigned long int n):
1472        cdef Integer x
1473        x = Integer()
1474
1475        _sig_on
1476        mpz_mul_2exp(x.value, self.value, n)
1477        _sig_off
1478        return x
1479       
1480    def __lshift__(x,y):
1481        """
1482        EXAMPLES:
1483            sage: 32 << 2
1484            128
1485            sage: 32 << int(2)
1486            128
1487            sage: int(32) << 2
1488            128
1489        """
1490        if isinstance(x, Integer) and isinstance(y, (Integer, int, long)):
1491            return x._lshift(long(y))
1492        return sage.rings.coerce.bin_op(x, y, operator.lshift)
1493   
1494    def _rshift(Integer self, unsigned long int n):
1495        cdef Integer x
1496        x = Integer()
1497        _sig_on
1498        mpz_fdiv_q_2exp(x.value, self.value, n)
1499        _sig_off
1500        return x
1501   
1502    def __rshift__(x, y):
1503        """
1504        EXAMPLES:
1505            sage: 32 >> 2
1506            8
1507            sage: 32 >> int(2)
1508            8
1509            sage: int(32) >> 2
1510            8
1511        """
1512        if isinstance(x, Integer) and isinstance(y, (Integer, int, long)):
1513            return x._rshift(long(y))
1514        return sage.rings.coerce.bin_op(x, y, operator.rshift)
1515       
1516    def _and(Integer self, Integer other):
1517        cdef Integer x
1518        x = Integer()
1519        mpz_and(x.value, self.value, other.value)
1520        return x
1521
1522    def __and__(x, y):
1523        if isinstance(x, Integer) and isinstance(y, Integer):
1524            return x._and(y)
1525        return sage.rings.coerce.bin_op(x, y, operator.and_)
1526
1527
1528    def _or(Integer self, Integer other):
1529        cdef Integer x
1530        x = Integer()
1531        mpz_ior(x.value, self.value, other.value)
1532        return x
1533
1534    def __or__(x, y):
1535        if isinstance(x, Integer) and isinstance(y, Integer):
1536            return x._or(y)
1537        return sage.rings.coerce.bin_op(x, y, operator.or_)
1538
1539
1540    def __invert__(self):
1541        """
1542        """
1543        return Integer(1)/self    # todo: optimize
1544       
1545
1546    def inverse_mod(self, n):
1547        """
1548        Returns the inverse of self modulo $n$, if this inverse exists.
1549        Otherwise, raises a \exception{ZeroDivisionError} exception.
1550       
1551        INPUT:
1552           self -- Integer
1553           n -- Integer
1554        OUTPUT:
1555           x -- Integer such that x*self = 1 (mod m), or
1556                raises ZeroDivisionError.
1557        IMPLEMENTATION:
1558           Call the mpz_invert GMP library function.
1559        EXAMPLES:
1560            sage: a = Integer(189)
1561            sage: a.inverse_mod(10000)
1562            4709
1563            sage: a.inverse_mod(-10000)
1564            4709
1565            sage: a.inverse_mod(1890)
1566            Traceback (most recent call last):
1567            ...
1568            ZeroDivisionError: Inverse does not exist.
1569            sage: a = Integer(19)**100000
1570            sage: b = a*a
1571            sage: c = a.inverse_mod(b)
1572            Traceback (most recent call last):
1573            ...
1574            ZeroDivisionError: Inverse does not exist.
1575        """
1576        cdef mpz_t x
1577        cdef object ans
1578        cdef int r
1579        cdef Integer m
1580        m = Integer(n)
1581
1582        if m == 1:
1583            return Integer(0)
1584
1585        mpz_init(x)
1586
1587        _sig_on
1588        r = mpz_invert(x, self.value, m.value)
1589        _sig_off
1590       
1591        if r == 0:
1592            raise ZeroDivisionError, "Inverse does not exist."
1593        ans = Integer()
1594        set_mpz(ans,x)
1595        mpz_clear(x)
1596        return ans
1597       
1598    def _gcd(self, Integer n):
1599        """
1600        Return the greatest common divisor of self and $n$.
1601
1602        EXAMPLE:
1603            sage: gcd(-1,1)
1604            1
1605            sage: gcd(0,1)
1606            1
1607            sage: gcd(0,0)
1608            0
1609            sage: gcd(2,2^6)
1610            2
1611            sage: gcd(21,2^6)
1612            1
1613        """
1614        cdef mpz_t g
1615        cdef object g0
1616
1617        mpz_init(g)
1618       
1619
1620        _sig_on
1621        mpz_gcd(g, self.value, n.value)
1622        _sig_off
1623
1624        g0 = Integer()
1625        set_mpz(g0,g)
1626        mpz_clear(g)
1627        return g0
1628
1629    def crt(self, y, m, n):
1630        """
1631        Return the unique integer between $0$ and $mn$ that is
1632        congruent to the integer modulo $m$ and to $y$ modulo $n$.  We
1633        assume that~$m$ and~$n$ are coprime.
1634        """
1635        cdef object g, s, t
1636        cdef Integer _y, _m, _n
1637        _y = Integer(y); _m = Integer(m); _n = Integer(n)
1638        g, s, t = _m.xgcd(_n)
1639        if not g.is_one():
1640            raise ArithmeticError, "CRT requires that gcd of moduli is 1."
1641        # Now s*m + t*n = 1, so the answer is x + (y-x)*s*m, where x=self.
1642        return (self + (_y-self)*s*_m) % (_m*_n)
1643
1644    def test_bit(self, index):
1645        r"""
1646        Return the bit at \code{index}
1647
1648        EXAMPLES:
1649            sage: w = 6
1650            sage: w.str(2)
1651            '110'
1652            sage: w.test_bit(2)
1653            1
1654            sage: w.test_bit(-1)
1655            0
1656        """
1657        cdef unsigned long int i
1658        i = index
1659        cdef Integer x
1660        x = Integer(self)
1661        return mpz_tstbit(x.value, i)
1662
1663
1664ONE = Integer(1)
1665
1666def integer(x):
1667    if isinstance(x, Integer):
1668        return x
1669    return Integer(x)
1670
1671
1672def LCM_list(v):
1673    cdef int i, n
1674    cdef mpz_t z
1675    cdef Integer w
1676   
1677    n = len(v)
1678
1679    if n == 0:
1680        return Integer(1)
1681
1682    try:
1683        w = v[0]
1684        mpz_init_set(z, w.value)
1685
1686        _sig_on
1687        for i from 1 <= i < n:
1688            w = v[i]
1689            mpz_lcm(z, z, w.value)
1690        _sig_off
1691    except TypeError:
1692        w = Integer(v[0])
1693        mpz_init_set(z, w.value)
1694
1695        _sig_on
1696        for i from 1 <= i < n:
1697            w = Integer(v[i])
1698            mpz_lcm(z, z, w.value)
1699        _sig_off
1700       
1701   
1702    w = Integer()
1703    mpz_set(w.value, z)
1704    mpz_clear(z)
1705    return w
1706
1707
1708
1709def GCD_list(v):
1710    cdef int i, n
1711    cdef mpz_t z
1712    cdef Integer w
1713   
1714    n = len(v)
1715
1716    if n == 0:
1717        return Integer(1)
1718
1719    try:
1720        w = v[0]
1721        mpz_init_set(z, w.value)
1722
1723        _sig_on
1724        for i from 1 <= i < n:
1725            w = v[i]
1726            mpz_gcd(z, z, w.value)
1727            if mpz_cmp_si(z, 1) == 0:
1728                _sig_off
1729                return Integer(1)
1730        _sig_off
1731    except TypeError:
1732        w = Integer(v[0])
1733        mpz_init_set(z, w.value)
1734
1735        _sig_on
1736        for i from 1 <= i < n:
1737            w = Integer(v[i])
1738            mpz_gcd(z, z, w.value)
1739            if mpz_cmp_si(z, 1) == 0:
1740                _sig_off
1741                return Integer(1)
1742        _sig_off
1743
1744   
1745    w = Integer()
1746    mpz_set(w.value, z)
1747    mpz_clear(z)
1748    return w
Note: See TracBrowser for help on using the repository browser.