Coverage for local/lib/python2.7/site-packages/sage/rings/integer.pyx : 79%
Hot-keys on this page
r m x p toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
|
r""" Elements of the ring `\ZZ` of integers
Sage has highly optimized and extensive functionality about arithmetic with integers and the ring of integers.
- Vincent Delecroix (2017-05-03): faster integer-rational comparisons
EXAMPLES:
Add 2 integers::
sage: a = Integer(3) ; b = Integer(4) sage: a + b == 7 True
Add an integer and a real number::
sage: a + 4.0 7.00000000000000
Add an integer and a rational number::
sage: a + Rational(2)/5 17/5
Add an integer and a complex number::
sage: b = ComplexField().0 + 1.5 sage: loads((a+b).dumps()) == a+b True
sage: z = 32 sage: -z -32 sage: z = 0; -z 0 sage: z = -0; -z 0 sage: z = -1; -z 1
Multiplication::
sage: a = Integer(3) ; b = Integer(4) sage: a * b == 12 True sage: loads((a * 4.0).dumps()) == a*b True sage: a * Rational(2)/5 6/5
::
sage: list([2,3]) * 4 [2, 3, 2, 3, 2, 3, 2, 3]
::
sage: 'sage'*Integer(3) 'sagesagesage'
COERCIONS:
Returns version of this integer in the multi-precision floating real field R::
sage: n = 9390823 sage: RR = RealField(200) sage: RR(n) 9.3908230000000000000000000000000000000000000000000000000000e6
AUTHORS:
- William Stein (2005): initial version
- Gonzalo Tornaria (2006-03-02): vastly improved python/GMP conversion; hashing
- Didier Deshommes (2006-03-06): numerous examples and docstrings
- William Stein (2006-03-31): changes to reflect GMP bug fixes
- William Stein (2006-04-14): added GMP factorial method (since it's now very fast).
- David Harvey (2006-09-15): added nth_root, exact_log
- David Harvey (2006-09-16): attempt to optimise Integer constructor
- Rishikesh (2007-02-25): changed quo_rem so that the rem is positive
- David Harvey, Martin Albrecht, Robert Bradshaw (2007-03-01): optimized Integer constructor and pool
- Pablo De Napoli (2007-04-01): multiplicative_order should return +infinity for non zero numbers
- Robert Bradshaw (2007-04-12): is_perfect_power, Jacobi symbol (with Kronecker extension). Convert some methods to use GMP directly rather than PARI, Integer(), PY_NEW(Integer)
- David Roe (2007-03-21): sped up valuation and is_square, added val_unit, is_power, is_power_of and divide_knowing_divisible_by
- Robert Bradshaw (2008-03-26): gamma function, multifactorials
- Robert Bradshaw (2008-10-02): bounded squarefree part
- David Loeffler (2011-01-15): fixed bug #10625 (inverse_mod should accept an ideal as argument)
- Vincent Delecroix (2010-12-28): added unicode in Integer.__init__
- David Roe (2012-03): deprecate :meth:`~sage.rings.integer.Integer.is_power` in favour of :meth:`~sage.rings.integer.Integer.is_perfect_power` (see :trac:`12116`)
- Vincent Klein (2017-05-11): add __mpz__() to class Integer
- Vincent Klein (2017-05-22): Integer constructor support gmpy2.mpz parameter """ #***************************************************************************** # Copyright (C) 2004,2006 William Stein <wstein@gmail.com> # Copyright (C) 2006 Gonzalo Tornaria <tornaria@math.utexas.edu> # Copyright (C) 2006 Didier Deshommes <dfdeshom@gmail.com> # Copyright (C) 2007 David Harvey <dmharvey@math.harvard.edu> # Copyright (C) 2007 Martin Albrecht <malb@informatik.uni-bremen.de> # Copyright (C) 2007,2008 Robert Bradshaw <robertwb@math.washington.edu> # Copyright (C) 2007 David Roe <roed314@gmail.com> # Copyright (C) 2017 Vincent Delecroix <20100.delecroix@gmail.com> # # Distributed under the terms of the GNU General Public License (GPL) # as published by the Free Software Foundation; either version 2 of # the License, or (at your option) any later version. # http://www.gnu.org/licenses/ #*****************************************************************************
from __future__ import absolute_import, print_function
# Do not create any Integer, especially non cdef'ed ones, before the hooked # creation and deletion are setup by the call to hook_fast_tp_functions
cimport cython from libc.math cimport (ldexp, sqrt as sqrt_double, log as log_c, ceil as ceil_c, isnan) from libc.string cimport memcpy cdef extern from "<limits.h>": const long LONG_MAX # Work around https://github.com/cython/cython/pull/2016
from cysignals.memory cimport check_allocarray, check_malloc, sig_free from cysignals.signals cimport sig_on, sig_off
import operator import sys
from sage.ext.stdsage cimport PY_NEW from sage.cpython.python_debug cimport if_Py_TRACE_REFS_then_PyObject_INIT
from sage.libs.gmp.mpz cimport * from sage.libs.gmp.mpq cimport * from sage.misc.superseded import deprecated_function_alias from sage.cpython.string cimport char_to_str, str_to_bytes from sage.arith.long cimport (pyobject_to_long, integer_check_long, integer_check_long_py)
from cpython.list cimport * from cpython.number cimport * from cpython.int cimport * from cpython.object cimport * from libc.stdint cimport uint64_t cimport sage.structure.element from sage.structure.element cimport (Element, EuclideanDomainElement, parent, coercion_model) from sage.structure.parent cimport Parent from cypari2.paridecl cimport * from sage.rings.rational cimport Rational from sage.arith.rational_reconstruction cimport mpq_rational_reconstruction from sage.libs.gmp.pylong cimport * from sage.libs.ntl.convert cimport mpz_to_ZZ from sage.libs.gmp.mpq cimport mpq_neg
from cypari2.gen cimport objtogen, Gen as pari_gen from sage.libs.pari.convert_gmp cimport INT_to_mpz, new_gen_from_mpz_t from cypari2.stack cimport new_gen from sage.libs.flint.ulong_extras cimport *
import sage.rings.infinity
from sage.structure.coerce cimport is_numpy_type from sage.structure.element import coerce_binop
from sage.libs.gmp.binop cimport mpq_add_z, mpq_mul_z, mpq_div_zz
IF HAVE_GMPY2: cimport gmpy2 gmpy2.import_gmpy2()
cdef extern from *: int unlikely(int) nogil # Defined by Cython
cdef object numpy_long_interface = {'typestr': '=i4' if sizeof(long) == 4 else '=i8' } cdef object numpy_int64_interface = {'typestr': '=i8'} cdef object numpy_object_interface = {'typestr': '|O'}
cdef set_from_Integer(Integer self, Integer other):
cdef set_from_pari_gen(Integer self, pari_gen x): r""" EXAMPLES::
sage: [Integer(pari(x)) for x in [1, 2^60, 2., GF(3)(1), GF(9,'a')(2)]] [1, 1152921504606846976, 2, 1, 2] sage: Integer(pari(2.1)) # indirect doctest Traceback (most recent call last): ... TypeError: Attempt to coerce non-integral real number to an Integer """ # Simplify and lift until we get an integer elif paritype == t_REAL: # Check that the fractional part is zero # floor yields an integer elif paritype == t_PADIC: # Lifting a PADIC yields an integer x = x.lift() break elif paritype == t_INTMOD: # Lifting an INTMOD yields an integer elif paritype == t_POLMOD: elif paritype == t_FFELT: # x = (f modulo defining polynomial of finite field); # we extract f. else:
# Now we have a true PARI integer, convert it to Sage
cdef _digits_naive(mpz_t v,l,int offset,Integer base,digits): """ This method fills in digit entries in the list, l, using the most basic digit algorithm -- repeat division by base.
INPUT:
- ``v`` - the value whose digits we want to put into the list
- ``l`` - the list to file
- ``offset`` - offset from the beginning of the list that we want to fill at
- ``base`` -- the base to which we finding digits
- ``digits`` - a python sequence type with objects to use for digits note that python negative index semantics are relied upon
AUTHORS:
- Joel B. Mohler (2009-01-16) """ cdef mpz_t mpz_value cdef mpz_t mpz_res # used on one side of the 'if' cdef Integer z # used on the other side of the 'if'
# we aim to avoid sage Integer creation if possible else:
cdef _digits_internal(mpz_t v,l,int offset,int power_index,power_list,digits): """ INPUT:
- ``v`` - the value whose digits we want to put into the list
- ``l`` - the list to file
- ``offset`` - offset from the beginning of the list that we want to fill at
- ``power_index`` - a measure of size to fill and index to power_list we're filling 1 << (power_index+1) digits
- ``power_list`` - a list of powers of the base, precomputed in method digits digits - a python sequence type with objects to use for digits note that python negative index semantics are relied upon
AUTHORS:
- Joel B. Mohler (2008-03-13) """ cdef mpz_t mpz_res cdef mpz_t mpz_quot cdef Integer temp cdef int v_int # It turns out that simple repeated division is very fast for # relatively few digits. I don't think this is a real algorithmic # statement, it's an annoyance introduced by memory allocation. # I think that manual memory management with mpn_* would make the # divide & conquer approach even faster, but the code would be much # more complicated. else:
from sage.structure.sage_object cimport SageObject from sage.structure.richcmp cimport rich_to_bool_sgn
from sage.structure.element cimport EuclideanDomainElement, ModuleElement, Element from sage.structure.element import bin_op from sage.structure.coerce_exceptions import CoercionException
from . import integer_ring cdef Parent the_integer_ring = integer_ring.ZZ
# The documentation for the ispseudoprime() function in the PARI # manual states that its result is always prime up to this 2^64. cdef mpz_t PARI_PSEUDOPRIME_LIMIT mpz_init(PARI_PSEUDOPRIME_LIMIT) mpz_ui_pow_ui(PARI_PSEUDOPRIME_LIMIT, 2, 64)
def is_Integer(x): """ Return true if x is of the Sage integer type.
EXAMPLES::
sage: from sage.rings.integer import is_Integer sage: is_Integer(2) True sage: is_Integer(2/1) False sage: is_Integer(int(2)) False sage: is_Integer(long(2)) False sage: is_Integer('5') False """
cdef inline Integer as_Integer(x): else:
cdef class IntegerWrapper(Integer): r""" Rationale for the ``IntegerWrapper`` class:
With ``Integers``, the allocation/deallocation function slots are hijacked with custom functions that stick already allocated ``Integers`` (with initialized ``parent`` and ``mpz_t`` fields) into a pool on "deallocation" and then pull them out whenever a new one is needed. Because ``Integers`` are so common, this is actually a significant savings. However , this does cause issues with subclassing a Python class directly from ``Integer`` (but that's ok for a Cython class).
As a workaround, one can instead derive a class from the intermediate class ``IntegerWrapper``, which sets statically its alloc/dealloc methods to the *original* ``Integer`` alloc/dealloc methods, before they are swapped manually for the custom ones.
The constructor of ``IntegerWrapper`` further allows for specifying an alternative parent to ``IntegerRing()``. """
def __init__(self, parent=None, x=None, unsigned int base=0): """ We illustrate how to create integers with parents different from ``IntegerRing()``::
sage: from sage.rings.integer import IntegerWrapper
sage: n = IntegerWrapper(Primes(), 3) # indirect doctest sage: n 3 sage: n.parent() Set of all prime numbers: 2, 3, 5, 7, ...
Pickling seems to work now (as of :trac:`10314`)::
sage: nn = loads(dumps(n)) sage: nn 3 sage: nn.parent() Integer Ring
sage: TestSuite(n).run() """
cdef class Integer(sage.structure.element.EuclideanDomainElement): r""" The ``Integer`` class represents arbitrary precision integers. It derives from the ``Element`` class, so integers can be used as ring elements anywhere in Sage.
Integer() interprets strings that begin with ``0o`` as octal numbers, strings that begin with ``0x`` as hexadecimal numbers and strings that begin with ``0b`` as binary numbers.
The class ``Integer`` is implemented in Cython, as a wrapper of the GMP ``mpz_t`` integer type.
EXAMPLES::
sage: Integer(123) 123 sage: Integer("123") 123
Sage Integers support :pep:`3127` literals::
sage: Integer('0x12') 18 sage: Integer('-0o12') -10 sage: Integer('+0b101010') 42
Conversion from PARI::
sage: Integer(pari('-10380104371593008048799446356441519384')) -10380104371593008048799446356441519384 sage: Integer(pari('Pol([-3])')) -3
Conversion from gmpy2::
sage: from gmpy2 import mpz # optional - gmpy2 sage: Integer(mpz(3)) # optional - gmpy2 3
.. automethod:: __pow__ """
def __cinit__(self): global the_integer_ring
def __init__(self, x=None, base=0): """ EXAMPLES::
sage: a = long(-901824309821093821093812093810928309183091832091) sage: b = ZZ(a); b -901824309821093821093812093810928309183091832091 sage: ZZ(b) -901824309821093821093812093810928309183091832091 sage: ZZ('-901824309821093821093812093810928309183091832091') -901824309821093821093812093810928309183091832091 sage: ZZ(int(-93820984323)) -93820984323 sage: ZZ(ZZ(-901824309821093821093812093810928309183091832091)) -901824309821093821093812093810928309183091832091 sage: ZZ(QQ(-901824309821093821093812093810928309183091832091)) -901824309821093821093812093810928309183091832091 sage: ZZ(RR(2.0)^80) 1208925819614629174706176 sage: ZZ(QQbar(sqrt(28-10*sqrt(3)) + sqrt(3))) 5 sage: ZZ(AA(32).nth_root(5)) 2 sage: ZZ(pari('Mod(-3,7)')) 4 sage: ZZ('sage') Traceback (most recent call last): ... TypeError: unable to convert 'sage' to an integer sage: Integer('zz',36).str(36) 'zz' sage: ZZ('0x3b').str(16) '3b' sage: ZZ( ZZ(5).digits(3) , 3) 5 sage: import numpy sage: ZZ(numpy.int64(7^7)) 823543 sage: ZZ(numpy.ubyte(-7)) 249 sage: ZZ(True) 1 sage: ZZ(False) 0 sage: ZZ(1==0) 0 sage: ZZ('+10') 10 sage: from gmpy2 import mpz # optional - gmpy2 sage: ZZ(mpz(42)) # optional - gmpy2 42
::
sage: k = GF(2) sage: ZZ( (k(0),k(1)), 2) 2
::
sage: ZZ(float(2.0)) 2 sage: ZZ(float(1.0/0.0)) Traceback (most recent call last): ... OverflowError: cannot convert float infinity to integer sage: ZZ(float(0.0/0.0)) Traceback (most recent call last): ... ValueError: cannot convert float NaN to integer
::
sage: class MyInt(int): ....: pass sage: class MyLong(long): ....: pass sage: class MyFloat(float): ....: pass sage: ZZ(MyInt(3)) 3 sage: ZZ(MyLong(4)) 4 sage: ZZ(MyFloat(5)) 5
::
sage: Integer(u'0') 0 sage: Integer(u'0X2AEEF') 175855
Test conversion from PARI (:trac:`11685`)::
sage: ZZ(pari(-3)) -3 sage: ZZ(pari("-3.0")) -3 sage: ZZ(pari("-3.5")) Traceback (most recent call last): ... TypeError: Attempt to coerce non-integral real number to an Integer sage: ZZ(pari("1e100")) Traceback (most recent call last): ... PariError: precision too low in truncr (precision loss in truncation) sage: ZZ(pari("10^50")) 100000000000000000000000000000000000000000000000000 sage: ZZ(pari("Pol(3)")) 3 sage: ZZ(GF(3^20,'t')(1)) 1 sage: ZZ(pari(GF(3^20,'t')(1))) 1 sage: x = polygen(QQ) sage: K.<a> = NumberField(x^2+3) sage: ZZ(a^2) -3 sage: ZZ(pari(a)^2) -3 sage: ZZ(pari("Mod(x, x^3+x+1)")) # Note error message refers to lifted element Traceback (most recent call last): ... TypeError: Unable to coerce PARI x to an Integer
Test coercion of p-adic with negative valuation::
sage: ZZ(pari(Qp(11)(11^-7))) Traceback (most recent call last): ... TypeError: Cannot convert p-adic with negative valuation to an integer
Test converting a list with a very large base::
sage: a=ZZ(randint(0,2^128-1)) sage: L = a.digits(2^64) sage: a == sum([x * 2^(64*i) for i,x in enumerate(L)]) True sage: a == ZZ(L,base=2^64) True
Test comparisons with numpy types (see :trac:`13386` and :trac:`18076`)::
sage: import numpy sage: numpy.int8('12') == 12 True sage: 12 == numpy.int8('12') True
sage: numpy.float('15') == 15 True sage: 15 == numpy.float('15') True """ # TODO: All the code below should somehow be in an external # cdef'd function. Then e.g., if a matrix or vector or # polynomial is getting filled by mpz_t's, it can use the # rules below to do the fill construction of mpz_t's, but # without the overhead of creating any Python objects at all. # The cdef's function should be of the form # mpz_init_set_sage(mpz_t y, object x) # Then this function becomes the one liner: # mpz_init_set_sage(self.value, x)
cdef Integer tmp cdef char* xs cdef int paritype cdef Py_ssize_t j cdef object otmp
cdef Element lift
mpz_set_si(self.value, 0)
else: # First do all the type-check versions (these are fast to test), # except those for which the conversion itself will be slow.
else:
else:
set_from_Integer(self, lift) return pass
# should probably also have fast code for Python ints... # one of the entries was something other than 0 or 1. else:
elif HAVE_GMPY2 and type(x) is gmpy2.mpz: mpz_set(self.value, (<gmpy2.mpz>x).z) return
def __reduce__(self): """ This is used when pickling integers.
EXAMPLES::
sage: n = 5 sage: t = n.__reduce__(); t (<built-in function make_integer>, ('5',)) sage: t[0](*t[1]) 5 sage: loads(dumps(n)) == n True """ # This single line below took me HOURS to figure out. # It is the *trick* needed to pickle Cython extension types. # The trick is that you must put a pure Python function # as the first argument, and that function must return # the result of unpickling with the argument in the second # tuple as input. All kinds of problems happen # if we don't do this.
cdef _reduce_set(self, s): """ Set this integer from a string in base 32.
.. NOTE::
Integers are supposed to be immutable, so you should not use this function. """
def __index__(self): """ Needed so integers can be used as list indices.
EXAMPLES::
sage: v = [1,2,3,4,5] sage: v[Integer(3)] 4 sage: v[Integer(2):Integer(4)] [3, 4]
See :trac:`20750`::
sage: import re sage: p = re.compile('(a)b') sage: m = p.match('ab') sage: m.group(Integer(0)) 'ab' sage: m.group(Integer(1)) 'a' """
def _im_gens_(self, codomain, im_gens): """ Return the image of self under the map that sends the generators of the parent to im_gens. Since ZZ maps canonically in the category of rings, this is just the natural coercion.
EXAMPLES::
sage: n = -10 sage: R = GF(17) sage: n._im_gens_(R, [R(1)]) 7 """
cdef _xor(Integer self, Integer other): cdef Integer x
def __xor__(x, y): """ Compute the exclusive or of x and y.
EXAMPLES::
sage: n = ZZ(2); m = ZZ(3) sage: n.__xor__(m) 1 """
def __richcmp__(left, right, int op): """ cmp for integers
EXAMPLES::
sage: 2 < 3 True sage: 2 > 3 False sage: 2 == 3 False sage: 3 > 2 True sage: 3 < 2 False
sage: 1000000000000000000000000000000000000000000000000000.0r==1000000000000000000000000000000000000000000000000000 False sage: 1000000000000000000000000000000000000000000000000000.1r==1000000000000000000000000000000000000000000000000000 False
Canonical coercions are used but non-canonical ones are not.
::
sage: 4 == 4/1 True sage: 4 == '4' False
TESTS::
sage: 3 < 4r True sage: 3r < 4 True sage: 3 >= 4r False sage: 4r <= 3 False sage: 12345678901234567890123456789r == 12345678901234567890123456789 True sage: 12345678901234567890123456788 < 12345678901234567890123456789r True sage: 2 < 2.7r True sage: 4 < 3.1r False sage: -1r < 1 True sage: -1.5r < 3 True sage: Ilist = [-2,-1,0,1,2,12345678901234567890123456788] sage: ilist = [-4r,-1r,0r,1r,2r,5r] sage: llist = [-12345678901234567890123456788r, 12345678901234567890123456788r, 12345678901234567890123456900r] sage: flist = [-21.8r, -1.2r, -.000005r, 0.0r, .999999r, 1000000000000.0r] sage: all([(a < b) == (RR(a) < RR(b)) for (a, b) in zip(Ilist, ilist)]) True sage: all([(a > b) == (RR(a) > RR(b)) for (a, b) in zip(Ilist, ilist)]) True sage: all([(a == b) == (RR(a) == RR(b)) for (a, b) in zip(Ilist, ilist)]) True sage: all([(a <= b) == (RR(a) <= RR(b)) for (a, b) in zip(Ilist, ilist)]) True sage: all([(a >= b) == (RR(a) >= RR(b)) for (a, b) in zip(Ilist, ilist)]) True sage: all([(a != b) == (RR(a) != RR(b)) for (a, b) in zip(Ilist, ilist)]) True sage: all([(a < b) == (RR(a) < RR(b)) for (a, b) in zip(Ilist, llist)]) True sage: all([(a > b) == (RR(a) > RR(b)) for (a, b) in zip(Ilist, llist)]) True sage: all([(a < b) == (RR(a) < RR(b)) for (a, b) in zip(Ilist, flist)]) True sage: all([(a > b) == (RR(a) > RR(b)) for (a, b) in zip(Ilist, flist)]) True
Verify that :trac:`12149` was fixed (and the fix is consistent with Python ints)::
sage: a = int(1); b = 1; n = float('nan') sage: a == n False sage: a == n, b == n (False, False) sage: a != n, b != n, n != b (True, True, True) sage: a < n, b < n, n > b (False, False, False) sage: a > n, b > n, n < b (False, False, False) sage: a <= n, b <= n, n >= b (False, False, False) sage: a >= n, b >= n, n <= b (False, False, False) """ cdef int c cdef double d cdef mpz_t mpz_tmp
# this case should only occur in python 2 else:
cpdef int _cmp_(left, right) except -2: r""" EXAMPLES::
sage: 1._cmp_(2) -1 sage: 0._cmp_(0) 0 sage: (-3**10 + 1)._cmp_(-3**10) 1 """ cdef int c
def __copy__(self): """ Return a copy of the integer.
EXAMPLES::
sage: n = 2 sage: copy(n) 2 sage: copy(n) is n False """ cdef Integer z
def list(self): """ Return a list with this integer in it, to be compatible with the method for number fields.
EXAMPLES::
sage: m = 5 sage: m.list() [5] """
def __dealloc__(self):
def __repr__(self): """ Return string representation of this integer.
EXAMPLES::
sage: n = -5; n.__repr__() '-5' """
def _latex_(self): """ Return latex representation of this integer. This is just the underlying string representation and nothing more. This is called by the latex function.
EXAMPLES::
sage: n = -5; n._latex_() '-5' sage: latex(n) -5 """
def _sympy_(self): """ Convert Sage Integer() to SymPy Integer.
EXAMPLES::
sage: n = 5; n._sympy_() 5 sage: n = -5; n._sympy_() -5 """
def _mathml_(self): """ Return mathml representation of this integer.
EXAMPLES::
sage: mathml(-45) <mn>-45</mn> sage: (-45)._mathml_() '<mn>-45</mn>' """
def __mpz__(self): """ Return a gmpy2 integer
EXAMPLES::
sage: a = 5 sage: a.__mpz__() # optional - gmpy2 mpz(5) sage: from gmpy2 import mpz # optional - gmpy2 sage: mpz(a) # optional - gmpy2 mpz(5)
TESTS::
sage: a.__mpz__(); raise NotImplementedError("gmpy2 is not installed") Traceback (most recent call last): ... NotImplementedError: gmpy2 is not installed """ IF HAVE_GMPY2: return gmpy2.GMPy_MPZ_From_mpz(self.value) ELSE:
def str(self, int base=10): r""" Return the string representation of ``self`` in the given base.
EXAMPLES::
sage: Integer(2^10).str(2) '10000000000' sage: Integer(2^10).str(17) '394'
::
sage: two=Integer(2) sage: two.str(1) Traceback (most recent call last): ... ValueError: base (=1) must be between 2 and 36
::
sage: two.str(37) Traceback (most recent call last): ... ValueError: base (=37) must be between 2 and 36
::
sage: big = 10^5000000 sage: s = big.str() # long time (2s on sage.math, 2014) sage: len(s) # long time (depends on above defn of s) 5000001 sage: s[:10] # long time (depends on above defn of s) '1000000000' """ cdef size_t n cdef char *s
def __format__(self, *args, **kwargs): """ Returns a string representation using Python's Format protocol. Valid format descriptions are exactly those for Python integers.
EXAMPLES::
sage: "{0:#x}; {0:#b}; {0:+05d}".format(ZZ(17)) '0x11; 0b10001; +0017'
"""
def ordinal_str(self): """ Returns a string representation of the ordinal associated to self.
EXAMPLES::
sage: [ZZ(n).ordinal_str() for n in range(25)] ['0th', '1st', '2nd', '3rd', '4th', ... '10th', '11th', '12th', '13th', '14th', ... '20th', '21st', '22nd', '23rd', '24th']
sage: ZZ(1001).ordinal_str() '1001st'
sage: ZZ(113).ordinal_str() '113th' sage: ZZ(112).ordinal_str() '112th' sage: ZZ(111).ordinal_str() '111th'
""" raise ValueError("Negative integers are not ordinals.") else:
def __hex__(self): r""" Return the hexadecimal digits of self in lower case.
.. NOTE::
'0x' is *not* prepended to the result like is done by the corresponding Python function on int or long. This is for efficiency sake--adding and stripping the string wastes time; since this function is used for conversions from integers to other C-library structures, it is important that it be fast.
EXAMPLES::
sage: print(hex(Integer(15))) f sage: print(hex(Integer(16))) 10 sage: print(hex(Integer(16938402384092843092843098243))) 36bb1e3929d1a8fe2802f083 sage: print(hex(long(16938402384092843092843098243))) 0x36bb1e3929d1a8fe2802f083L """
def __oct__(self): r""" Return the digits of self in base 8.
.. NOTE::
'0' is *not* prepended to the result like is done by the corresponding Python function on int or long. This is for efficiency sake--adding and stripping the string wastes time; since this function is used for conversions from integers to other C-library structures, it is important that it be fast.
EXAMPLES::
sage: print(oct(Integer(800))) 1440 sage: print(oct(Integer(8))) 10 sage: print(oct(Integer(-50))) -62 sage: print(oct(Integer(-899))) -1603 sage: print(oct(Integer(16938402384092843092843098243))) 15535436162247215217705000570203
Behavior of Sage integers vs. Python integers::
sage: oct(Integer(10)) '12' sage: oct(int(10)) '012' sage: oct(Integer(-23)) '-27' sage: oct(int(-23)) '-027' """
def binary(self): """ Return the binary digits of self as a string.
EXAMPLES::
sage: print(Integer(15).binary()) 1111 sage: print(Integer(16).binary()) 10000 sage: print(Integer(16938402384092843092843098243).binary()) 1101101011101100011110001110010010100111010001101010001111111000101000000000101111000010000011 """
def bits(self): """ Return the bits in self as a list, least significant first. The result satisfies the identity
::
x == sum(b*2^e for e, b in enumerate(x.bits()))
Negative numbers will have negative "bits". (So, strictly speaking, the entries of the returned list are not really members of `\ZZ/2\ZZ`.)
This method just calls :func:`digits` with ``base=2``.
.. SEEALSO::
:func:`nbits` (number of bits; a faster way to compute ``len(x.bits())``; and :func:`binary`, which returns a string in more-familiar notation.
EXAMPLES::
sage: 500.bits() [0, 0, 1, 0, 1, 1, 1, 1, 1] sage: 11.bits() [1, 1, 0, 1] sage: (-99).bits() [-1, -1, 0, 0, 0, -1, -1] """
def nbits(self): """ Return the number of bits in self.
EXAMPLES::
sage: 500.nbits() 9 sage: 5.nbits() 3 sage: 0.nbits() == len(0.bits()) == 0.ndigits(base=2) True sage: 12345.nbits() == len(12345.binary()) True """ # mpz_sizeinbase(0,2) always returns 1 else:
def trailing_zero_bits(self): """ Return the number of trailing zero bits in self, i.e. the exponent of the largest power of 2 dividing self.
EXAMPLES::
sage: 11.trailing_zero_bits() 0 sage: (-11).trailing_zero_bits() 0 sage: (11<<5).trailing_zero_bits() 5 sage: (-11<<5).trailing_zero_bits() 5 sage: 0.trailing_zero_bits() 0
"""
def digits(self, base=10, digits=None, padto=0): r""" Return a list of digits for ``self`` in the given base in little endian order.
The returned value is unspecified if self is a negative number and the digits are given.
INPUT:
- ``base`` - integer (default: 10)
- ``digits`` - optional indexable object as source for the digits
- ``padto`` - the minimal length of the returned list, sufficient number of zeros are added to make the list minimum that length (default: 0)
As a shorthand for ``digits(2)``, you can use :meth:`.bits`.
Also see :meth:`ndigits`.
EXAMPLES::
sage: 17.digits() [7, 1] sage: 5.digits(base=2, digits=["zero","one"]) ['one', 'zero', 'one'] sage: 5.digits(3) [2, 1] sage: 0.digits(base=10) # 0 has 0 digits [] sage: 0.digits(base=2) # 0 has 0 digits [] sage: 10.digits(16,'0123456789abcdef') ['a'] sage: 0.digits(16,'0123456789abcdef') [] sage: 0.digits(16,'0123456789abcdef',padto=1) ['0'] sage: 123.digits(base=10,padto=5) [3, 2, 1, 0, 0] sage: 123.digits(base=2,padto=3) # padto is the minimal length [1, 1, 0, 1, 1, 1, 1] sage: 123.digits(base=2,padto=10,digits=(1,-1)) [-1, -1, 1, -1, -1, -1, -1, 1, 1, 1] sage: a=9939082340; a.digits(10) [0, 4, 3, 2, 8, 0, 9, 3, 9, 9] sage: a.digits(512) [100, 302, 26, 74] sage: (-12).digits(10) [-2, -1] sage: (-12).digits(2) [0, 0, -1, -1]
We support large bases.
::
sage: n=2^6000 sage: n.digits(2^3000) [0, 0, 1]
::
sage: base=3; n=25 sage: l=n.digits(base) sage: # the next relationship should hold for all n,base sage: sum(base^i*l[i] for i in range(len(l)))==n True sage: base=3; n=-30; l=n.digits(base); sum(base^i*l[i] for i in range(len(l)))==n True
The inverse of this method -- constructing an integer from a list of digits and a base -- can be done using the above method or by simply using :class:`ZZ() <sage.rings.integer_ring.IntegerRing_class>` with a base::
sage: x = 123; ZZ(x.digits(), 10) 123 sage: x == ZZ(x.digits(6), 6) True sage: x == ZZ(x.digits(25), 25) True
Using :func:`sum` and :func:`enumerate` to do the same thing is slightly faster in many cases (and :func:`~sage.misc.misc_c.balanced_sum` may be faster yet). Of course it gives the same result::
sage: base = 4 sage: sum(digit * base^i for i, digit in enumerate(x.digits(base))) == ZZ(x.digits(base), base) True
Note: In some cases it is faster to give a digits collection. This would be particularly true for computing the digits of a series of small numbers. In these cases, the code is careful to allocate as few python objects as reasonably possible.
::
sage: digits = list(range(15)) sage: l = [ZZ(i).digits(15,digits) for i in range(100)] sage: l[16] [1, 1]
This function is comparable to ``str`` for speed.
::
sage: n=3^100000 sage: n.digits(base=10)[-1] # slightly slower than str 1 sage: n=10^10000 sage: n.digits(base=10)[-1] # slightly faster than str 1
AUTHORS:
- Joel B. Mohler (2008-03-02): significantly rewrote this entire function """ cdef Integer _base cdef list power_list cdef list l cdef int i cdef size_t s
else:
raise ValueError("base must be >= 2")
cdef bint do_sig_on else: else: # mpz_tstbit seems to return 0 for the high-order bit of # negative numbers?! else:
# We use a divide and conquer approach (suggested by the prior # author, malb?, of the digits method) here: for base b, compute # b^2, b^4, b^8, ... (repeated squaring) until you get larger # than your number; then compute (n // b^256, n % b^256) # (if b^512 > number) to split the number in half and recurse
# Pre-computing the exact number of digits up-front is actually # faster (especially for large values of self) than trimming off # trailing zeros after the fact. It also seems that it would # avoid duplicating the list in memory with a list-slice.
# set up digits for optimal access once we get inside the worker # functions # list objects have fastest access in the innermost loop # We can get a speed boost by pre-allocating digit values in # big cases. # We do this we have more digits than the base and the base # is not too extremely large (currently, "extremely" means # larger than 10000 -- that's very arbitrary.) else: # All the digits will be negated in the recursive function. # we'll just compensate for python index semantics digits = [Integer(i) for i in range(-_base,0)] digits[0] = the_integer_ring._zero_element
else: # count the bits of s
# Note that it may appear that the recursive calls to # _digit_internal would be assigning list elements i in l for # anywhere from 0<=i<(1<<power_index). However, this is not # the case due to the optimization of skipping assigns # assigning zero.
# padding should be taken care of with-in the function # all we need to do is return
def ndigits(self, base=10): """ Return the number of digits of self expressed in the given base.
INPUT:
- ``base`` - integer (default: 10)
EXAMPLES::
sage: n = 52 sage: n.ndigits() 2 sage: n = -10003 sage: n.ndigits() 5 sage: n = 15 sage: n.ndigits(2) 4 sage: n = 1000**1000000+1 sage: n.ndigits() 3000001 sage: n = 1000**1000000-1 sage: n.ndigits() 3000000 sage: n = 10**10000000-10**9999990 sage: n.ndigits() 10000000 """ cdef Integer temp
else:
cdef void set_from_mpz(Integer self, mpz_t value):
cdef int _to_ZZ(self, ZZ_c *z) except -1:
def __add__(left, right): r""" TESTS::
sage: 1 + 2 3 sage: sum(Integer(i) for i in [1..100]) 5050 sage: 1 + 2/3 5/3 sage: 1 + (-2/3) 1/3 """ cdef Integer x cdef Rational y
cpdef _add_(self, right): """ Integer addition.
TESTS::
sage: 32._add_(23) 55 sage: a = ZZ.random_element(10^50000) sage: b = ZZ.random_element(10^50000) sage: a._add_(b) == b._add_(a) True """ # self and right are guaranteed to be Integers
cdef _add_long(self, long n): """ Fast path for adding a C long.
TESTS::
sage: int(10) + Integer(100) 110 sage: Integer(100) + int(10) 110 sage: Integer(10^100) + int(10) 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010
Also called for subtraction::
sage: Integer(100) - int(10) 90 sage: Integer(10^100) - int(10) 9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999990
Make sure it works when -<long>n would overflow::
sage: most_neg_long = int(-sys.maxsize - 1) sage: type(most_neg_long), type(-most_neg_long) (<... 'int'>, <type 'long'>) sage: 0 + most_neg_long == most_neg_long True sage: 0 - most_neg_long == -most_neg_long True """ cdef Integer x = <Integer>PY_NEW(Integer) if n > 0: mpz_add_ui(x.value, self.value, n) else: # Note that 0-<unsigned long>n is always -n as an unsigned # long (whereas -n may overflow). mpz_sub_ui(x.value, self.value, 0 - <unsigned long>n) return x
def __sub__(left, right): r""" TESTS::
sage: 1 - 2 -1 sage: 1 - 2/3 1/3 sage: 1 - (-2/3) 5/3 sage: (-1) - (-5/4) 1/4 """ cdef Integer x cdef Rational y mpq_denref((<Rational>right).value)) mpq_numref((<Rational>right).value))
cpdef _sub_(self, right): """ Integer subtraction.
TESTS::
sage: Integer(32) - Integer(23) 9 sage: Integer(10^100) - Integer(1) 9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999 sage: Integer(1) - Integer(10^100) -9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999 sage: a = ZZ.random_element(10^50000) sage: b = ZZ.random_element(10^50000) sage: a-b == -(b-a) == a + -b True """ # self and right are guaranteed to be Integers
def __neg__(self): """ TESTS::
sage: a = Integer(3) sage: -a -3 sage: a = Integer(3^100); a 515377520732011331036461129765621272702107522001 sage: -a -515377520732011331036461129765621272702107522001 """
cpdef _neg_(self): cdef Integer x = <Integer>PY_NEW(Integer) mpz_neg(x.value, self.value) return x
cpdef _act_on_(self, s, bint self_on_left): """ EXAMPLES::
sage: 8 * [0] #indirect doctest [0, 0, 0, 0, 0, 0, 0, 0] sage: 'hi' * 8 'hihihihihihihihi' """ else: return s * int(self) # will raise the appropriate exception
cdef _mul_long(self, long n): """ Fast path for multiplying a C long.
TESTS::
sage: Integer(25) * int(4) 100 sage: int(4) * Integer(25) 100 sage: Integer(10^100) * int(4) 40000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 """ cdef Integer x = <Integer>PY_NEW(Integer) if mpz_size(self.value) > 100000: sig_on() mpz_mul_si(x.value, self.value, n) sig_off() else: mpz_mul_si(x.value, self.value, n) return x
def __mul__(left, right): r""" TESTS::
sage: 3 * 2 6 sage: 5 * QQ((2,3)) 10/3 sage: 3 * (-5/6) -5/2 sage: (-2) * (-5/4) 5/2 """ cdef Integer x cdef Rational y
cpdef _mul_(self, right): """ Integer multiplication.
sage: 25._mul_(4) 100 sage: (5^100)._mul_(2^100) 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 sage: a = ZZ.random_element(10^50000) sage: b = ZZ.random_element(10^50000) sage: a._mul_(b) == b._mul_(a) True """ # self and right are guaranteed to be Integers # We only use the signal handler (to enable ctrl-c out) when the # product might take a while to compute sig_on() mpz_mul(x.value, self.value, (<Integer>right).value) sig_off() else:
def __div__(left, right): r""" TESTS::
sage: 3 / 2 3/2 sage: 5 / QQ((10,3)) 3/2 sage: 3 / (-5/6) -18/5 sage: (-2) / (-5/4) 8/5 sage: 3 / polygen(ZZ) 3/x
sage: 3 / 0 Traceback (most recent call last): ... ZeroDivisionError: rational division by zero sage: 3 / QQ.zero() Traceback (most recent call last): ... ZeroDivisionError: rational division by zero sage: 3 / QQbar.zero() Traceback (most recent call last): ... ZeroDivisionError: rational division by zero """ cdef Rational x # left * den(right) / num(right) mpq_numref((<Rational>right).value)) mpq_denref((<Rational>right).value))
cpdef _div_(self, right): r""" Computes `\frac{a}{b}`
EXAMPLES::
sage: 3._div_(4) 3/4 sage: (-32)._div_(-32) 1 """
cpdef _floordiv_(self, right): r""" Computes the whole part of `\frac{x}{y}`.
EXAMPLES::
sage: a = Integer(321) ; b = Integer(10) sage: a // b 32 sage: z = Integer(-231) sage: z // 2 -116 sage: z = Integer(231) sage: z // 2 115 sage: z // -2 -116 sage: z // 0 Traceback (most recent call last): ... ZeroDivisionError: Integer division by zero sage: 101 // int(5) 20 sage: 100 // int(-3) -34
TESTS::
sage: signs = [(11,5), (11,-5), (-11,5), (-11,-5)] sage: control = [int(a) // int(b) for a, b in signs] sage: [a // b for a,b in signs] == control True sage: [a // int(b) for a,b in signs] == control True sage: [int(a) // b for a,b in signs] == control True """
else:
def __pow__(left, right, modulus): r""" Return ``(left ^ right) % modulus``.
EXAMPLES::
sage: 2^-6 1/64 sage: 2^6 64 sage: 2^0 1 sage: 2^-0 1 sage: (-1)^(1/3) (-1)^(1/3)
For consistency with Python and MPFR, 0^0 is defined to be 1 in Sage::
sage: 0^0 1
See also `<http://www.faqs.org/faqs/sci-math-faq/0to0/>`_ and `<https://math.stackexchange.com/questions/11150/zero-to-the-zero-power-is-00-1>`_.
The base need not be a Sage integer. If it is a Python type, the result is a Python type too::
sage: r = int(2) ^ 10; r; type(r) 1024 <... 'int'> sage: r = int(3) ^ -3; r; type(r) 0.037037037037037035 <... 'float'> sage: r = float(2.5) ^ 10; r; type(r) 9536.7431640625 <... 'float'>
We raise 2 to various interesting exponents::
sage: 2^x # symbolic x 2^x sage: 2^1.5 # real number 2.82842712474619 sage: 2^float(1.5) # python float abs tol 3e-16 2.8284271247461903 sage: 2^I # complex number 2^I sage: r = 2 ^ int(-3); r; type(r) 1/8 <type 'sage.rings.rational.Rational'> sage: f = 2^(sin(x)-cos(x)); f 2^(-cos(x) + sin(x)) sage: f(x=3) 2^(-cos(3) + sin(3))
A symbolic sum::
sage: x,y,z = var('x,y,z') sage: 2^(x+y+z) 2^(x + y + z) sage: 2^(1/2) sqrt(2) sage: 2^(-1/2) 1/2*sqrt(2)
TESTS::
sage: R.<t> = QQ[] sage: 2^t Traceback (most recent call last): ... TypeError: no canonical coercion from Univariate Polynomial Ring in t over Rational Field to Rational Field sage: 'sage' ^ 3 doctest:...: DeprecationWarning: raising a string to an integer power is deprecated See http://trac.sagemath.org/24260 for details. 'sagesagesage' """ from sage.rings.finite_rings.integer_mod import Mod return Mod(left, modulus) ** right
# left is a non-Element: do the powering with a Python int
cpdef _pow_(self, other): """ Integer powering.
TESTS::
sage: 2._pow_(3) 8 sage: (-2)._pow_(3) -8 sage: 2._pow_(-3) 1/8 sage: (-2)._pow_(-3) -1/8 sage: 2._pow_(4) 16 sage: (-2)._pow_(4) 16 sage: 2._pow_(-4) 1/16 sage: (-2)._pow_(-4) 1/16 sage: 0._pow_(3) 0 sage: 0._pow_(-3) Traceback (most recent call last): ... ZeroDivisionError: rational division by zero
The exponent must fit in a long unless the base is -1, 0, or 1::
sage: 2 ^ 100000000000000000000000 Traceback (most recent call last): ... OverflowError: exponent must be at most 2147483647 # 32-bit OverflowError: exponent must be at most 9223372036854775807 # 64-bit sage: 1 ^ 100000000000000000000000 1 sage: 1 ^ -100000000000000000000000 1 sage: 0 ^ 100000000000000000000000 0 sage: 0 ^ -100000000000000000000000 Traceback (most recent call last): ... ZeroDivisionError: rational division by zero sage: (-1) ^ 100000000000000000000000 1 sage: (-1) ^ 100000000000000000000001 -1 sage: (-1) ^ -100000000000000000000000 1 sage: (-1) ^ -100000000000000000000001 -1 """
# Raising to an exponent which doesn't fit in a long overflows # except if the base is -1, 0 or 1.
elif s == -1: else: else: else:
cdef _pow_long(self, long n): elif n == 1:
cdef Integer x cdef Rational q else: else: # If the denominator was negative, change sign and set # numerator to -1
cpdef _pow_int(self, n): """ Integer powering to an integer exponent.
TESTS::
sage: 2._pow_int(int(20)) 1048576 sage: 1._pow_int(int(2^100)) 1 """
def nth_root(self, int n, bint truncate_mode=0): r""" Returns the (possibly truncated) n'th root of self.
INPUT:
- ``n`` - integer >= 1 (must fit in C int type).
- ``truncate_mode`` - boolean, whether to allow truncation if self is not an n'th power.
OUTPUT:
If truncate_mode is 0 (default), then returns the exact n'th root if self is an n'th power, or raises a ValueError if it is not.
If truncate_mode is 1, then if either n is odd or self is positive, returns a pair (root, exact_flag) where root is the truncated nth root (rounded towards zero) and exact_flag is a boolean indicating whether the root extraction was exact; otherwise raises a ValueError.
AUTHORS:
- David Harvey (2006-09-15) - Interface changed by John Cremona (2009-04-04)
EXAMPLES::
sage: Integer(125).nth_root(3) 5 sage: Integer(124).nth_root(3) Traceback (most recent call last): ... ValueError: 124 is not a 3rd power sage: Integer(124).nth_root(3, truncate_mode=1) (4, False) sage: Integer(125).nth_root(3, truncate_mode=1) (5, True) sage: Integer(126).nth_root(3, truncate_mode=1) (5, False)
::
sage: Integer(-125).nth_root(3) -5 sage: Integer(-125).nth_root(3,truncate_mode=1) (-5, True) sage: Integer(-124).nth_root(3,truncate_mode=1) (-4, False) sage: Integer(-126).nth_root(3,truncate_mode=1) (-5, False)
::
sage: Integer(125).nth_root(2, True) (11, False) sage: Integer(125).nth_root(3, True) (5, True)
::
sage: Integer(125).nth_root(-5) Traceback (most recent call last): ... ValueError: n (=-5) must be positive
::
sage: Integer(-25).nth_root(2) Traceback (most recent call last): ... ValueError: cannot take even root of negative number
::
sage: a=9 sage: a.nth_root(3) Traceback (most recent call last): ... ValueError: 9 is not a 3rd power
sage: a.nth_root(22) Traceback (most recent call last): ... ValueError: 9 is not a 22nd power
sage: ZZ(2^20).nth_root(21) Traceback (most recent call last): ... ValueError: 1048576 is not a 21st power
sage: ZZ(2^20).nth_root(21, truncate_mode=1) (1, False)
""" cdef Integer x cdef bint is_exact
else: else:
cpdef size_t _exact_log_log2_iter(self,Integer m): """ This is only for internal use only. You should expect it to crash and burn for negative or other malformed input. In particular, if the base `2 \leq m < 4` the log2 approximation of m is 1 and certain input causes endless loops. Along these lines, it is clear that this function is most useful for m with a relatively large number of bits.
For ``small`` values (which I'll leave quite ambiguous), this function is a fast path for exact log computations. Any integer division with such input tends to dominate the runtime. Thus we avoid division entirely in this function.
AUTHOR::
- Joel B. Mohler (2009-04-10)
EXAMPLES::
sage: Integer(125)._exact_log_log2_iter(4) 3 sage: Integer(5^150)._exact_log_log2_iter(5) 150 """ cdef size_t n_log2 cdef size_t m_log2 cdef size_t l_min cdef size_t l_max cdef size_t l cdef Integer result cdef mpz_t accum cdef mpz_t temp_exp
raise ValueError("This is undefined or possibly non-convergent with this algorithm.")
# This might over-shoot and make accum > self, but # we'll know that it's only over by a factor of m^1.
# Let x=n_log2-(mpz_sizeinbase(accum,2)-1) and y=m_log2. # Now, with x>0 and y>0, we have the following observation. # If floor((x-1)/(y+1))=0, then x-1<y+1 which implies that # x/y<1+2/y. # So long as y>=2, this means that floor(x/y)<=1. This shows # that this iteration is forced to converge for input m >= 4. # If m=3, we can find input so that floor((x-1)/(y+1))=0 and # floor(x/y)=2 which results in non-convergence.
# We need the additional '-1' in the l_min computation # because mpz_sizeinbase(accum,2)-1 is smaller than the # true log_2(accum)
cpdef size_t _exact_log_mpfi_log(self,m): """ This is only for internal use only. You should expect it to crash and burn for negative or other malformed input.
I avoid using this function until the input is large. The overhead associated with computing the floating point log entirely dominates the runtime for small values. Note that this is most definitely not an artifact of format conversion. Tricks with log2 approximations and using exact integer arithmetic are much better for small input.
AUTHOR::
- Joel B. Mohler (2009-04-10)
EXAMPLES::
sage: Integer(125)._exact_log_mpfi_log(3) 4 sage: Integer(5^150)._exact_log_mpfi_log(5) 150 """ cdef int i cdef list pow_2_things cdef int pow_2 cdef size_t upper,lower,middle
# upper is *greater* than the answer except Exception: # ceiling is probably Infinity # I'm not sure what to do now upper = 0 # since the log function is monotonic increasing, lower # and upper bracket our desired answer
# if upper - lower == 1: "we are done" # You could test it by checking rif_m**(lower+1), but I think # that's a waste of time since it won't be conclusive. # We must test with exact integer arithmetic which takes all # the bits of self into account. else: # this case would only happen in cases with extremely large 'self' rif_m = R(m) min_power = rif_m**lower middle = upper-lower pow_2 = 0 while middle != 0: middle >>= 1 pow_2 += 1 # if middle was an exact power of 2, adjust down if (1 << (pow_2-1)) == upper-lower: pow_2 -= 1 pow_2_things = [rif_m]*pow_2 for i from 1<=i<pow_2: pow_2_things[i] = pow_2_things[i-1]**2 for i from pow_2>i>=0: middle = lower + int(2)**i exp = min_power*pow_2_things[i] if exp > rif_self: upper = middle elif exp < rif_self: lower = middle min_power = exp else: sig_off() if m**middle <= self: return middle else: return lower
raise ValueError("The input for exact_log is too large and support is not implemented.")
def exact_log(self, m): r""" Returns the largest integer `k` such that `m^k \leq \text{self}`, i.e., the floor of `\log_m(\text{self})`.
This is guaranteed to return the correct answer even when the usual log function doesn't have sufficient precision.
INPUT:
- ``m`` - integer >= 2
AUTHORS:
- David Harvey (2006-09-15) - Joel B. Mohler (2009-04-08) -- rewrote this to handle small cases and/or easy cases up to 100x faster..
EXAMPLES::
sage: Integer(125).exact_log(5) 3 sage: Integer(124).exact_log(5) 2 sage: Integer(126).exact_log(5) 3 sage: Integer(3).exact_log(5) 0 sage: Integer(1).exact_log(5) 0 sage: Integer(178^1700).exact_log(178) 1700 sage: Integer(178^1700-1).exact_log(178) 1699 sage: Integer(178^1700+1).exact_log(178) 1700 sage: # we need to exercise the large base code path too sage: Integer(1780^1700-1).exact_log(1780) 1699
sage: # The following are very very fast. sage: # Note that for base m a perfect power of 2, we get the exact log by counting bits. sage: n=2983579823750185701375109835; m=32 sage: n.exact_log(m) 18 sage: # The next is a favorite of mine. The log2 approximate is exact and immediately provable. sage: n=90153710570912709517902579010793251709257901270941709247901209742124;m=213509721309572 sage: n.exact_log(m) 4
::
sage: x = 3^100000 sage: RR(log(RR(x), 3)) 100000.000000000 sage: RR(log(RR(x + 100000), 3)) 100000.000000000
::
sage: x.exact_log(3) 100000 sage: (x+1).exact_log(3) 100000 sage: (x-1).exact_log(3) 99999
::
sage: x.exact_log(2.5) Traceback (most recent call last): ... TypeError: Attempt to coerce non-integral RealNumber to Integer """ cdef Integer _m cdef Integer result cdef size_t n_log2 cdef size_t m_log2 cdef size_t guess # this will contain the final answer cdef mpz_t z else:
raise ValueError("both self and m must be positive") raise ValueError("m must be at least 2")
# Here, m is a power of 2 and the correct answer is found # by a log 2 approximation. # In this case, we have an upper bound and lower bound which # give the same answer, thus, the correct answer. # if the base m is at most 256, we can use mpz_sizeinbase # to get the following guess which is either the exact # log, or 1+ the exact log
# we've already excluded the case when m is an exact power of 2
# If we have a very large number of digits, it can be a nice # shortcut to test the guess using interval arithmetic. # (suggested by David Harvey and Carl Witty) # "for randomly distributed integers, the chance of this # interval-based comparison failing is absurdly low" # At this point, either # 1) self is close enough to a perfect power of m that we # need an exact comparison, or # 2) the numbers are small enough that converting to the # interval field is more work than the exact comparison. # for input with small exact log, it's very fast to work in exact # integer arithmetic starting from log2 approximations else: # finally, we are out of easy cases this subroutine uses interval # arithmetic to guess and check the exact log.
def log(self, m=None, prec=None): r""" Returns symbolic log by default, unless the logarithm is exact (for an integer argument). When precision is given, the RealField approximation to that bit precision is used.
This function is provided primarily so that Sage integers may be treated in the same manner as real numbers when convenient. Direct use of exact_log is probably best for arithmetic log computation.
INPUT:
- ``m`` - default: natural log base e
- ``prec`` - integer (default: None): if None, returns symbolic, else to given bits of precision as in RealField
EXAMPLES::
sage: Integer(124).log(5) log(124)/log(5) sage: Integer(124).log(5,100) 2.9950093311241087454822446806 sage: Integer(125).log(5) 3 sage: Integer(125).log(5,prec=53) 3.00000000000000 sage: log(Integer(125)) 3*log(5)
For extremely large numbers, this works::
sage: x = 3^100000 sage: log(x,3) 100000
With the new Pynac symbolic backend, log(x) also works in a reasonable amount of time for this x::
sage: x = 3^100000 sage: log(x) log(1334971414230...5522000001)
But approximations are probably more useful in this case, and work to as high a precision as we desire::
sage: x.log(3,53) # default precision for RealField 100000.000000000 sage: (x+1).log(3,53) 100000.000000000 sage: (x+1).log(3,1000) 100000.000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
We can use non-integer bases, with default e::
sage: x.log(2.5,prec=53) 119897.784671579
We also get logarithms of negative integers, via the symbolic ring, using the branch from `-pi` to `pi`::
sage: log(-1) I*pi
The logarithm of zero is done likewise::
sage: log(0) -Infinity
Some rational bases yield integer logarithms (:trac:`21517`)::
sage: ZZ(8).log(1/2) -3
Check that Python ints are accepted (:trac:`21518`)::
sage: ZZ(8).log(int(2)) 3 """
pass
def exp(self, prec=None): r""" Returns the exponential function of self as a real number.
This function is provided only so that Sage integers may be treated in the same manner as real numbers when convenient.
INPUT:
- ``prec`` - integer (default: None): if None, returns symbolic, else to given bits of precision as in RealField
EXAMPLES::
sage: Integer(8).exp() e^8 sage: Integer(8).exp(prec=100) 2980.9579870417282747435920995 sage: exp(Integer(8)) e^8
For even fairly large numbers, this may not be useful.
::
sage: y=Integer(145^145) sage: y.exp() e^25024207011349079210459585279553675697932183658421565260323592409432707306554163224876110094014450895759296242775250476115682350821522931225499163750010280453185147546962559031653355159703678703793369785727108337766011928747055351280379806937944746847277089168867282654496776717056860661614337004721164703369140625 sage: y.exp(prec=53) # default RealField precision +infinity """
def prime_to_m_part(self, m): """ Returns the prime-to-m part of self, i.e., the largest divisor of ``self`` that is coprime to ``m``.
INPUT:
- ``m`` - Integer
OUTPUT: Integer
EXAMPLES::
sage: 43434.prime_to_m_part(20) 21717 sage: 2048.prime_to_m_part(2) 1 sage: 2048.prime_to_m_part(3) 2048
sage: 0.prime_to_m_part(2) Traceback (most recent call last): ... ArithmeticError: self must be nonzero """
def prime_divisors(self): """ The prime divisors of self, sorted in increasing order. If n is negative, we do *not* include -1 among the prime divisors, since -1 is not a prime number.
EXAMPLES::
sage: a = 1; a.prime_divisors() [] sage: a = 100; a.prime_divisors() [2, 5] sage: a = -100; a.prime_divisors() [2, 5] sage: a = 2004; a.prime_divisors() [2, 3, 167] """
prime_factors = prime_divisors
cpdef list _pari_divisors_small(self): r""" Return the list of divisors of this number using PARI ``divisorsu``.
.. SEEALSO::
This method is better used through :meth:`divisors`.
EXAMPLES::
sage: 4._pari_divisors_small() [1, 2, 4]
The integer must fit into an unsigned long::
sage: (-4)._pari_divisors_small() Traceback (most recent call last): ... AssertionError sage: (2**65)._pari_divisors_small() Traceback (most recent call last): ... AssertionError """ # we need n to fit into a long and not a unsigned long in order to use # smallInteger
global avma cdef GEN d cdef list output
finally: avma = ltop
@cython.boundscheck(False) @cython.wraparound(False) def divisors(self, method=None): """ Returns a list of all positive integer divisors of the integer self.
EXAMPLES::
sage: (-3).divisors() [1, 3] sage: 6.divisors() [1, 2, 3, 6] sage: 28.divisors() [1, 2, 4, 7, 14, 28] sage: (2^5).divisors() [1, 2, 4, 8, 16, 32] sage: 100.divisors() [1, 2, 4, 5, 10, 20, 25, 50, 100] sage: 1.divisors() [1] sage: 0.divisors() Traceback (most recent call last): ... ValueError: n must be nonzero sage: (2^3 * 3^2 * 17).divisors() [1, 2, 3, 4, 6, 8, 9, 12, 17, 18, 24, 34, 36, 51, 68, 72, 102, 136, 153, 204, 306, 408, 612, 1224] sage: a = odd_part(factorial(31)) sage: v = a.divisors(); len(v) 172800 sage: prod(e+1 for p,e in factor(a)) 172800 sage: all([t.divides(a) for t in v]) True
::
sage: n = 2^551 - 1 sage: L = n.divisors() sage: len(L) 256 sage: L[-1] == n True
TESTS::
sage: prod(primes_first_n(64)).divisors() Traceback (most recent call last): ... OverflowError: value too large sage: prod(primes_first_n(58)).divisors() Traceback (most recent call last): ... OverflowError: value too large # 32-bit MemoryError: failed to allocate 288230376151711744 * 24 bytes # 64-bit
Check for memory leaks and ability to interrupt (the ``divisors`` call below allocates about 800 MB every time, so a memory leak will not go unnoticed)::
sage: n = prod(primes_first_n(25)) sage: for i in range(20): # long time ....: try: ....: alarm(RDF.random_element(1e-3, 0.5)) ....: _ = n.divisors() ....: cancel_alarm() # we never get here ....: except AlarmInterrupt: ....: pass
Test a strange method::
sage: 100.divisors(method='hey') Traceback (most recent call last): ... ValueError: method must be 'pari' or 'sage'
.. NOTE::
If one first computes all the divisors and then sorts it, the sorting step can easily dominate the runtime. Note, however, that (non-negative) multiplication on the left preserves relative order. One can leverage this fact to keep the list in order as one computes it using a process similar to that of the merge sort algorithm. """
else:
cdef list all, prev, sorted cdef Py_ssize_t tip, top cdef Py_ssize_t i, j, e, ee cdef Integer apn, p, pn, z, all_tip
# All of the declarations below are for optimizing the unsigned long-sized # case. Operations are performed in C as far as possible without # overflow before moving to Python objects. cdef unsigned long p_c, pn_c, apn_c cdef Py_ssize_t all_len, sorted_len, prev_len cdef unsigned long* ptr cdef unsigned long* empty_c cdef unsigned long* swap_tmp cdef unsigned long* all_c cdef unsigned long* sorted_c cdef unsigned long* prev_c
# These are used to keep track of whether or not we are able to # perform the operations in machine words. A factor of 0.999 # safety margin is added to cover any floating-point rounding # issues.
with cython.overflowcheck(True): # Using *= does not work, see # https://github.com/cython/cython/issues/1381
# The two cases below are essentially the same algorithm, one # operating on Integers in Python lists, the other on unsigned long's.
else: # fits_c is False: use mpz integers # apn = a*pn
# all the data is in sorted_c sorted = [] for i in range(sorted_len): z = <Integer>PY_NEW(Integer) mpz_set_ui(z.value, sorted_c[i]) sorted.append(z) finally:
def __pos__(self): """ EXAMPLES::
sage: z=43434 sage: z.__pos__() 43434 """
def __abs__(self): """ Computes `|self|`
EXAMPLES::
sage: z = -1 sage: abs(z) 1 sage: abs(z) == abs(1) True """
def euclidean_degree(self): r""" Return the degree of this element as an element of an Euclidean domain.
If this is an element in the ring of integers, this is simply its absolute value.
EXAMPLES::
sage: ZZ(1).euclidean_degree() 1
""" raise NotImplementedError
def sign(self): """ Returns the sign of this integer, which is -1, 0, or 1 depending on whether this number is negative, zero, or positive respectively.
OUTPUT: Integer
EXAMPLES::
sage: 500.sign() 1 sage: 0.sign() 0 sage: (-10^43).sign() -1 """
def __mod__(x, y): r""" Return x modulo y.
EXAMPLES::
sage: z = 43 sage: z % 2 1 sage: z % 0 Traceback (most recent call last): ... ZeroDivisionError: Integer modulo by zero sage: -5 % 7 2 sage: -5 % -7 -5 sage: 5 % -7 -2 sage: 5 % int(-7) -2 sage: int(5) % -7 -2 sage: int(5) % int(-7) -2
TESTS::
sage: signs = [(11,5), (11,-5), (-11,5), (-11,-5)] sage: control = [int(a) % int(b) for a, b in signs] sage: [a % b for a,b in signs] == control True sage: [a % int(b) for a,b in signs] == control True sage: [int(a) % b for a,b in signs] == control True
This example caused trouble in :trac:`6083`::
sage: a = next_prime(2**31) sage: b = Integers(a)(100) sage: a % b Traceback (most recent call last): ... ArithmeticError: reduction modulo 100 not defined """ cdef Integer z
# First case: Integer % Integer sig_on() mpz_fdiv_r(z.value, (<Integer>x).value, (<Integer>y).value) sig_off() else:
# Next: Integer % C long # x must be an Integer in this case # y cannot be converted to an integer return NotImplemented # y is some kind of integer, # but too large for a C long return x % Integer(y)
raise ZeroDivisionError("Integer modulo by zero") else:
# Use the coercion model
def quo_rem(Integer self, other): """ Returns the quotient and the remainder of self divided by other. Note that the remainder returned is always either zero or of the same sign as other.
INPUT:
- ``other`` - the divisor
OUTPUT:
- ``q`` - the quotient of self/other
- ``r`` - the remainder of self/other
EXAMPLES::
sage: z = Integer(231) sage: z.quo_rem(2) (115, 1) sage: z.quo_rem(-2) (-116, -1) sage: z.quo_rem(0) Traceback (most recent call last): ... ZeroDivisionError: Integer division by zero
sage: a = ZZ.random_element(10**50) sage: b = ZZ.random_element(10**15) sage: q, r = a.quo_rem(b) sage: q*b + r == a True
sage: 3.quo_rem(ZZ['x'].0) (0, 3)
TESTS:
The divisor can be rational as well, although the remainder will always be zero (:trac:`7965`)::
sage: 5.quo_rem(QQ(2)) (5/2, 0) sage: 5.quo_rem(2/3) (15/2, 0)
""" cdef long d, res
elif d == 0: raise ZeroDivisionError("Integer division by zero") else: res = mpz_fdiv_qr_ui(q.value, r.value, self.value, -d) mpz_neg(q.value, q.value) if res: mpz_sub_ui(q.value, q.value, 1) mpz_sub_ui(r.value, r.value, -d)
sig_on() mpz_fdiv_qr(q.value, r.value, self.value, (<Integer>other).value) sig_off() else:
else:
def powermod(self, exp, mod): """ Compute self\*\*exp modulo mod.
EXAMPLES::
sage: z = 2 sage: z.powermod(31,31) 2 sage: z.powermod(0,31) 1 sage: z.powermod(-31,31) == 2^-31 % 31 True
As expected, the following is invalid::
sage: z.powermod(31,0) Traceback (most recent call last): ... ZeroDivisionError: cannot raise to a power modulo 0 """ cdef Integer x, _exp, _mod
def rational_reconstruction(self, Integer m): """ Return the rational reconstruction of this integer modulo m, i.e., the unique (if it exists) rational number that reduces to self modulo m and whose numerator and denominator is bounded by sqrt(m/2).
INPUT:
- ``self`` -- Integer
- ``m`` -- Integer
OUTPUT:
- a :class:`Rational`
EXAMPLES::
sage: (3/7)%100 29 sage: (29).rational_reconstruction(100) 3/7
TESTS:
Check that :trac:`9345` is fixed::
sage: 0.rational_reconstruction(0) Traceback (most recent call last): ... ZeroDivisionError: rational reconstruction with zero modulus sage: ZZ.random_element(-10^6, 10^6).rational_reconstruction(0) Traceback (most recent call last): ... ZeroDivisionError: rational reconstruction with zero modulus """ cdef Integer a
powermodm_ui = deprecated_function_alias(17852, powermod)
def __int__(self): """ Return the Python int (or long) corresponding to this Sage integer.
EXAMPLES::
sage: n = 920938 sage: int(n) 920938 sage: int(-n) -920938 sage: type(n.__int__()) <... 'int'> sage: n = 99028390823409823904823098490238409823490820938 sage: int(n) 99028390823409823904823098490238409823490820938L sage: int(-n) -99028390823409823904823098490238409823490820938L sage: type(n.__int__()) <type 'long'> sage: int(-1), int(0), int(1) (-1, 0, 1) """
def __long__(self): """ Return the Python long corresponding to this Sage integer.
EXAMPLES::
sage: n = 9023408290348092849023849820934820938490234290 sage: long(n) 9023408290348092849023849820934820938490234290L sage: long(-n) -9023408290348092849023849820934820938490234290L sage: n = 920938 sage: long(n) 920938L sage: n.__long__() 920938L sage: long(-1), long(0), long(1) (-1L, 0L, 1L) """
def __float__(self): """ Return double precision floating point representation of this integer.
EXAMPLES::
sage: n = Integer(17); float(n) 17.0 sage: n = Integer(902834098234908209348209834092834098); float(n) 9.028340982349083e+35 sage: n = Integer(-57); float(n) -57.0 sage: n.__float__() -57.0 sage: type(n.__float__()) <... 'float'> """
def _rpy_(self): """ Returns int(self) so that rpy can convert self into an object it knows how to work with.
EXAMPLES::
sage: n = 100 sage: n._rpy_() 100 sage: type(n._rpy_()) <... 'int'> """
def __hash__(self): """ Return the hash of this integer.
This agrees with the Python hash of the corresponding Python int or long.
EXAMPLES::
sage: n = -920384; n.__hash__() -920384 sage: hash(int(n)) -920384 sage: n = -920390823904823094890238490238484; n.__hash__() -873977844 # 32-bit 6874330978542788722 # 64-bit sage: hash(long(n)) -873977844 # 32-bit 6874330978542788722 # 64-bit
TESTS::
sage: hash(-1), hash(0), hash(1) (-2, 0, 1) sage: n = 2^31 + 2^63 + 2^95 + 2^127 + 2^128*(2^32-2) sage: hash(n) == hash(long(n)) True sage: hash(n-1) == hash(long(n-1)) True sage: hash(-n) == hash(long(-n)) True sage: hash(1-n) == hash(long(1-n)) True sage: n = 2^63 + 2^127 + 2^191 + 2^255 + 2^256*(2^64-2) sage: hash(n) == hash(long(n)) True sage: hash(n-1) == hash(long(n-1)) True sage: hash(-n) == hash(long(-n)) True sage: hash(1-n) == hash(long(1-n)) True
These tests come from :trac:`4957`::
sage: n = 2^31 + 2^13 sage: hash(n) -2147475456 # 32-bit 2147491840 # 64-bit sage: hash(n) == hash(int(n)) True sage: n = 2^63 + 2^13 sage: hash(n) -2147475456 # 32-bit -9223372036854767616 # 64-bit sage: hash(n) == hash(int(n)) True """
cdef hash_c(self): """ A C version of the __hash__ function. """
def trial_division(self, long bound=LONG_MAX, long start=2): """ Return smallest prime divisor of self up to bound, beginning checking at start, or abs(self) if no such divisor is found.
INPUT:
- ``bound`` -- a positive integer that fits in a C signed long - ``start`` -- a positive integer that fits in a C signed long
OUTPUT:
- a positive integer
EXAMPLES::
sage: n = next_prime(10^6)*next_prime(10^7); n.trial_division() 1000003 sage: (-n).trial_division() 1000003 sage: n.trial_division(bound=100) 10000049000057 sage: n.trial_division(bound=-10) Traceback (most recent call last): ... ValueError: bound must be positive sage: n.trial_division(bound=0) Traceback (most recent call last): ... ValueError: bound must be positive sage: ZZ(0).trial_division() Traceback (most recent call last): ... ValueError: self must be nonzero
sage: n = next_prime(10^5) * next_prime(10^40); n.trial_division() 100003 sage: n.trial_division(bound=10^4) 1000030000000000000000000000000000000012100363 sage: (-n).trial_division(bound=10^4) 1000030000000000000000000000000000000012100363 sage: (-n).trial_division() 100003 sage: n = 2 * next_prime(10^40); n.trial_division() 2 sage: n = 3 * next_prime(10^40); n.trial_division() 3 sage: n = 5 * next_prime(10^40); n.trial_division() 5 sage: n = 2 * next_prime(10^4); n.trial_division() 2 sage: n = 3 * next_prime(10^4); n.trial_division() 3 sage: n = 5 * next_prime(10^4); n.trial_division() 5
You can specify a starting point::
sage: n = 3*5*101*103 sage: n.trial_division(start=50) 101 """ cdef unsigned long dif[8] # We need to find i. # Algorithm: only trial divide by numbers that # are congruent to 1,7,11,13,17,19,23,29 mod 30=2*3*5. else: # self is big -- it doesn't fit in unsigned long.
# x.value = floor(sqrt(self.value)) else:
def factor(self, algorithm='pari', proof=None, limit=None, int_=False, verbose=0): """ Return the prime factorization of this integer as a formal Factorization object.
INPUT:
- ``algorithm`` - string
- ``'pari'`` - (default) use the PARI library
- ``'kash'`` - use the KASH computer algebra system (requires the optional kash package)
- ``'magma'`` - use the MAGMA computer algebra system (requires an installation of MAGMA)
- ``'qsieve'`` - use Bill Hart's quadratic sieve code; WARNING: this may not work as expected, see qsieve? for more information
- ``'ecm'`` - use ECM-GMP, an implementation of Hendrik Lenstra's elliptic curve method.
- ``proof`` - bool (default: True) whether or not to prove primality of each factor (only applicable for ``'pari'`` and ``'ecm'``).
- ``limit`` - int or None (default: None) if limit is given it must fit in a signed int, and the factorization is done using trial division and primes up to limit.
OUTPUT:
- a Factorization object containing the prime factors and their multiplicities
EXAMPLES::
sage: n = 2^100 - 1; n.factor() 3 * 5^3 * 11 * 31 * 41 * 101 * 251 * 601 * 1801 * 4051 * 8101 * 268501
This factorization can be converted into a list of pairs `(p, e)`, where `p` is prime and `e` is a positive integer. Each pair can also be accessed directly by its index (ordered by increasing size of the prime)::
sage: f = 60.factor() sage: list(f) [(2, 2), (3, 1), (5, 1)] sage: f[2] (5, 1)
Similarly, the factorization can be converted to a dictionary so the exponent can be extracted for each prime::
sage: f = (3^6).factor() sage: dict(f) {3: 6} sage: dict(f)[3] 6
We use proof=False, which doesn't prove correctness of the primes that appear in the factorization::
sage: n = 920384092842390423848290348203948092384082349082 sage: n.factor(proof=False) 2 * 11 * 1531 * 4402903 * 10023679 * 619162955472170540533894518173 sage: n.factor(proof=True) 2 * 11 * 1531 * 4402903 * 10023679 * 619162955472170540533894518173
We factor using trial division only::
sage: n.factor(limit=1000) 2 * 11 * 41835640583745019265831379463815822381094652231
We factor using a quadratic sieve algorithm::
sage: p = next_prime(10^20) sage: q = next_prime(10^21) sage: n = p*q sage: n.factor(algorithm='qsieve') doctest:... RuntimeWarning: the factorization returned by qsieve may be incomplete (the factors may not be prime) or even wrong; see qsieve? for details 100000000000000000039 * 1000000000000000000117
We factor using the elliptic curve method::
sage: p = next_prime(10^15) sage: q = next_prime(10^21) sage: n = p*q sage: n.factor(algorithm='ecm') 1000000000000037 * 1000000000000000000117
TESTS::
sage: n = 42 sage: n.factor(algorithm='foobar') Traceback (most recent call last): ... ValueError: Algorithm is not known """
cdef Integer n, p, unit cdef int i cdef n_factor_t f
else:
from sage.rings.factorint import factor_trial_division return factor_trial_division(self)
if algorithm == 'kash': from sage.interfaces.all import kash as I else: from sage.interfaces.all import magma as I str_res = I.eval('Factorization(%s)'%n) # The result looks like "[ <n1, p1>, <p2, e2>, ... ] str_res = str_res.replace(']', '').replace('[', '').replace('>', '').replace('<', '').split(',') res = [int(s.strip()) for s in str_res] exp_type = int if int_ else Integer F = [(Integer(p), exp_type(e)) for p,e in zip(res[0::2], res[1::2])] return Factorization(F, unit) else:
def support(self): """ Return a sorted list of the primes dividing this integer.
OUTPUT: The sorted list of primes appearing in the factorization of this rational with positive exponent.
EXAMPLES::
sage: factorial(10).support() [2, 3, 5, 7] sage: (-999).support() [3, 37]
Trying to find the support of 0 gives an arithmetic error::
sage: 0.support() Traceback (most recent call last): ... ArithmeticError: Support of 0 not defined. """
def coprime_integers(self, m): """ Return the positive integers `< m` that are coprime to this integer.
EXAMPLES::
sage: n = 8 sage: n.coprime_integers(8) [1, 3, 5, 7] sage: n.coprime_integers(11) [1, 3, 5, 7, 9] sage: n = 5; n.coprime_integers(10) [1, 2, 3, 4, 6, 7, 8, 9] sage: n.coprime_integers(5) [1, 2, 3, 4] sage: n = 99; n.coprime_integers(99) [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]
TESTS::
sage: for n in srange(-6,7): ....: for m in range(1,abs(n)+3): ....: assert n.coprime_integers(m) == [k for k in srange(1,m) if gcd(k,n) == 1]
AUTHORS:
- Naqi Jaffery (2006-01-24): examples
- David Roe (2017-10-02): Now uses sieving for larger inputs
ALGORITHM:
Create an integer with `m` bits and set bits at every multiple of a prime `p` that divides this integer and is less than `m`. Then return a list of integers corresponding to the unset bits. """ raise ValueError("m is too large") cdef unsigned long ilong, plong # p is larger than m, so no more primes are needed. # Set bits in sieve at each multiple of p # Now divide by p until no ps remain # If we have found all factors, we break
def divides(self, n): """ Return True if self divides n.
EXAMPLES::
sage: Z = IntegerRing() sage: Z(5).divides(Z(10)) True sage: Z(0).divides(Z(5)) False sage: Z(10).divides(Z(5)) False """ cdef bint t cdef Integer _n
cpdef RingElement _valuation(Integer self, Integer p): r""" Return the p-adic valuation of self.
We do not require that p be prime, but it must be at least 2. For more documentation see ``valuation``
AUTHORS:
- David Roe (3/31/07) """
cdef mpz_t u
cdef object _val_unit(Integer self, Integer p): r""" Returns a pair: the p-adic valuation of self, and the p-adic unit of self.
We do not require the p be prime, but it must be at least 2. For more documentation see ``val_unit``
AUTHORS:
- David Roe (2007-03-31) """ cdef Integer v, u raise ValueError("You can only compute the valuation with respect to a integer larger than 1.")
def valuation(self, p): """ Return the p-adic valuation of self.
INPUT:
- ``p`` - an integer at least 2.
EXAMPLES::
sage: n = 60 sage: n.valuation(2) 2 sage: n.valuation(3) 1 sage: n.valuation(7) 0 sage: n.valuation(1) Traceback (most recent call last): ... ValueError: You can only compute the valuation with respect to a integer larger than 1.
We do not require that p is a prime::
sage: (2^11).valuation(4) 5 """
# Alias for valuation ord = valuation
def val_unit(self, p): r""" Returns a pair: the p-adic valuation of self, and the p-adic unit of self.
INPUT:
- ``p`` - an integer at least 2.
OUTPUT:
- ``v_p(self)`` - the p-adic valuation of ``self``
- ``u_p(self)`` - ``self`` / `p^{v_p(\mathrm{self})}`
EXAMPLES::
sage: n = 60 sage: n.val_unit(2) (2, 15) sage: n.val_unit(3) (1, 20) sage: n.val_unit(7) (0, 60) sage: (2^11).val_unit(4) (5, 2) sage: 0.val_unit(2) (+Infinity, 1) """
def odd_part(self): r""" The odd part of the integer `n`. This is `n / 2^v`, where `v = \mathrm{valuation}(n,2)`.
IMPLEMENTATION:
Currently returns 0 when self is 0. This behaviour is fairly arbitrary, and in Sage 4.6 this special case was not handled at all, eventually propagating a TypeError. The caller should not rely on the behaviour in case self is 0.
EXAMPLES::
sage: odd_part(5) 5 sage: odd_part(4) 1 sage: odd_part(factorial(31)) 122529844256906551386796875 """ cdef Integer odd cdef unsigned long bits
return self
cdef Integer _divide_knowing_divisible_by(Integer self, Integer right): r""" Returns the integer self / right when self is divisible by right.
If self is not divisible by right, the return value is undefined, and may not even be close to self/right. For more documentation see ``divide_knowing_divisible_by``
AUTHORS:
- David Roe (2007-03-31) """ raise ZeroDivisionError cdef Integer x # Only use the signal handler (to enable ctrl-c out) when the # quotient might take a while to compute sig_on() mpz_divexact(x.value, self.value, right.value) sig_off() else:
def divide_knowing_divisible_by(self, right): r""" Returns the integer self / right when self is divisible by right.
If self is not divisible by right, the return value is undefined, and may not even be close to self/right for multi-word integers.
EXAMPLES::
sage: a = 8; b = 4 sage: a.divide_knowing_divisible_by(b) 2 sage: (100000).divide_knowing_divisible_by(25) 4000 sage: (100000).divide_knowing_divisible_by(26) # close (random) 3846
However, often it's way off.
::
sage: a = 2^70; a 1180591620717411303424 sage: a // 11 # floor divide 107326510974310118493 sage: a.divide_knowing_divisible_by(11) # way off and possibly random 43215361478743422388970455040 """
def _lcm(self, Integer n): """ Returns the least common multiple of self and `n`.
EXAMPLES::
sage: n = 60 sage: n._lcm(150) 300 """
def denominator(self): """ Return the denominator of this integer, which of course is always 1.
EXAMPLES::
sage: x = 5 sage: x.denominator() 1 sage: x = 0 sage: x.denominator() 1 """
def numerator(self): """ Return the numerator of this integer.
EXAMPLES::
sage: x = 5 sage: x.numerator() 5
::
sage: x = 0 sage: x.numerator() 0 """
def factorial(self): r""" Return the factorial `n! = 1 \cdot 2 \cdot 3 \cdots n`.
If the input does not fit in an ``unsigned long int`` a symbolic expression is returned.
EXAMPLES::
sage: for n in srange(7): ....: print("{} {}".format(n, n.factorial())) 0 1 1 1 2 2 3 6 4 24 5 120 6 720 sage: 234234209384023842034.factorial() factorial(234234209384023842034) """
@cython.cdivision(True) def multifactorial(self, int k): r""" Compute the k-th factorial `n!^{(k)}` of self.
For k=1 this is the standard factorial, and for k greater than one it is the product of every k-th terms down from self to k. The recursive definition is used to extend this function to the negative integers.
EXAMPLES::
sage: 5.multifactorial(1) 120 sage: 5.multifactorial(2) 15 sage: 5.multifactorial(3) 10 sage: 23.multifactorial(2) 316234143225 sage: prod([1..23, step=2]) 316234143225 sage: (-29).multifactorial(7) 1/2640
TESTS::
sage: for a in range(1,20): ....: for b in range(1,20): ....: assert ZZ(a).multifactorial(b) == prod(range(a,0,-b)) """ raise ValueError("multifactorial only defined for positive values of k")
raise ValueError("multifactorial not implemented for n >= 2^32.\nThis is probably OK, since the answer would have billions of digits.")
# base case
# easy to calculate else:
# negative base case
# reflection case else:
# compute the actual product, optimizing the number of large # multiplications cdef int i,j
# we need (at most) log_2(#factors) concurrent sub-products
# for the i-th terms we use the bits of i to calculate how many # times we need to multiply "up" the stack of sub-products
def gamma(self): r""" The gamma function on integers is the factorial function (shifted by one) on positive integers, and `\pm \infty` on non-positive integers.
EXAMPLES::
sage: gamma(5) 24 sage: gamma(0) Infinity sage: gamma(-1) Infinity sage: gamma(-2^150) Infinity """ else:
def floor(self): """ Return the floor of self, which is just self since self is an integer.
EXAMPLES::
sage: n = 6 sage: n.floor() 6 """
def ceil(self): """ Return the ceiling of self, which is self since self is an integer.
EXAMPLES::
sage: n = 6 sage: n.ceil() 6 """
def trunc(self): """ Round this number to the nearest integer, which is self since self is an integer.
EXAMPLES::
sage: n = 6 sage: n.trunc() 6 """
def round(Integer self, mode="away"): """ Returns the nearest integer to ``self``, which is self since self is an integer.
EXAMPLES:
This example addresses :trac:`23502`::
sage: n = 6 sage: n.round() 6 """
def real(self): """ Returns the real part of self, which is self.
EXAMPLES::
sage: Integer(-4).real() -4 """
def imag(self): """ Returns the imaginary part of self, which is zero.
EXAMPLES::
sage: Integer(9).imag() 0 """
def is_one(self): r""" Returns ``True`` if the integer is `1`, otherwise ``False``.
EXAMPLES::
sage: Integer(1).is_one() True sage: Integer(0).is_one() False """
def __nonzero__(self): r""" Returns ``True`` if the integer is not `0`, otherwise ``False``.
EXAMPLES::
sage: Integer(1).is_zero() False sage: Integer(0).is_zero() True """
def is_integral(self): """ Return ``True`` since integers are integral, i.e., satisfy a monic polynomial with integer coefficients.
EXAMPLES::
sage: Integer(3).is_integral() True """
def is_rational(self): r""" Return ``True`` as an integer is a rational number.
EXAMPLES::
sage: 5.is_rational() True """
def is_integer(self): """ Returns ``True`` as they are integers
EXAMPLES::
sage: sqrt(4).is_integer() True """
def is_unit(self): r""" Returns ``true`` if this integer is a unit, i.e., 1 or `-1`.
EXAMPLES::
sage: for n in srange(-2,3): ....: print("{} {}".format(n, n.is_unit())) -2 False -1 True 0 False 1 True 2 False """
def is_square(self): r""" Returns ``True`` if self is a perfect square.
EXAMPLES::
sage: Integer(4).is_square() True sage: Integer(41).is_square() False """
def perfect_power(self): r""" Returns ``(a, b)``, where this integer is `a^b` and `b` is maximal.
If called on `-1`, `0` or `1`, `b` will be `1`, since there is no maximal value of `b`.
.. SEEALSO::
- :meth:`is_perfect_power`: testing whether an integer is a perfect power is usually faster than finding `a` and `b`. - :meth:`is_prime_power`: checks whether the base is prime. - :meth:`is_power_of`: if you know the base already, this method is the fastest option.
EXAMPLES::
sage: 144.perfect_power() (12, 2) sage: 1.perfect_power() (1, 1) sage: 0.perfect_power() (0, 1) sage: (-1).perfect_power() (-1, 1) sage: (-8).perfect_power() (-2, 3) sage: (-4).perfect_power() (-4, 1) sage: (101^29).perfect_power() (101, 29) sage: (-243).perfect_power() (-3, 5) sage: (-64).perfect_power() (-4, 3) """
def global_height(self, prec=None): r""" Returns the absolute logarithmic height of this rational integer.
INPUT:
- ``prec`` (int) -- desired floating point precision (default: default RealField precision).
OUTPUT:
(real) The absolute logarithmic height of this rational integer.
ALGORITHM:
The height of the integer `n` is `\log |n|`.
EXAMPLES::
sage: ZZ(5).global_height() 1.60943791243410 sage: ZZ(-2).global_height(prec=100) 0.69314718055994530941723212146 sage: exp(_) 2.0000000000000000000000000000 """ else: return R.zero()
cdef bint _is_power_of(Integer self, Integer n): r""" Returns a non-zero int if there is an integer b with `\mathtt{self} = n^b`.
For more documentation see ``is_power_of``.
AUTHORS:
- David Roe (2007-03-31) """ cdef int a cdef unsigned long b, c cdef mpz_t u, sabs, nabs else: else: elif a == 0: # n == 0 else: return 0 elif a == -1: # n == -1 else: return 0 elif a == -2: # n == -2 # An odd power of -2 is negative, an even power must be positive. else: # number of bits set in |self| is not 1, so self cannot be a power of -2 return 0 else: # |self| is not a power of 2, so self cannot be a power of -2 return 0 else: # n < -2 # Having obtained b and c, we're done with nabs and sabs (on this branch anyway) # These two cases are that b // c is even and self positive, or b // c is odd and self negative else: # The sign of self is wrong return 0 else: # Since |self| is not a power of |n|, self cannot be a power of n return 0 else: # self is not a power of 2, and thus cannot be a power of n, which is a power of 2. mpz_clear(nabs) mpz_clear(sabs) return 0 else: # |n| is not a power of 2, so we use mpz_remove # Having obtained b and u, we're done with nabs mpz_clear(u) if b % 2 == 0: # an even power of |n|, and since self > 0, this means that self is a power of n return 1 else: return 0 return 1 else: else: # |self| is not a power of |n|, so self cannot be a power of n mpz_clear(u) return 0 else: else: # self is not a power of 2, and thus not a power of n else: # n > 2, but not a power of 2, so we use mpz_remove else:
def is_power_of(Integer self, n): r""" Returns ``True`` if there is an integer b with `\mathtt{self} = n^b`.
.. SEEALSO::
- :meth:`perfect_power`: Finds the minimal base for which this integer is a perfect power. - :meth:`is_perfect_power`: If you don't know the base but just want to know if this integer is a perfect power, use this function. - :meth:`is_prime_power`: Checks whether the base is prime.
EXAMPLES::
sage: Integer(64).is_power_of(4) True sage: Integer(64).is_power_of(16) False
TESTS::
sage: Integer(-64).is_power_of(-4) True sage: Integer(-32).is_power_of(-2) True sage: Integer(1).is_power_of(1) True sage: Integer(-1).is_power_of(-1) True sage: Integer(0).is_power_of(1) False sage: Integer(0).is_power_of(0) True sage: Integer(1).is_power_of(0) True sage: Integer(1).is_power_of(8) True sage: Integer(-8).is_power_of(2) False sage: Integer(-81).is_power_of(-3) False
.. NOTE::
For large integers self, is_power_of() is faster than is_perfect_power(). The following examples gives some indication of how much faster.
::
sage: b = lcm(range(1,10000)) sage: b.exact_log(2) 14446 sage: t=cputime() sage: for a in range(2, 1000): k = b.is_perfect_power() sage: cputime(t) # random 0.53203299999999976 sage: t=cputime() sage: for a in range(2, 1000): k = b.is_power_of(2) sage: cputime(t) # random 0.0 sage: t=cputime() sage: for a in range(2, 1000): k = b.is_power_of(3) sage: cputime(t) # random 0.032002000000000308
::
sage: b = lcm(range(1, 1000)) sage: b.exact_log(2) 1437 sage: t=cputime() sage: for a in range(2, 10000): k = b.is_perfect_power() # note that we change the range from the example above sage: cputime(t) # random 0.17201100000000036 sage: t=cputime(); TWO=int(2) sage: for a in range(2, 10000): k = b.is_power_of(TWO) sage: cputime(t) # random 0.0040000000000000036 sage: t=cputime() sage: for a in range(2, 10000): k = b.is_power_of(3) sage: cputime(t) # random 0.040003000000000011 sage: t=cputime() sage: for a in range(2, 10000): k = b.is_power_of(a) sage: cputime(t) # random 0.02800199999999986 """
def is_prime_power(self, *, proof=None, bint get_data=False): r""" Return ``True`` if this integer is a prime power, and ``False`` otherwise.
A prime power is a prime number raised to a positive power. Hence `1` is not a prime power.
For a method that uses a pseudoprimality test instead see :meth:`is_pseudoprime_power`.
INPUT:
- ``proof`` -- Boolean or ``None`` (default). If ``False``, use a strong pseudo-primality test (see :meth:`is_pseudoprime`). If ``True``, use a provable primality test. If unset, use the default arithmetic proof flag.
- ``get_data`` -- (default ``False``), if ``True`` return a pair ``(p,k)`` such that this integer equals ``p^k`` with ``p`` a prime and ``k`` a positive integer or the pair ``(self,0)`` otherwise.
.. SEEALSO::
- :meth:`perfect_power`: Finds the minimal base for which integer is a perfect power. - :meth:`is_perfect_power`: Doesn't test whether the base is prime. - :meth:`is_power_of`: If you know the base already this method is the fastest option. - :meth:`is_pseudoprime_power`: If the entry is very large.
EXAMPLES::
sage: 17.is_prime_power() True sage: 10.is_prime_power() False sage: 64.is_prime_power() True sage: (3^10000).is_prime_power() True sage: (10000).is_prime_power() False sage: (-3).is_prime_power() False sage: 0.is_prime_power() False sage: 1.is_prime_power() False sage: p = next_prime(10^20); p 100000000000000000039 sage: p.is_prime_power() True sage: (p^97).is_prime_power() True sage: (p+1).is_prime_power() False
With the ``get_data`` keyword set to ``True``::
sage: (3^100).is_prime_power(get_data=True) (3, 100) sage: 12.is_prime_power(get_data=True) (12, 0) sage: (p^97).is_prime_power(get_data=True) (100000000000000000039, 97) sage: q = p.next_prime(); q 100000000000000000129 sage: (p*q).is_prime_power(get_data=True) (10000000000000000016800000000000000005031, 0)
The method works for large entries when `proof=False`::
sage: proof.arithmetic(False) sage: ((10^500 + 961)^4).is_prime_power() True sage: proof.arithmetic(True)
We check that :trac:`4777` is fixed::
sage: n = 150607571^14 sage: n.is_prime_power() True """
cdef long p, n # Note that self.value fits in a long, so there is no # overflow possible because of mixing signed/unsigned longs. # We call the PARI function uisprimepower() else: else:
else:
else:
def is_prime(self, proof=None): r""" Test whether ``self`` is prime.
INPUT:
- ``proof`` -- Boolean or ``None`` (default). If False, use a strong pseudo-primality test (see :meth:`is_pseudoprime`). If True, use a provable primality test. If unset, use the :mod:`default arithmetic proof flag <sage.structure.proof.proof>`.
.. NOTE::
Integer primes are by definition *positive*! This is different than Magma, but the same as in PARI. See also the :meth:`is_irreducible()` method.
EXAMPLES::
sage: z = 2^31 - 1 sage: z.is_prime() True sage: z = 2^31 sage: z.is_prime() False sage: z = 7 sage: z.is_prime() True sage: z = -7 sage: z.is_prime() False sage: z.is_irreducible() True
::
sage: z = 10^80 + 129 sage: z.is_prime(proof=False) True sage: z.is_prime(proof=True) True
When starting Sage the arithmetic proof flag is True. We can change it to False as follows::
sage: proof.arithmetic() True sage: n = 10^100 + 267 sage: timeit("n.is_prime()") # not tested 5 loops, best of 3: 163 ms per loop sage: proof.arithmetic(False) sage: proof.arithmetic() False sage: timeit("n.is_prime()") # not tested 1000 loops, best of 3: 573 us per loop
ALGORITHM:
Calls the PARI ``isprime`` function. """
else:
cdef bint _pseudoprime_is_prime(self, proof) except -1: """ Given a pseudoprime, return ``self.is_prime(proof)``.
INPUT:
- ``self`` -- A PARI pseudoprime
- ``proof`` -- Mandatory proof flag (True, False or None)
OUTPUT:
- The result of ``self.is_prime(proof)`` but faster """ else:
def is_irreducible(self): r""" Returns ``True`` if self is irreducible, i.e. +/- prime
EXAMPLES::
sage: z = 2^31 - 1 sage: z.is_irreducible() True sage: z = 2^31 sage: z.is_irreducible() False sage: z = 7 sage: z.is_irreducible() True sage: z = -7 sage: z.is_irreducible() True """
def is_pseudoprime(self): r""" Test whether ``self`` is a pseudoprime.
This uses PARI's Baillie-PSW probabilistic primality test. Currently, there are no known pseudoprimes for Baillie-PSW that are not actually prime. However it is conjectured that there are infinitely many.
See :wikipedia:`Baillie-PSW_primality_test`
EXAMPLES::
sage: z = 2^31 - 1 sage: z.is_pseudoprime() True sage: z = 2^31 sage: z.is_pseudoprime() False """
def is_pseudoprime_power(self, get_data=False): r""" Test if this number is a power of a pseudoprime number.
For large numbers, this method might be faster than :meth:`is_prime_power`.
INPUT:
- ``get_data`` -- (default ``False``) if ``True`` return a pair `(p,k)` such that this number equals `p^k` with `p` a pseudoprime and `k` a positive integer or the pair ``(self,0)`` otherwise.
EXAMPLES::
sage: x = 10^200 + 357 sage: x.is_pseudoprime() True sage: (x^12).is_pseudoprime_power() True sage: (x^12).is_pseudoprime_power(get_data=True) (1000...000357, 12) sage: (997^100).is_pseudoprime_power() True sage: (998^100).is_pseudoprime_power() False sage: ((10^1000 + 453)^2).is_pseudoprime_power() True
TESTS::
sage: 0.is_pseudoprime_power() False sage: (-1).is_pseudoprime_power() False sage: 1.is_pseudoprime_power() False """
def is_perfect_power(self): r""" Returns ``True`` if ``self`` is a perfect power, ie if there exist integers `a` and `b`, `b > 1` with ``self`` `= a^b`.
.. SEEALSO::
- :meth:`perfect_power`: Finds the minimal base for which this integer is a perfect power. - :meth:`is_power_of`: If you know the base already this method is the fastest option. - :meth:`is_prime_power`: Checks whether the base is prime.
EXAMPLES::
sage: Integer(-27).is_perfect_power() True sage: Integer(12).is_perfect_power() False
sage: z = 8 sage: z.is_perfect_power() True sage: 144.is_perfect_power() True sage: 10.is_perfect_power() False sage: (-8).is_perfect_power() True sage: (-4).is_perfect_power() False
TESTS:
This is a test to make sure we work around a bug in GMP, see :trac:`4612`.
::
sage: [ -a for a in srange(100) if not (-a^3).is_perfect_power() ] [] """ cdef mpz_t tmp cdef int res
def is_norm(self, K, element=False, proof=True): r""" See ``QQ(self).is_norm()``.
EXAMPLES::
sage: K = NumberField(x^2 - 2, 'beta') sage: n = 4 sage: n.is_norm(K) True sage: 5.is_norm(K) False sage: 7.is_norm(QQ) True sage: n.is_norm(K, element=True) (True, -4*beta + 6) sage: n.is_norm(K, element=True)[1].norm() 4 sage: n = 5 sage: n.is_norm(K, element=True) (False, None) sage: n = 7 sage: n.is_norm(QQ, element=True) (True, 7)
"""
def _bnfisnorm(self, K, proof=True, extra_primes=0): r""" See ``QQ(self)._bnfisnorm()``.
EXAMPLES::
sage: 3._bnfisnorm(QuadraticField(-1, 'i')) (1, 3) sage: 7._bnfisnorm(CyclotomicField(7)) (-zeta7^5 - zeta7^4 - 2*zeta7^3 - zeta7^2 - zeta7 - 1, 1) """
def jacobi(self, b): r""" Calculate the Jacobi symbol `\left(\frac{self}{b}\right)`.
EXAMPLES::
sage: z = -1 sage: z.jacobi(17) 1 sage: z.jacobi(19) -1 sage: z.jacobi(17*19) -1 sage: (2).jacobi(17) 1 sage: (3).jacobi(19) -1 sage: (6).jacobi(17*19) -1 sage: (6).jacobi(33) 0 sage: a = 3; b = 7 sage: a.jacobi(b) == -b.jacobi(a) True """ cdef long tmp tmp = b if (tmp & 1) == 0: raise ValueError("Jacobi symbol not defined for even b.") return mpz_kronecker_si(self.value, tmp) b = Integer(b) raise ValueError("Jacobi symbol not defined for even b.")
def kronecker(self, b): r""" Calculate the Kronecker symbol `\left(\frac{self}{b}\right)` with the Kronecker extension `(self/2)=(2/self)` when `self` is odd, or `(self/2)=0` when `self` is even.
EXAMPLES::
sage: z = 5 sage: z.kronecker(41) 1 sage: z.kronecker(43) -1 sage: z.kronecker(8) -1 sage: z.kronecker(15) 0 sage: a = 2; b = 5 sage: a.kronecker(b) == b.kronecker(a) True """
def class_number(self, proof=True): r""" Returns the class number of the quadratic order with this discriminant.
INPUT:
- ``self`` -- an integer congruent to `0` or `1\mod4` which is not a square
- ``proof`` (boolean, default ``True``) -- if ``False`` then for negative disscriminants a faster algorithm is used by the PARI library which is known to give incorrect results when the class group has many cyclic factors.
OUTPUT:
(integer) the class number of the quadratic order with this discriminant.
.. NOTE::
This is not always equal to the number of classes of primitive binary quadratic forms of discriminant `D`, which is equal to the narrow class number. The two notions are the same when `D<0`, or `D>0` and the fundamental unit of the order has negative norm; otherwise the number of classes of forms is twice this class number.
EXAMPLES::
sage: (-163).class_number() 1 sage: (-104).class_number() 6 sage: [((4*n+1),(4*n+1).class_number()) for n in [21..29]] [(85, 2), (89, 1), (93, 1), (97, 1), (101, 1), (105, 2), (109, 1), (113, 1), (117, 1)]
TESTS:
The integer must not be a square or an error is raised::
sage: 100.class_number() Traceback (most recent call last): ... ValueError: class_number not defined for square integers
The integer must be 0 or 1 mod 4 or an error is raised::
sage: 10.class_number() Traceback (most recent call last): ... ValueError: class_number only defined for integers congruent to 0 or 1 modulo 4 sage: 3.class_number() Traceback (most recent call last): ... ValueError: class_number only defined for integers congruent to 0 or 1 modulo 4
"""
def radical(self, *args, **kwds): r""" Return the product of the prime divisors of self. Computing the radical of zero gives an error.
EXAMPLES::
sage: Integer(10).radical() 10 sage: Integer(20).radical() 10 sage: Integer(-100).radical() 10 sage: Integer(0).radical() Traceback (most recent call last): ... ArithmeticError: Radical of 0 not defined. """
def squarefree_part(self, long bound=-1): r""" Return the square free part of `x` (=self), i.e., the unique integer `z` that `x = z y^2`, with `y^2` a perfect square and `z` square-free.
Use ``self.radical()`` for the product of the primes that divide self.
If self is 0, just returns 0.
EXAMPLES::
sage: squarefree_part(100) 1 sage: squarefree_part(12) 3 sage: squarefree_part(17*37*37) 17 sage: squarefree_part(-17*32) -34 sage: squarefree_part(1) 1 sage: squarefree_part(-1) -1 sage: squarefree_part(-2) -2 sage: squarefree_part(-4) -1
::
sage: a = 8 * 5^6 * 101^2 sage: a.squarefree_part(bound=2).factor() 2 * 5^6 * 101^2 sage: a.squarefree_part(bound=5).factor() 2 * 101^2 sage: a.squarefree_part(bound=1000) 2 sage: a.squarefree_part(bound=2**14) 2 sage: a = 7^3 * next_prime(2^100)^2 * next_prime(2^200) sage: a / a.squarefree_part(bound=1000) 49 """ cdef Integer z cdef long even_part, p, p2 cdef char switch_p return self return self else: else:
def next_probable_prime(self): """ Returns the next probable prime after self, as determined by PARI.
EXAMPLES::
sage: (-37).next_probable_prime() 2 sage: (100).next_probable_prime() 101 sage: (2^512).next_probable_prime() 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084171 sage: 0.next_probable_prime() 2 sage: 126.next_probable_prime() 127 sage: 144168.next_probable_prime() 144169 """
def next_prime(self, proof=None): r""" Return the next prime after self.
This method calls the PARI ``nextprime`` function.
INPUT:
- ``proof`` - bool or None (default: None, see proof.arithmetic or sage.structure.proof) Note that the global Sage default is proof=True
EXAMPLES::
sage: 100.next_prime() 101 sage: (10^50).next_prime() 100000000000000000000000000000000000000000000000151
Use ``proof=False``, which is way faster since it does not need a primality proof::
sage: b = (2^1024).next_prime(proof=False) sage: b - 2^1024 643
::
sage: Integer(0).next_prime() 2 sage: Integer(1001).next_prime() 1009 """ # Use PARI to compute the next *pseudo*-prime p = Integer(p.__pari__().nextprime(True))
def previous_prime(self, proof=None): r""" Returns the previous prime before self.
This method calls the PARI ``precprime`` function.
INPUT:
- ``proof`` - if ``True`` ensure that the returned value is the next prime power and if set to ``False`` uses probabilistic methods (i.e. the result is not guaranteed). By default it uses global configuration variables to determine which alternative to use (see :mod:`proof.arithmetic` or :mod:`sage.structure.proof`).
.. SEEALSO::
- :meth:`next_prime`
EXAMPLES::
sage: 10.previous_prime() 7 sage: 7.previous_prime() 5 sage: 14376485.previous_prime() 14376463
sage: 2.previous_prime() Traceback (most recent call last): ... ValueError: no prime less than 2
An example using ``proof=False``, which is way faster since it does not need a primality proof::
sage: b = (2^1024).previous_prime(proof=False) sage: 2^1024 - b 105 """ mpz_sub_ui(p.value, p.value, 1) p = Integer(p.__pari__().precprime())
def next_prime_power(self, proof=None): r""" Return the next prime power after self.
INPUT:
- ``proof`` - if ``True`` ensure that the returned value is the next prime power and if set to ``False`` uses probabilistic methods (i.e. the result is not guaranteed). By default it uses global configuration variables to determine which alternative to use (see :mod:`proof.arithmetic` or :mod:`sage.structure.proof`).
ALGORITHM:
The algorithm is naive. It computes the next power of 2 and go through the odd numbers calling :meth:`is_prime_power`.
.. SEEALSO::
- :meth:`previous_prime_power` - :meth:`is_prime_power` - :meth:`next_prime` - :meth:`previous_prime`
EXAMPLES::
sage: (-1).next_prime_power() 2 sage: 2.next_prime_power() 3 sage: 103.next_prime_power() 107 sage: 107.next_prime_power() 109 sage: 2044.next_prime_power() 2048
TESTS::
sage: [(2**k-1).next_prime_power() for k in range(1,10)] [2, 4, 8, 16, 32, 64, 128, 256, 512] sage: [(2**k).next_prime_power() for k in range(10)] [2, 3, 5, 9, 17, 37, 67, 131, 257, 521]
sage: for _ in range(10): ....: n = ZZ.random_element(2**256).next_prime_power() ....: m = n.next_prime_power().previous_prime_power() ....: assert m == n, "problem with n = {}".format(n) """
# return the power of 2 we just skipped
def previous_prime_power(self, proof=None): r""" Return the previous prime power before self.
INPUT:
- ``proof`` - if ``True`` ensure that the returned value is the next prime power and if set to ``False`` uses probabilistic methods (i.e. the result is not guaranteed). By default it uses global configuration variables to determine which alternative to use (see :mod:`proof.arithmetic` or :mod:`sage.structure.proof`).
ALGORITHM:
The algorithm is naive. It computes the previous power of 2 and go through the odd numbers calling the method :meth:`is_prime_power`.
.. SEEALSO::
- :meth:`next_prime_power` - :meth:`is_prime_power` - :meth:`previous_prime` - :meth:`next_prime`
EXAMPLES::
sage: 3.previous_prime_power() 2 sage: 103.previous_prime_power() 101 sage: 107.previous_prime_power() 103 sage: 2044.previous_prime_power() 2039
sage: 2.previous_prime_power() Traceback (most recent call last): ... ValueError: no prime power less than 2
TESTS::
sage: [(2**k+1).previous_prime_power() for k in range(1,10)] [2, 4, 8, 16, 32, 64, 128, 256, 512] sage: [(2**k).previous_prime_power() for k in range(2, 10)] [3, 7, 13, 31, 61, 127, 251, 509]
sage: for _ in range(10): ....: n = ZZ.random_element(3,2**256).previous_prime_power() ....: m = n.previous_prime_power().next_prime_power() ....: assert m == n, "problem with n = {}".format(n) """
# return the power of 2 we just skipped
def additive_order(self): """ Return the additive order of self.
EXAMPLES::
sage: ZZ(0).additive_order() 1 sage: ZZ(1).additive_order() +Infinity """ else:
def multiplicative_order(self): r""" Return the multiplicative order of self.
EXAMPLES::
sage: ZZ(1).multiplicative_order() 1 sage: ZZ(-1).multiplicative_order() 2 sage: ZZ(0).multiplicative_order() +Infinity sage: ZZ(2).multiplicative_order() +Infinity """ else:
def is_squarefree(self): """ Returns True if this integer is not divisible by the square of any prime and False otherwise.
EXAMPLES::
sage: 100.is_squarefree() False sage: 102.is_squarefree() True sage: 0.is_squarefree() False """
cpdef __pari__(self): """ Returns the PARI version of this integer.
EXAMPLES::
sage: n = 9390823 sage: m = n.__pari__(); m 9390823 sage: type(m) <type 'cypari2.gen.Gen'>
TESTS::
sage: n = 10^10000000 sage: m = n.__pari__() ## crash from trac 875 sage: m % 1234567 1041334
"""
def _interface_init_(self, I=None): """ Return canonical string to coerce this integer to any other math software, i.e., just the string representation of this integer in base 10.
EXAMPLES::
sage: n = 9390823 sage: n._interface_init_() '9390823' """
@property def __array_interface__(self): """ Used for NumPy conversion.
EXAMPLES::
sage: import numpy sage: numpy.array([1, 2, 3]) array([1, 2, 3]) sage: numpy.array([1, 2, 3]).dtype dtype('int32') # 32-bit dtype('int64') # 64-bit
sage: numpy.array(2**40).dtype dtype('int64') sage: numpy.array(2**400).dtype dtype('O')
sage: numpy.array([1,2,3,0.1]).dtype dtype('float64') """ return numpy_int64_interface else:
def _magma_init_(self, magma): """ Return string that evaluates in Magma to this element.
For small integers we just use base 10. For large integers we use base 16, but use Magma's StringToInteger command, which (for no good reason) is much faster than 0x[string literal]. We only use base 16 for integers with at least 10000 binary digits, since e.g., for a large list of small integers the overhead of calling StringToInteger can be a killer.
EXAMPLES: sage: (117)._magma_init_(magma) # optional - magma '117'
Large integers use hex: sage: m = 3^(2^20) # optional - magma sage: s = m._magma_init_(magma) # optional - magma sage: 'StringToInteger' in s # optional - magma True sage: magma(m).sage() == m # optional - magma True """ return 'StringToInteger("%s",16)'%self.str(16) else:
def _sage_input_(self, sib, coerced): r""" Produce an expression which will reproduce this value when evaluated.
EXAMPLES::
sage: sage_input(1, verify=True) # Verified 1 sage: sage_input(1, preparse=False) ZZ(1) sage: sage_input(-12435, verify=True) # Verified -12435 sage: sage_input(0, verify=True) # Verified 0 sage: sage_input(-3^70, verify=True) # Verified -2503155504993241601315571986085849 sage: sage_input(-37, preparse=False) -ZZ(37) sage: sage_input(-37 * polygen(ZZ), preparse=False) R = ZZ['x'] x = R.gen() -37*x sage: from sage.misc.sage_input import SageInputBuilder sage: (-314159)._sage_input_(SageInputBuilder(preparse=False), False) {unop:- {call: {atomic:ZZ}({atomic:314159})}} sage: (314159)._sage_input_(SageInputBuilder(preparse=False), True) {atomic:314159} """ else: else:
def sqrtrem(self): r""" Return (s, r) where s is the integer square root of self and r is the remainder such that `\text{self} = s^2 + r`. Raises ``ValueError`` if self is negative.
EXAMPLES::
sage: 25.sqrtrem() (5, 0) sage: 27.sqrtrem() (5, 2) sage: 0.sqrtrem() (0, 0)
::
sage: Integer(-102).sqrtrem() Traceback (most recent call last): ... ValueError: square root of negative integer not defined.
"""
def isqrt(self): r""" Returns the integer floor of the square root of self, or raises an ``ValueError`` if self is negative.
EXAMPLES::
sage: a = Integer(5) sage: a.isqrt() 2
::
sage: Integer(-102).isqrt() Traceback (most recent call last): ... ValueError: square root of negative integer not defined. """
def sqrt(self, prec=None, extend=True, all=False): """ The square root function.
INPUT:
- ``prec`` - integer (default: None): if None, returns an exact square root; otherwise returns a numerical square root if necessary, to the given bits of precision.
- ``extend`` - bool (default: True); if True, return a square root in an extension ring, if necessary. Otherwise, raise a ValueError if the square is not in the base ring. Ignored if prec is not None.
- ``all`` - bool (default: False); if True, return all square roots of self, instead of just one.
EXAMPLES::
sage: Integer(144).sqrt() 12 sage: sqrt(Integer(144)) 12 sage: Integer(102).sqrt() sqrt(102)
::
sage: n = 2 sage: n.sqrt(all=True) [sqrt(2), -sqrt(2)] sage: n.sqrt(prec=10) 1.4 sage: n.sqrt(prec=100) 1.4142135623730950488016887242 sage: n.sqrt(prec=100,all=True) [1.4142135623730950488016887242, -1.4142135623730950488016887242] sage: n.sqrt(extend=False) Traceback (most recent call last): ... ValueError: square root of 2 not an integer sage: Integer(144).sqrt(all=True) [12, -12] sage: Integer(0).sqrt(all=True) [0] sage: type(Integer(5).sqrt()) <type 'sage.symbolic.expression.Expression'> sage: type(Integer(5).sqrt(prec=53)) <type 'sage.rings.real_mpfr.RealNumber'> sage: type(Integer(-5).sqrt(prec=53)) <type 'sage.rings.complex_number.ComplexNumber'>
TESTS:
Check that :trac:`9466` is fixed::
sage: 3.sqrt(extend=False, all=True) [] """
raise ValueError("square root of negative number not an integer")
cdef int non_square cdef mpz_t tmp
else:
@coerce_binop def xgcd(self, Integer n): r""" Return the extended gcd of this element and ``n``.
INPUT:
- ``n`` -- an integer
OUTPUT:
A triple ``(g, s, t)`` such that ``g`` is the non-negative gcd of ``self`` and ``n``, and ``s`` and ``t`` are cofactors satisfying the Bezout identity
.. MATH::
g = s \cdot \mathrm{self} + t \cdot n.
.. NOTE::
There is no guarantee that the cofactors will be minimal. If you need the cofactors to be minimal use :meth:`_xgcd`. Also, using :meth:`_xgcd` directly might be faster in some cases, see :trac:`13628`.
EXAMPLES::
sage: 6.xgcd(4) (2, 1, -1)
"""
def _xgcd(self, Integer n, bint minimal=0): r""" Return the extended gcd of ``self`` and ``n``.
INPUT:
- ``n`` -- an integer - ``minimal`` -- a boolean (default: ``False``), whether to compute minimal cofactors (see below)
OUTPUT:
A triple ``(g, s, t)`` such that ``g`` is the non-negative gcd of ``self`` and ``n``, and ``s`` and ``t`` are cofactors satisfying the Bezout identity
.. MATH::
g = s \cdot \mathrm{self} + t \cdot n.
.. NOTE::
If ``minimal`` is ``False``, then there is no guarantee that the returned cofactors will be minimal in any sense; the only guarantee is that the Bezout identity will be satisfied (see examples below).
If ``minimal`` is ``True``, the cofactors will satisfy the following conditions. If either ``self`` or ``n`` are zero, the trivial solution is returned. If both ``self`` and ``n`` are nonzero, the function returns the unique solution such that `0 \leq s < |n|/g` (which then must also satisfy `0 \leq |t| \leq |\mbox{\rm self}|/g`).
EXAMPLES::
sage: 5._xgcd(7) (1, 3, -2) sage: 5*3 + 7*-2 1 sage: g,s,t = 58526524056._xgcd(101294172798) sage: g 22544886 sage: 58526524056 * s + 101294172798 * t 22544886
Try ``minimal`` option with various edge cases::
sage: 5._xgcd(0, minimal=True) (5, 1, 0) sage: (-5)._xgcd(0, minimal=True) (5, -1, 0) sage: 0._xgcd(5, minimal=True) (5, 0, 1) sage: 0._xgcd(-5, minimal=True) (5, 0, -1) sage: 0._xgcd(0, minimal=True) (0, 1, 0)
Output may differ with and without the ``minimal`` option::
sage: 5._xgcd(6) (1, -1, 1) sage: 5._xgcd(6, minimal=True) (1, 5, -4)
Exhaustive tests, checking minimality conditions::
sage: for a in srange(-20, 20): ....: for b in srange(-20, 20): ....: if a == 0 or b == 0: continue ....: g, s, t = a._xgcd(b) ....: assert g > 0 ....: assert a % g == 0 and b % g == 0 ....: assert a*s + b*t == g ....: g, s, t = a._xgcd(b, minimal=True) ....: assert g > 0 ....: assert a % g == 0 and b % g == 0 ....: assert a*s + b*t == g ....: assert s >= 0 and s < abs(b)/g ....: assert abs(t) <= abs(a)/g
AUTHORS:
- David Harvey (2007-12-26): added minimality option """
# Note: the GMP documentation for mpz_gcdext (or mpn_gcdext for that # matter) makes absolutely no claims about any minimality conditions # satisfied by the returned cofactors. They guarantee a non-negative # gcd, but that's it. So we have to do some work ourselves.
# handle degenerate cases n == 0 and self == 0
# both n and self are nonzero, so we need to do a division and # make the appropriate adjustment
cdef mpz_t u1, u2 else:
cpdef _shift_helper(Integer self, y, int sign): """ Function used to compute left and right shifts of integers. Shifts self y bits to the left if sign is 1, and to the right if sign is -1.
WARNING: This function does no error checking. In particular, it assumes that sign is either 1 or -1,
EXAMPLES::
sage: n = 1234 sage: factor(n) 2 * 617 sage: n._shift_helper(1, 1) 2468 sage: n._shift_helper(1, -1) 617 sage: n._shift_helper(100, 1) 1564280840681635081446931755433984 sage: n._shift_helper(100, -1) 0 sage: n._shift_helper(-100, 1) 0 sage: n._shift_helper(-100, -1) 1564280840681635081446931755433984
TESTS::
sage: 1 << (2^60) # optional - mpir Traceback (most recent call last): ... MemoryError: failed to allocate ... bytes # 64-bit OverflowError: Python int too large to convert to C long # 32-bit
sage: 1 << (2^60) # optional - gmp Traceback (most recent call last): ... RuntimeError: Aborted # 64-bit OverflowError: Python int too large to convert to C long # 32-bit """ cdef long n
# For a Python int, we can just use the Python/C API. else: # If it's not already an Integer, try to convert it. except ValueError: return bin_op(self, y, operator.lshift if sign == 1 else operator.rshift)
# If y wasn't a Python int, it's now an Integer, so set n # accordingly. # Doesn't fit in a long so shifting to the right by # this much will be 0. else: # Doesn't fit in a long so shifting to the left by # this much will raise appropriate overflow error n = y
# Decide which way we're shifting
# Now finally call into MPIR to do the shifting. else:
def __lshift__(x, y): """ Shift x to the left by y bits.
EXAMPLES::
sage: 32 << 2 128 sage: 32 << int(2) 128 sage: int(32) << 2 128 sage: 1 << 2.5 Traceback (most recent call last): ... TypeError: unsupported operands for <<: 1, 2.5000...
sage: 32 << (4/2) 128
A negative shift to the left is treated as a right shift::
sage: 128 << -2 32 sage: 128 << (-2^100) 0 """ # note that x need not be self -- int(3) << ZZ(2) will # dispatch this function
def __rshift__(x, y): """ Shift x to the right by y bits.
EXAMPLES::
sage: 32 >> 2 8 sage: 32 >> int(2) 8 sage: int(32) >> 2 8 sage: 1 >> 2.5 Traceback (most recent call last): ... TypeError: unsupported operands for >>: 1, 2.5000... sage: 10^5 >> 10^100 0
A negative shift to the right is treated as a left shift::
sage: 8 >> -2 32 """ # note that x need not be self -- int(3) >> ZZ(2) will # dispatch this function
cdef _and(Integer self, Integer other):
def __and__(x, y): """ Return the bitwise and two integers.
EXAMPLES::
sage: n = Integer(6); m = Integer(2) sage: n & m 2 sage: n.__and__(m) 2 """
cdef _or(Integer self, Integer other):
def __or__(x, y): """ Return the bitwise or of the integers x and y.
EXAMPLES::
sage: n = 8; m = 4 sage: n.__or__(m) 12 """ return bin_op(x, y, operator.or_)
def __invert__(self): """ Return the multiplicative inverse of self, as a rational number.
EXAMPLES::
sage: n = 10 sage: 1/n 1/10 sage: n.__invert__() 1/10 sage: n = -3 sage: ~n -1/3 """ cdef Rational x
def inverse_of_unit(self): """ Return inverse of self if self is a unit in the integers, i.e., self is -1 or 1. Otherwise, raise a ZeroDivisionError.
EXAMPLES::
sage: (1).inverse_of_unit() 1 sage: (-1).inverse_of_unit() -1 sage: 5.inverse_of_unit() Traceback (most recent call last): ... ArithmeticError: inverse does not exist sage: 0.inverse_of_unit() Traceback (most recent call last): ... ArithmeticError: inverse does not exist """ else:
def inverse_mod(self, n): """ Returns the inverse of self modulo `n`, if this inverse exists. Otherwise, raises a ``ZeroDivisionError`` exception.
INPUT:
- ``self`` - Integer
- ``n`` - Integer, or ideal of integer ring
OUTPUT:
- ``x`` - Integer such that x\*self = 1 (mod m), or raises ZeroDivisionError.
IMPLEMENTATION:
Call the mpz_invert GMP library function.
EXAMPLES::
sage: a = Integer(189) sage: a.inverse_mod(10000) 4709 sage: a.inverse_mod(-10000) 4709 sage: a.inverse_mod(1890) Traceback (most recent call last): ... ZeroDivisionError: Inverse does not exist. sage: a = Integer(19)**100000 sage: b = a*a sage: c = a.inverse_mod(b) Traceback (most recent call last): ... ZeroDivisionError: Inverse does not exist.
We check that :trac:`10625` is fixed::
sage: ZZ(2).inverse_mod(ZZ.ideal(3)) 2
We check that :trac:`9955` is fixed::
sage: Rational(3)%Rational(-1) 0 """ cdef int r
def gcd(self, n): """ Return the greatest common divisor of self and `n`.
EXAMPLES::
sage: gcd(-1,1) 1 sage: gcd(0,1) 1 sage: gcd(0,0) 0 sage: gcd(2,2^6) 2 sage: gcd(21,2^6) 1 """
def crt(self, y, m, n): """ Return the unique integer between `0` and `mn` that is congruent to the integer modulo `m` and to `y` modulo `n`. We assume that `m` and `n` are coprime.
EXAMPLES::
sage: n = 17 sage: m = n.crt(5, 23, 11); m 247 sage: m%23 17 sage: m%11 5 """ cdef object g, s, t cdef Integer _y, _m, _n raise ArithmeticError("CRT requires that gcd of moduli is 1.") # Now s*m + t*n = 1, so the answer is x + (y-x)*s*m, where x=self.
def test_bit(self, long index): r""" Return the bit at ``index``.
If the index is negative, returns 0.
Although internally a sign-magnitude representation is used for integers, this method pretends to use a two's complement representation. This is illustrated with a negative integer below.
EXAMPLES::
sage: w = 6 sage: w.str(2) '110' sage: w.test_bit(2) 1 sage: w.test_bit(-1) 0 sage: x = -20 sage: x.str(2) '-10100' sage: x.test_bit(4) 0 sage: x.test_bit(5) 1 sage: x.test_bit(6) 1 """ else:
def popcount(self): """ Return the number of 1 bits in the binary representation. If self<0, we return Infinity.
EXAMPLES::
sage: n = 123 sage: n.str(2) '1111011' sage: n.popcount() 6
sage: n = -17 sage: n.popcount() +Infinity """
def conjugate(self): """ Return the complex conjugate of this integer, which is the integer itself.
EXAMPLES: sage: n = 205 sage: n.conjugate() 205 """
def binomial(self, m, algorithm='mpir'): """ Return the binomial coefficient "self choose m".
INPUT:
- ``m`` -- an integer
- ``algorithm`` -- ``'mpir'`` (default) or ``'pari'``; ``'mpir'`` is faster for small ``m``, and ``'pari'`` tends to be faster for large ``m``
OUTPUT:
- integer
EXAMPLES::
sage: 10.binomial(2) 45 sage: 10.binomial(2, algorithm='pari') 45 sage: 10.binomial(-2) 0 sage: (-2).binomial(3) -4 sage: (-3).binomial(0) 1
The argument ``m`` or (``self-m``) must fit into unsigned long::
sage: (2**256).binomial(2**256) 1 sage: (2**256).binomial(2**256-1) 115792089237316195423570985008687907853269984665640564039457584007913129639936 sage: (2**256).binomial(2**128) Traceback (most recent call last): ... OverflowError: m must fit in an unsigned long
TESTS::
sage: 0.binomial(0) 1 sage: 0.binomial(1) 0 sage: 0.binomial(-1) 0 sage: 13.binomial(2r) 78
Check that it can be interrupted (:trac:`17852`)::
sage: alarm(0.5); (2^100).binomial(2^22, algorithm='mpir') Traceback (most recent call last): ... AlarmInterrupt
For PARI, we try 10 interrupts with increasing intervals to check for reliable interrupting, see :trac:`18919`::
sage: from cysignals import AlarmInterrupt sage: for i in [1..10]: # long time (5s) ....: try: ....: alarm(i/11) ....: (2^100).binomial(2^22, algorithm='pari') ....: except AlarmInterrupt: ....: pass """ cdef Integer x cdef Integer mm
else:
# trivial cases and potential simplification binom(n,x) -> binom(n,n-x)
# now call the various backend else: else: raise ValueError("algorithm must be one of: 'pari', 'mpir'")
cdef int mpz_set_str_python(mpz_ptr z, char* s, int base) except -1: """ Wrapper around ``mpz_set_str()`` which supports :pep:`3127` literals.
If the string is invalid, a ``TypeError`` will be raised.
INPUT:
- ``z`` -- A pre-allocated ``mpz_t`` where the result will be stored.
- ``s`` -- A string to be converted to an ``mpz_t``.
- ``base`` -- Either 0 or a base between 2 and 36: a base to use for the string conversion. 0 means auto-detect using prefixes.
EXAMPLES::
sage: Integer('12345') 12345 sage: Integer(' - 1 2 3 4 5 ') -12345 sage: Integer(u' - 0x 1 2 3 4 5 ') -74565 sage: Integer('-0012345', 16) -74565 sage: Integer('+0x12345') 74565 sage: Integer('0X12345', 16) Traceback (most recent call last): ... TypeError: unable to convert '0X12345' to an integer sage: Integer('0x12345', 1000) Traceback (most recent call last): ... ValueError: base (=1000) must be 0 or between 2 and 36 sage: Integer('0x00DeadBeef') 3735928559 sage: Integer('0x0x12345') Traceback (most recent call last): ... TypeError: unable to convert '0x0x12345' to an integer sage: Integer('-0B100') -4 sage: Integer('-0B100', 16) -45312 sage: Integer('0B12345') Traceback (most recent call last): ... TypeError: unable to convert '0B12345' to an integer
Test zeros::
sage: Integer('') Traceback (most recent call last): ... TypeError: unable to convert '' to an integer sage: Integer("0") 0 sage: Integer(" 0O 0 ") # second character is the letter O 0 sage: Integer("-00") 0 sage: Integer("+00000", 4) 0
For octals, the old leading-zero style is deprecated (unless an explicit base is given)::
sage: Integer('0o12') 10 sage: Integer('012', 8) 10 sage: Integer('012') doctest:...: DeprecationWarning: use 0o as octal prefix instead of 0 If you do not want this number to be interpreted as octal, remove the leading zeros. See http://trac.sagemath.org/17413 for details. 10
We disallow signs in unexpected places::
sage: Integer('+ -0') Traceback (most recent call last): ... TypeError: unable to convert '+ -0' to an integer sage: Integer('0o-0') Traceback (most recent call last): ... TypeError: unable to convert '0o-0' to an integer """
# Check for signs
# If no base was given, check for PEP 3127 prefixes else: # String starts with "0" else: # Give deprecation warning about octals, unless the # number is zero (to allow for "0").
# Disallow a sign here
from sage.misc.lazy_import import lazy_import lazy_import('sage.arith.functions', 'LCM_list', deprecation=22630)
def GCD_list(v): r""" Return the greatest common divisor of a list of integers.
INPUT:
- ``v`` -- list or tuple
Elements of `v` are converted to Sage integers. An empty list has GCD zero.
This function is used, for example, by ``rings/arith.py``.
EXAMPLES::
sage: from sage.rings.integer import GCD_list sage: w = GCD_list([3,9,30]); w 3 sage: type(w) <type 'sage.rings.integer.Integer'>
Check that the bug reported in :trac:`3118` has been fixed::
sage: sage.rings.integer.GCD_list([2,2,3]) 1
The inputs are converted to Sage integers.
::
sage: w = GCD_list([int(3), int(9), '30']); w 3 sage: type(w) <type 'sage.rings.integer.Integer'>
Check that the GCD of the empty list is zero (:trac:`17257`)::
sage: GCD_list([]) 0 """
elif n == 1:
def make_integer(s): """ Create a Sage integer from the base-32 Python *string* s. This is used in unpickling integers.
EXAMPLES::
sage: from sage.rings.integer import make_integer sage: make_integer('-29') -73 sage: make_integer(29) Traceback (most recent call last): ... TypeError: expected str...Integer found """
cdef class int_to_Z(Morphism): """ Morphism from Python ints to Sage integers.
EXAMPLES::
sage: f = ZZ.coerce_map_from(int); type(f) <type 'sage.rings.integer.int_to_Z'> sage: f(5r) 5 sage: type(f(5r)) <type 'sage.rings.integer.Integer'> sage: 1 + 2r 3 sage: type(1 + 2r) <type 'sage.rings.integer.Integer'>
This is intented for internal use by the coercion system, to facilitate fast expressions mixing ints and more complex Python types. Note that (as with all morphisms) the input is forcably coerced to the domain ``int`` if it is not already of the correct type which may have undesirable results::
sage: f.domain() Set of Python objects of class 'int' sage: f(1/3) 0 sage: f(1.7) 1 sage: f("10") 10
A pool is used for small integers::
sage: f(10) is f(10) True sage: f(-2) is f(-2) True """
def __init__(self): """ TESTS::
sage: f = ZZ.coerce_map_from(int) sage: f.parent() Set of Morphisms from Set of Python objects of class 'int' to Integer Ring in Category of sets """ import sage.categories.homset from sage.structure.parent import Set_PythonType Morphism.__init__(self, sage.categories.homset.Hom(Set_PythonType(int), integer_ring.ZZ))
cpdef Element _call_(self, a): """ Returns a new integer with the same value as a.
TESTS::
sage: f = ZZ.coerce_map_from(int) sage: f(100r) 100 """
def _repr_type(self): """ TESTS::
sage: f = ZZ.coerce_map_from(int) sage: print(f) Native morphism: From: Set of Python objects of class 'int' To: Integer Ring """
cdef class long_to_Z(Morphism): """ EXAMPLES::
sage: f = ZZ.coerce_map_from(long); f Native morphism: From: Set of Python objects of class 'long' To: Integer Ring sage: f(1rL) 1 sage: f(-10000000000000000000001r) -10000000000000000000001 """ def __init__(self): import sage.categories.homset from sage.structure.parent import Set_PythonType Morphism.__init__(self, sage.categories.homset.Hom(Set_PythonType(long), integer_ring.ZZ))
cpdef Element _call_(self, a): cdef Integer r cdef long l
def _repr_type(self):
############### INTEGER CREATION CODE #####################
# This variable holds the size of any Integer object in bytes. cdef int sizeof_Integer
# We use a global Integer element to steal all the references # from. DO NOT INITIALIZE IT AGAIN and DO NOT REFERENCE IT! cdef Integer global_dummy_Integer global_dummy_Integer = Integer()
# A global pool for performance when integers are rapidly created and destroyed. # It operates on the following principles: # # - The pool starts out empty. # - When an new integer is needed, one from the pool is returned # if available, otherwise a new Integer object is created # - When an integer is collected, it will add it to the pool # if there is room, otherwise it will be deallocated. cdef int integer_pool_size = 100
cdef PyObject** integer_pool cdef int integer_pool_count = 0
# used for profiling the pool cdef int total_alloc = 0 cdef int use_pool = 0
cdef PyObject* fast_tp_new(type t, args, kwds) except NULL: global integer_pool, integer_pool_count, total_alloc, use_pool
cdef PyObject* new cdef mpz_ptr new_mpz
# for profiling pool usage # total_alloc += 1
# If there is a ready integer in the pool, we will # decrement the counter and return that.
# for profiling pool usage # use_pool += 1
# Otherwise, we have to create one. else:
# allocate enough room for the Integer, sizeof_Integer is # sizeof(Integer). The use of PyObject_Malloc directly # assumes that Integers are not garbage collected, i.e. # they do not possess references to other Python # objects (as indicated by the Py_TPFLAGS_HAVE_GC flag). # See below for a more detailed description. raise MemoryError
# Now set every member as set in z, the global dummy Integer # created before this tp_new started to operate.
# We allocate memory for the _mp_d element of the value of this # new Integer. We allocate one limb. Normally, one would use # mpz_init() for this, but we allocate the memory directly. # This saves time both by avoiding extra function calls and # because the rest of the mpz struct was already initialized # fully using the memcpy above. # # What is done here is potentially very dangerous as it reaches # deeply into the internal structure of GMP. Consequently things # may break if a new release of GMP changes some internals. To # emphasize this, this is what the GMP manual has to say about # the documentation for the struct we are using: # # "This chapter is provided only for informational purposes and the # various internals described here may change in future GMP releases. # Applications expecting to be compatible with future releases should use # only the documented interfaces described in previous chapters."
# This line is only needed if Python is compiled in debugging mode # './configure --with-pydebug' or SAGE_DEBUG=yes. If that is the # case a Python object has a bunch of debugging fields which are # initialized with this macro.
# The global_dummy_Integer may have a reference count larger than # one, but it is expected that newly created objects have a # reference count of one. This is potentially unneeded if # everybody plays nice, because the gobal_dummy_Integer has only # one reference in that case.
# Objects from the pool have reference count zero, so this # needs to be set in this case.
cdef void fast_tp_dealloc(PyObject* o):
# If there is room in the pool for a used integer object, # then put it in rather than deallocating it.
global integer_pool, integer_pool_count
# Here we free any extra memory used by the mpz_t by # setting it to a single limb.
# It's cheap to zero out an integer, so do it here.
# And add it to the pool.
# Again, we move to the mpz_t and clear it. As in fast_tp_new, # we free the memory directly.
# Free the object. This assumes that Py_TPFLAGS_HAVE_GC is not # set. If it was set another free function would need to be # called.
from sage.misc.allocator cimport hook_tp_functions cdef hook_fast_tp_functions(): """ Initialize the fast integer creation functions. """ global global_dummy_Integer, sizeof_Integer, integer_pool
integer_pool = <PyObject**>check_allocarray(integer_pool_size, sizeof(PyObject*))
cdef PyObject* o o = <PyObject *>global_dummy_Integer
# store how much memory needs to be allocated for an Integer. sizeof_Integer = o.ob_type.tp_basicsize
# Finally replace the functions called when an Integer needs # to be constructed/destructed. hook_tp_functions(global_dummy_Integer, <newfunc>(&fast_tp_new), <destructor>(&fast_tp_dealloc), False)
cdef integer(x): if isinstance(x, Integer): return x return Integer(x)
def free_integer_pool(): cdef int i cdef PyObject *o
global integer_pool_count, integer_pool_size
for i from 0 <= i < integer_pool_count: o = integer_pool[i] mpz_clear( (<Integer>o).value ) # Free the object. This assumes that Py_TPFLAGS_HAVE_GC is not # set. If it was set another free function would need to be # called. PyObject_Free(o)
integer_pool_size = 0 integer_pool_count = 0 sig_free(integer_pool)
# Replace default allocation and deletion with faster custom ones hook_fast_tp_functions()
# zero and one initialization initialized = False cdef set_zero_one_elements(): global the_integer_ring, initialized if initialized: return the_integer_ring._zero_element = Integer(0) the_integer_ring._one_element = Integer(1) initialized = True set_zero_one_elements()
cdef Integer zero = the_integer_ring._zero_element cdef Integer one = the_integer_ring._one_element
# pool of small integer for fast sign computation # Use the same defaults as Python, documented at http://docs.python.org/2/c-api/int.html#PyInt_FromLong DEF small_pool_min = -5 DEF small_pool_max = 256 # we could use the above zero and one here cdef list small_pool = [Integer(k) for k in range(small_pool_min, small_pool_max+1)]
cdef inline Integer smallInteger(long value): """ This is the fastest way to create a (likely) small Integer. """ cdef Integer z else:
# The except value is just some random double, it doesn't matter what it is. cdef double mpz_get_d_nearest(mpz_t x) except? -648555075988944.5: """ Convert a ``mpz_t`` to a ``double``, with round-to-nearest-even. This differs from ``mpz_get_d()`` which does round-to-zero.
TESTS::
sage: x = ZZ(); float(x) 0.0 sage: x = 2^54 - 1 sage: float(x) 1.8014398509481984e+16 sage: float(-x) -1.8014398509481984e+16 sage: x = 2^10000; float(x) inf sage: float(-x) -inf
::
sage: x = (2^53 - 1) * 2^971; float(x) # Largest double 1.7976931348623157e+308 sage: float(-x) -1.7976931348623157e+308 sage: x = (2^53) * 2^971; float(x) inf sage: float(-x) -inf sage: x = ZZ((2^53 - 1/2) * 2^971); float(x) inf sage: float(-x) -inf sage: x = ZZ((2^53 - 3/4) * 2^971); float(x) 1.7976931348623157e+308 sage: float(-x) -1.7976931348623157e+308
AUTHORS:
- Jeroen Demeyer (:trac:`16385`, based on :trac:`14416`) """
# Easy case: x is exactly representable as double.
# Check for overflow else:
# General case
# We should shift x right by this amount in order # to have 54 bits remaining.
# Compute q = trunc(x / 2^shift) and let remainder_is_zero be True # if and only if no truncation occurred. cdef int remainder_is_zero
cdef mpz_t q
# Convert abs(q) to a 64-bit integer. cdef uint64_t q64 else: assert sizeof(mp_limb_t) == 4 q64 = q_limbs[1] q64 = (q64 << 32) + q_limbs[0]
# Round q from 54 to 53 bits of precision. # Round towards zero pass else: # Remainder is non-zero: round away from zero else: # Halfway case: round to even
# The conversion of q64 to double is *exact*. # This is because q64 is even and satisfies 2^53 <= q64 <= 2^54. |