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""" Rational Numbers
AUTHORS:
- William Stein (2005): first version
- William Stein (2006-02-22): floor and ceil (pure fast GMP versions).
- Gonzalo Tornaria and William Stein (2006-03-02): greatly improved python/GMP conversion; hashing
- William Stein and Naqi Jaffery (2006-03-06): height, sqrt examples, and improve behavior of sqrt.
- David Harvey (2006-09-15): added nth_root
- Pablo De Napoli (2007-04-01): corrected the implementations of multiplicative_order, is_one; optimized __nonzero__ ; documented: lcm,gcd
- John Cremona (2009-05-15): added support for local and global logarithmic heights.
- Travis Scrimshaw (2012-10-18): Added doctests for full coverage.
- Vincent Delecroix (2013): continued fraction
- Vincent Delecroix (2017-05-03): faster integer-rational comparison
- Vincent Klein (2017-05-11): add __mpq__() to class Rational
- Vincent Klein (2017-05-22): Rational constructor support gmpy2.mpq or gmpy2.mpz parameter. Add __mpz__ to class Rational.
TESTS::
sage: a = -2/3 sage: a == loads(dumps(a)) True """
#***************************************************************************** # Copyright (C) 2004, 2006 William Stein <wstein@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
from cpython cimport * from cpython.object cimport Py_EQ, Py_NE
from cysignals.signals cimport sig_on, sig_off
import sys import operator import fractions
from sage.misc.mathml import mathml from sage.arith.long cimport pyobject_to_long, integer_check_long_py from sage.cpython.string cimport char_to_str, str_to_bytes
import sage.misc.misc as misc from sage.structure.sage_object cimport SageObject from sage.structure.richcmp cimport rich_to_bool_sgn import sage.rings.rational_field
cimport sage.rings.integer as integer from .integer cimport Integer
from cypari2.paridecl cimport * from cypari2.gen cimport Gen as pari_gen from sage.libs.pari.convert_gmp cimport INT_to_mpz, INTFRAC_to_mpq, new_gen_from_mpq_t
from .integer_ring import ZZ from sage.arith.rational_reconstruction cimport mpq_rational_reconstruction
from sage.structure.coerce cimport is_numpy_type
from sage.libs.gmp.pylong cimport mpz_set_pylong
from sage.structure.element cimport Element, RingElement, ModuleElement, coercion_model from sage.structure.element import bin_op, coerce_binop from sage.structure.parent cimport Parent from sage.categories.morphism cimport Morphism from sage.categories.map cimport Map
import sage.rings.real_mpfr import sage.rings.real_double from libc.stdint cimport uint64_t from sage.libs.gmp.binop cimport mpq_add_z, mpq_mul_z, mpq_div_zz
from cpython.int cimport PyInt_AS_LONG
cimport sage.rings.fast_arith import sage.rings.fast_arith
cdef sage.rings.fast_arith.arith_int ai ai = sage.rings.fast_arith.arith_int()
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 object numpy_double_interface = {'typestr': '=f8'}
from libc.math cimport ldexp from sage.libs.gmp.all cimport *
IF HAVE_GMPY2: cimport gmpy2 gmpy2.import_gmpy2()
cdef class Rational(sage.structure.element.FieldElement)
cdef inline void set_from_mpq(Rational self, mpq_t value): mpq_set(self.value, value)
cdef inline void set_from_Rational(Rational self, Rational other):
cdef inline void set_from_Integer(Rational self, integer.Integer other):
cdef object Rational_mul_(Rational a, Rational b): cdef Rational x x = <Rational> Rational.__new__(Rational)
sig_on() mpq_mul(x.value, a.value, b.value) sig_off()
return x
cdef object Rational_div_(Rational a, Rational b): cdef Rational x x = <Rational> Rational.__new__(Rational)
sig_on() mpq_div(x.value, a.value, b.value) sig_off()
return x
cdef Rational_add_(Rational self, Rational other): cdef Rational x x = <Rational> Rational.__new__(Rational) sig_on() mpq_add(x.value, self.value, other.value) sig_off() return x
cdef Rational_sub_(Rational self, Rational other): cdef Rational x x = <Rational> Rational.__new__(Rational)
sig_on() mpq_sub(x.value, self.value, other.value) sig_off()
return x
cdef Parent the_rational_ring = sage.rings.rational_field.Q
# make sure zero/one elements are set cdef set_zero_one_elements(): global the_rational_ring the_rational_ring._zero_element = Rational(0) the_rational_ring._one_element = Rational(1)
set_zero_one_elements()
cpdef Integer integer_rational_power(Integer a, Rational b): """ Compute `a^b` as an integer, if it is integral, or return ``None``.
The nonnegative real root is taken for even denominators.
INPUT:
- a -- an ``Integer`` - b -- a nonnegative ``Rational``
OUTPUT:
`a^b` as an ``Integer`` or ``None``
EXAMPLES::
sage: from sage.rings.rational import integer_rational_power sage: integer_rational_power(49, 1/2) 7 sage: integer_rational_power(27, 1/3) 3 sage: integer_rational_power(-27, 1/3) is None True sage: integer_rational_power(-27, 2/3) is None True sage: integer_rational_power(512, 7/9) 128
sage: integer_rational_power(27, 1/4) is None True sage: integer_rational_power(-16, 1/4) is None True
sage: integer_rational_power(0, 7/9) 0 sage: integer_rational_power(1, 7/9) 1 sage: integer_rational_power(-1, 7/9) is None True sage: integer_rational_power(-1, 8/9) is None True sage: integer_rational_power(-1, 9/8) is None True
TESTS (:trac:`11228`)::
sage: integer_rational_power(-10, QQ(2)) 100 sage: integer_rational_power(0, QQ(0)) 1 """ raise ValueError("Only positive exponents supported.") cdef bint exact pass # z is 0 else: # too big to take roots/powers return None else: else:
cpdef rational_power_parts(a, b, factor_limit=10**5): """ Compute rationals or integers `c` and `d` such that `a^b = c*d^b` with `d` small. This is used for simplifying radicals.
INPUT:
- ``a`` -- a rational or integer - ``b`` -- a rational - ``factor_limit`` -- the limit used in factoring ``a``
EXAMPLES::
sage: from sage.rings.rational import rational_power_parts sage: rational_power_parts(27, 1/2) (3, 3) sage: rational_power_parts(-128, 3/4) (8, -8) sage: rational_power_parts(-4, 1/2) (2, -1) sage: rational_power_parts(-4, 1/3) (1, -4) sage: rational_power_parts(9/1000, 1/2) (3/10, 1/10)
TESTS:
Check if :trac:`8540` is fixed::
sage: rational_power_parts(3/4, -1/2) (2, 3) sage: t = (3/4)^(-1/2); t 2/3*sqrt(3) sage: t^2 4/3
Check if :trac:`15605` is fixed::
sage: rational_power_parts(-1, -1/3) (1, -1) sage: (-1)^(-1/3) -(-1)^(2/3) sage: 1 / ((-1)^(1/3)) -(-1)^(2/3) sage: rational_power_parts(-1, 2/3) (1, -1) sage: (-1)^(2/3) (-1)^(2/3) sage: all(rational_power_parts(-1, i/77) == (1,-1) for i in range(1,9)) True sage: (-1)^(1/3)*(-1)^(1/5) (-1)^(8/15) sage: bool((-1)^(2/3) == -1/2 + sqrt(3)/2*I) True sage: all((-1)^(p/q) == cos(p*pi/q) + I * sin(p*pi/q) for p in srange(1,6) for q in srange(1,6)) True """ a = Integer(a) else:
def is_Rational(x): """ Return true if x is of the Sage rational number type.
EXAMPLES::
sage: from sage.rings.rational import is_Rational sage: is_Rational(2) False sage: is_Rational(2/1) True sage: is_Rational(int(2)) False sage: is_Rational(long(2)) False sage: is_Rational('5') False """
cdef class Rational(sage.structure.element.FieldElement): """ A rational number.
Rational numbers are implemented using the GMP C library.
EXAMPLES::
sage: a = -2/3 sage: type(a) <type 'sage.rings.rational.Rational'> sage: parent(a) Rational Field sage: Rational('1/0') Traceback (most recent call last): ... TypeError: unable to convert '1/0' to a rational sage: Rational(1.5) 3/2 sage: Rational('9/6') 3/2 sage: Rational((2^99,2^100)) 1/2 sage: Rational(("2", "10"), 16) 1/8 sage: Rational(QQbar(125/8).nth_root(3)) 5/2 sage: Rational(AA(209735/343 - 17910/49*golden_ratio).nth_root(3) + 3*AA(golden_ratio)) 53/7 sage: QQ(float(1.5)) 3/2 sage: QQ(RDF(1.2)) 6/5
Conversion from fractions::
sage: import fractions sage: f = fractions.Fraction(1r, 2r) sage: Rational(f) 1/2
Conversion from PARI::
sage: Rational(pari('-939082/3992923')) -939082/3992923 sage: Rational(pari('Pol([-1/2])')) #9595 -1/2
Conversions from numpy::
sage: import numpy as np sage: QQ(np.int8('-15')) -15 sage: QQ(np.int16('-32')) -32 sage: QQ(np.int32('-19')) -19 sage: QQ(np.uint32('1412')) 1412
sage: QQ(np.float16('12')) 12
Conversions from gmpy2::
sage: from gmpy2 import * # optional - gmpy2 sage: QQ(mpq('3/4')) # optional - gmpy2 3/4 sage: QQ(mpz(42)) # optional - gmpy2 42 sage: Rational(mpq(2/3)) # optional - gmpy2 2/3 sage: Rational(mpz(5)) # optional - gmpy2 5 """ def __cinit__(self): r""" Initialize ``self`` as an element of `\QQ`.
EXAMPLES::
sage: p = Rational(3) # indirect doctest sage: p.parent() Rational Field """ global the_rational_ring
def __init__(self, x=None, unsigned int base=0): """ Create a new rational number.
INPUT:
- ``x`` - object (default: ``None``)
- ``base`` - base if ``x`` is a string
EXAMPLES::
sage: a = Rational() sage: a.__init__(7); a 7 sage: a.__init__('70', base=8); a 56 sage: a.__init__(pari('2/3')); a 2/3 sage: a.__init__('-h/3ki', 32); a -17/3730 sage: from gmpy2 import mpq # optional - gmpy2 sage: a.__init__(mpq('3/5')); a # optional - gmpy2 3/5
TESTS:
Check that :trac:`19835` is fixed::
sage: QQ((0r,-1r)) 0 sage: QQ((-1r,-1r)) 1
.. NOTE::
This is for demonstration purposes only, mutating rationals is almost always the wrong thing to do. """
def __reduce__(self): """ Used in pickling rational numbers.
EXAMPLES::
sage: a = 3/5 sage: a.__reduce__() (<built-in function make_rational>, ('3/5',)) """
def __index__(self): """ Needed so integers can be used as list indices.
EXAMPLES::
sage: v = [1,2,3,4,5] sage: v[3/1] 4 sage: v[3/2] Traceback (most recent call last): ... TypeError: rational is not an integer """
def _reduce_set(self, s): """ Used in setting a rational number when unpickling. Do not call this from external code since it violates immutability.
INPUT:
- ``s`` - string representation of rational in base 32
EXAMPLES::
sage: a = -17/3730; _, (s,) = a.__reduce__(); s '-h/3ki' sage: b = 2/3; b._reduce_set('-h/3ki'); b -17/3730
sage: Rational(pari(-345/7687)) -345/7687 sage: Rational(pari(-345)) -345 sage: Rational(pari('Mod(2,3)')) 2 sage: Rational(pari('x')) Traceback (most recent call last): ... TypeError: Unable to coerce PARI x to an Integer """
cdef __set_value(self, x, unsigned int base): cdef int n cdef Rational temp_rational cdef integer.Integer a, b
mpz_set_pylong(mpq_numref(self.value), x)
else: # Truncate in base 10 to match repr(x). # See https://trac.sagemath.org/ticket/21124 raise TypeError("unable to convert {!r} to a rational".format(x)) else: n = mpq_set_str(self.value, xstr, base) if n or mpz_cmp_si(mpq_denref(self.value), 0) == 0: raise TypeError("unable to convert {!r} to a rational".format(x)) mpq_canonicalize(self.value) raise TypeError("unable to convert {!r} to a rational".format(x))
else: else:
else:
mpq_set(self.value, temp_rational.value)
self.__set_value(integer.Integer(x), base) else: raise TypeError("unable to convert {!r} to a rational".format(x))
elif HAVE_GMPY2 and type(x) is gmpy2.mpq: mpq_set(self.value, (<gmpy2.mpq>x).q)
elif HAVE_GMPY2 and type(x) is gmpy2.mpz: mpq_set_z(self.value, (<gmpy2.mpz>x).z)
else:
cdef void set_from_mpq(Rational self, mpq_t value):
def list(self): """ Return a list with the rational element in it, to be compatible with the method for number fields.
OUTPUT:
- ``list`` - the list ``[self]``
EXAMPLES::
sage: m = 5/3 sage: m.list() [5/3] """
def continued_fraction_list(self, type="std"): r""" Return the list of partial quotients of this rational number.
INPUT:
- ``type`` - either "std" (the default) for the standard continued fractions or "hj" for the Hirzebruch-Jung ones.
EXAMPLES::
sage: (13/9).continued_fraction_list() [1, 2, 4] sage: 1 + 1/(2 + 1/4) 13/9
sage: (225/157).continued_fraction_list() [1, 2, 3, 4, 5] sage: 1 + 1/(2 + 1/(3 + 1/(4 + 1/5))) 225/157
sage: (fibonacci(20)/fibonacci(19)).continued_fraction_list() [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2]
sage: (-1/3).continued_fraction_list() [-1, 1, 2]
Check that the partial quotients of an integer ``n`` is simply ``[n]``::
sage: QQ(1).continued_fraction_list() [1] sage: QQ(0).continued_fraction_list() [0] sage: QQ(-1).continued_fraction_list() [-1]
Hirzebruch-Jung continued fractions::
sage: (11/19).continued_fraction_list("hj") [1, 3, 2, 3, 2] sage: 1 - 1/(3 - 1/(2 - 1/(3 - 1/2))) 11/19
sage: (225/137).continued_fraction_list("hj") [2, 3, 5, 10] sage: 2 - 1/(3 - 1/(5 - 1/10)) 225/137
sage: (-23/19).continued_fraction_list("hj") [-1, 5, 4] sage: -1 - 1/(5 - 1/4) -23/19 """ cdef Integer z cdef mpz_t p,q,tmp
else: mpz_clear(p) mpz_clear(q) mpz_clear(tmp) raise ValueError("the type must be one of 'floor', 'hj'")
def continued_fraction(self): r""" Return the continued fraction of that rational.
EXAMPLES::
sage: (641/472).continued_fraction() [1; 2, 1, 3, 1, 4, 1, 5]
sage: a = (355/113).continued_fraction(); a [3; 7, 16] sage: a.n(digits=10) 3.141592920 sage: pi.n(digits=10) 3.141592654
It's almost pi! """ #TODO: do better
def __richcmp__(left, right, int op): """ Compare two rational numbers.
INPUT:
- ``left, right`` -- objects
- ``op`` -- integer
EXAMPLES::
sage: 1/3 < 2/3 True sage: 2/3 < 1/3 False sage: 4/5 < 2.0 True sage: 4/5 < 0.8 False
sage: ones = [1, 1r, 1l, 1/1, 1.0r, 1.0] sage: twos = [2, 2r, 2l, 2/1, 2.0r, 2.0] sage: threes = [3, 3r, 3l, 3/1, 3.0r, 3.0] sage: from itertools import product sage: for one,two,three in product(ones,twos,threes): ....: assert one < two < three ....: assert one <= two <= three ....: assert three > two > one ....: assert three >= two >= one ....: assert one != two and one != three and two != three sage: for one1, one2 in product(ones,repeat=2): ....: assert (one1 == one2) is True ....: assert (one1 <= one2) is True ....: assert (one1 >= one2) is True """ cdef int c cdef mpz_t mpz_tmp
else: else:
cpdef int _cmp_(left, right) except -2: r""" TESTS::
sage: (2/3)._cmp_(3/4) -1 sage: (1/2)._cmp_(1/2) 0 """ cdef int c
def __copy__(self): """ Return a copy of ``self``.
OUTPUT: Rational
EXAMPLES::
sage: a = -17/37 sage: copy(a) is a False
Coercion does not make a new copy::
sage: QQ(a) is a True
The constructor also makes a new copy::
sage: Rational(a) is a False """ cdef Rational z
def __dealloc__(self): """ Free memory occupied by this rational number.
EXAMPLES::
sage: a = -17/37 sage: del a # indirect test """
def __repr__(self): """ Return string representation of this rational number.
EXAMPLES::
sage: a = -17/37; a.__repr__() '-17/37' """
def _latex_(self): """ Return Latex representation of this rational number.
EXAMPLES::
sage: a = -17/37 sage: a._latex_() '-\\frac{17}{37}' """ else: else:
def _sympy_(self): """ Convert Sage ``Rational`` to SymPy ``Rational``.
EXAMPLES::
sage: n = 1/2; n._sympy_() 1/2 sage: n = -1/5; n._sympy_() -1/5 sage: from sympy import Symbol sage: QQ(1)+Symbol('x')*QQ(2) 2*x + 1 """
def __mpz__(self): """ Return a gmpy2 ``mpz`` if this Rational is an integer.
EXAMPLES::
sage: q = 6/2 sage: q.__mpz__() # optional - gmpy2 mpz(3) sage: q = 1/4 sage: q.__mpz__() # optional - gmpy2 Traceback (most recent call last): ... TypeError: rational is not an integer
TESTS::
sage: QQ().__mpz__(); raise NotImplementedError("gmpy2 is not installed") Traceback (most recent call last): ... NotImplementedError: gmpy2 is not installed """ raise TypeError("rational is not an integer")
def __mpq__(self): """ Convert Sage ``Rational`` to gmpy2 ``Rational``.
EXAMPLES::
sage: r = 5/3 sage: r.__mpq__() # optional - gmpy2 mpq(5,3) sage: from gmpy2 import mpq # optional - gmpy2 sage: mpq(r) # optional - gmpy2 mpq(5,3)
TESTS::
sage: r.__mpq__(); raise NotImplementedError("gmpy2 is not installed") Traceback (most recent call last): ... NotImplementedError: gmpy2 is not installed """ IF HAVE_GMPY2: return gmpy2.GMPy_MPQ_From_mpq(self.value) ELSE:
def _magma_init_(self, magma): """ Return the magma representation of ``self``.
EXAMPLES::
sage: n = -485/82847 sage: n._magma_init_(magma) # optional - magma '-485/82847' """
@property def __array_interface__(self): """ Used for NumPy conversion. If ``self`` is integral, it converts to an ``Integer``. Otherwise it converts to a double floating point value.
EXAMPLES::
sage: import numpy sage: numpy.array([1, 2, 3/1]) array([1, 2, 3])
sage: numpy.array(QQ(2**40)).dtype dtype('int64') sage: numpy.array(QQ(2**400)).dtype dtype('O')
sage: numpy.array([1, 1/2, 3/4]) array([ 1. , 0.5 , 0.75]) """ return numpy_int64_interface else: else:
def _mathml_(self): """ Return mathml representation of this rational number.
EXAMPLES::
sage: a = -17/37; a._mathml_() '<mo>-</mo><mfrac><mrow><mn>17</mn></mrow><mrow><mn>37</mn></mrow></mfrac>' """ return '<mn>%s</mn>'%(self.numer()) else:
def _im_gens_(self, codomain, im_gens): """ Return the image of ``self`` under the homomorphism from the rational field to ``codomain``.
This always just returns ``self`` coerced into the ``codomain``.
INPUT:
- ``codomain`` -- object (usually a ring)
- ``im_gens`` -- list of elements of ``codomain``
EXAMPLES::
sage: a = -17/37 sage: a._im_gens_(QQ, [1/1]) -17/37 """
def content(self, other): """ Return the content of ``self`` and ``other``, i.e. the unique positive rational number `c` such that ``self/c`` and ``other/c`` are coprime integers.
``other`` can be a rational number or a list of rational numbers.
EXAMPLES::
sage: a = 2/3 sage: a.content(2/3) 2/3 sage: a.content(1/5) 1/15 sage: a.content([2/5, 4/9]) 2/45 """
def valuation(self, p): r""" Return the power of ``p`` in the factorization of self.
INPUT:
- ``p`` - a prime number
OUTPUT:
(integer or infinity) ``Infinity`` if ``self`` is zero, otherwise the (positive or negative) integer `e` such that ``self`` = `m*p^e` with `m` coprime to `p`.
.. NOTE::
See also :meth:`val_unit()` which returns the pair `(e,m)`. The function :meth:`ord()` is an alias for :meth:`valuation()`.
EXAMPLES::
sage: x = -5/9 sage: x.valuation(5) 1 sage: x.ord(5) 1 sage: x.valuation(3) -2 sage: x.valuation(2) 0
Some edge cases::
sage: (0/1).valuation(4) +Infinity sage: (7/16).valuation(4) -2 """
ord = valuation
def local_height(self, p, prec=None): r""" Returns the local height of this rational number at the prime `p`.
INPUT:
- ``p`` -- a prime number
- ``prec`` (int) -- desired floating point precision (default: default RealField precision).
OUTPUT:
(real) The local height of this rational number at the prime `p`.
EXAMPLES::
sage: a = QQ(25/6) sage: a.local_height(2) 0.693147180559945 sage: a.local_height(3) 1.09861228866811 sage: a.local_height(5) 0.000000000000000 """ else: return R.zero()
def local_height_arch(self, prec=None): r""" Returns the Archimedean local height of this rational number at the infinite place.
INPUT:
- ``prec`` (int) -- desired floating point precision (default: default RealField precision).
OUTPUT:
(real) The local height of this rational number `x` at the unique infinite place of `\QQ`, which is `\max(\log(|x|),0)`.
EXAMPLES::
sage: a = QQ(6/25) sage: a.local_height_arch() 0.000000000000000 sage: (1/a).local_height_arch() 1.42711635564015 sage: (1/a).local_height_arch(100) 1.4271163556401457483890413081 """ else:
def global_height_non_arch(self, prec=None): r""" Returns the total non-archimedean component of the height of this rational number.
INPUT:
- ``prec`` (int) -- desired floating point precision (default: default RealField precision).
OUTPUT:
(real) The total non-archimedean component of the height of this rational number.
ALGORITHM:
This is the sum of the local heights at all primes `p`, which may be computed without factorization as the log of the denominator.
EXAMPLES::
sage: a = QQ(5/6) sage: a.support() [2, 3, 5] sage: a.global_height_non_arch() 1.79175946922805 sage: [a.local_height(p) for p in a.support()] [0.693147180559945, 1.09861228866811, 0.000000000000000] sage: sum([a.local_height(p) for p in a.support()]) 1.79175946922805 """ else: R = RealField(prec) return R.zero()
def global_height_arch(self, prec=None): r""" Returns the total archimedean component of the height of this rational number.
INPUT:
- ``prec`` (int) -- desired floating point precision (default: default RealField precision).
OUTPUT:
(real) The total archimedean component of the height of this rational number.
ALGORITHM:
Since `\QQ` has only one infinite place this is just the value of the local height at that place. This separate function is included for compatibility with number fields.
EXAMPLES::
sage: a = QQ(6/25) sage: a.global_height_arch() 0.000000000000000 sage: (1/a).global_height_arch() 1.42711635564015 sage: (1/a).global_height_arch(100) 1.4271163556401457483890413081 """
def global_height(self, prec=None): r""" Returns the absolute logarithmic height of this rational number.
INPUT:
- ``prec`` (int) -- desired floating point precision (default: default RealField precision).
OUTPUT:
(real) The absolute logarithmic height of this rational number.
ALGORITHM:
The height is the sum of the total archimedean and non-archimedean components, which is equal to `\max(\log(n),\log(d))` where `n,d` are the numerator and denominator of the rational number.
EXAMPLES::
sage: a = QQ(6/25) sage: a.global_height_arch() + a.global_height_non_arch() 3.21887582486820 sage: a.global_height() 3.21887582486820 sage: (1/a).global_height() 3.21887582486820 sage: QQ(0).global_height() 0.000000000000000 sage: QQ(1).global_height() 0.000000000000000 """ else: R = RealField(prec)
def is_square(self): """ Return whether or not this rational number is a square.
OUTPUT: bool
EXAMPLES::
sage: x = 9/4 sage: x.is_square() True sage: x = (7/53)^100 sage: x.is_square() True sage: x = 4/3 sage: x.is_square() False sage: x = -1/4 sage: x.is_square() False """
def is_norm(self, L, element=False, proof=True): r""" Determine whether ``self`` is the norm of an element of ``L``.
INPUT:
- ``L`` -- a number field - ``element`` -- (default: ``False``) boolean whether to also output an element of which ``self`` is a norm - proof -- If ``True``, then the output is correct unconditionally. If ``False``, then the output assumes GRH.
OUTPUT:
If element is ``False``, then the output is a boolean ``B``, which is ``True`` if and only if ``self`` is the norm of an element of ``L``. If ``element`` is ``False``, then the output is a pair ``(B, x)``, where ``B`` is as above. If ``B`` is ``True``, then ``x`` an element of ``L`` such that ``self == x.norm()``. Otherwise, ``x is None``.
ALGORITHM:
Uses PARI's bnfisnorm. See ``_bnfisnorm()``.
EXAMPLES::
sage: K = NumberField(x^2 - 2, 'beta') sage: (1/7).is_norm(K) True sage: (1/10).is_norm(K) False sage: 0.is_norm(K) True sage: (1/7).is_norm(K, element=True) (True, 1/7*beta + 3/7) sage: (1/10).is_norm(K, element=True) (False, None) sage: (1/691).is_norm(QQ, element=True) (True, 1/691)
The number field doesn't have to be defined by an integral polynomial::
sage: B, e = (1/5).is_norm(QuadraticField(5/4, 'a'), element=True) sage: B True sage: e.norm() 1/5
A non-Galois number field::
sage: K.<a> = NumberField(x^3-2) sage: B, e = (3/5).is_norm(K, element=True); B True sage: e.norm() 3/5
sage: 7.is_norm(K) Traceback (most recent call last): ... NotImplementedError: is_norm is not implemented unconditionally for norms from non-Galois number fields sage: 7.is_norm(K, proof=False) False
AUTHORS:
- Craig Citro (2008-04-05)
- Marco Streng (2010-12-03) """
raise ValueError("L (=%s) must be a NumberField in is_norm" % L) assert a.norm() == self return True, a
def _bnfisnorm(self, K, proof=True, extra_primes=0): r""" This gives the output of the PARI function :pari:`bnfisnorm`.
Tries to tell whether the rational number ``self`` is the norm of some element `y` in ``K``. Returns a pair `(a, b)` where ``self = Norm(a)*b``. Looks for a solution that is an `S`-unit, with `S` a certain set of prime ideals containing (among others) all primes dividing ``self``.
If `K` is known to be Galois, set ``extra_primes = 0`` (in this case, ``self`` is a norm iff `b = 1`).
If ``extra_primes`` is non-zero, the program adds to `S` the following prime ideals, depending on the sign of extra_primes. If ``extra_primes > 0``, the ideals of norm less than ``extra_primes``. And if ``extra_primes < 0``, the ideals dividing ``extra_primes``.
Assuming GRH, the answer is guaranteed (i.e., ``self`` is a norm iff `b = 1`), if `S` contains all primes less than `12\log(\disc(L))^2`, where `L` is the Galois closure of `K`.
INPUT:
- ``K`` -- a number field - ``proof`` -- whether to certify the output of bnfinit. If ``False``, then correctness of the output depends on GRH. - ``extra_primes`` -- an integer as explained above
OUTPUT:
A pair `(a, b)` with `a` in `K` and `b` in `\QQ` such that ``self == Norm(a)*b`` as explained above.
ALGORITHM:
Uses PARI's bnfisnorm.
EXAMPLES::
sage: QQ(2)._bnfisnorm(QuadraticField(-1, 'i')) (i + 1, 1) sage: 7._bnfisnorm(NumberField(x^3-2, 'b')) (1, 7)
AUTHORS:
- Craig Citro (2008-04-05)
- Marco Streng (2010-12-03) """ raise ValueError("K must be a NumberField in bnfisnorm")
def is_perfect_power(self, expected_value=False): r""" Returns ``True`` if ``self`` is a perfect power.
INPUT:
- ``expected_value`` - (bool) whether or not this rational is expected be a perfect power. This does not affect the correctness of the output, only the runtime.
If ``expected_value`` is ``False`` (default) it will check the smallest of the numerator and denominator is a perfect power as a first step, which is often faster than checking if the quotient is a perfect power.
EXAMPLES::
sage: (4/9).is_perfect_power() True sage: (144/1).is_perfect_power() True sage: (4/3).is_perfect_power() False sage: (2/27).is_perfect_power() False sage: (4/27).is_perfect_power() False sage: (-1/25).is_perfect_power() False sage: (-1/27).is_perfect_power() True sage: (0/1).is_perfect_power() True
The second parameter does not change the result, but may change the runtime.
::
sage: (-1/27).is_perfect_power(True) True sage: (-1/25).is_perfect_power(True) False sage: (2/27).is_perfect_power(True) False sage: (144/1).is_perfect_power(True) True
This test makes sure we workaround a bug in GMP (see :trac:`4612`)::
sage: [ -a for a in srange(100) if not QQ(-a^3).is_perfect_power() ] [] sage: [ -a for a in srange(100) if not QQ(-a^3).is_perfect_power(True) ] [] """ cdef int s
return mpz_perfect_power_p(mpq_denref(self.value))
cdef mpz_t prod cdef bint res
# We should be able to run the code in the sign == 1 case # below for both cases. However, we need to do extra work to # avoid a bug in GMP's mpz_perfect_power_p; see trac #4612 for # more details. # # The code in the case of sign == -1 could definitely be # cleaned up, but it will be removed shortly, since both GMP # and eMPIRe have fixes for the mpz_perfect_power_p bug.
# A necessary condition is that both the numerator and denominator # be perfect powers, which can be faster to disprove than the full # product (especially if both have a large prime factor). else:
else: # self is negative
while mpz_perfect_square_p(prod): mpz_sqrt(prod, prod) if not mpz_perfect_power_p(prod): mpz_clear(prod) return False else: if not mpz_perfect_power_p(mpq_denref(self.value)): return False mpz_init(prod) else:
def squarefree_part(self): """ Return the square free part of `x`, i.e., an integer z such that `x = z y^2`, for a perfect square `y^2`.
EXAMPLES::
sage: a = 1/2 sage: a.squarefree_part() 2 sage: b = a/a.squarefree_part() sage: b, b.is_square() (1/4, True) sage: a = 24/5 sage: a.squarefree_part() 30 """
def is_padic_square(self, p): """ Determines whether this rational number is a square in `\QQ_p` (or in `R` when ``p = infinity``).
INPUT:
- ``p`` - a prime number, or ``infinity``
EXAMPLES::
sage: QQ(2).is_padic_square(7) True sage: QQ(98).is_padic_square(7) True sage: QQ(2).is_padic_square(5) False
TESTS::
sage: QQ(5/7).is_padic_square(int(2)) False """ ## Special case when self is zero return True
## Deal with p = infinity (i.e. the real numbers) return (self > 0)
## Check that p is prime raise ValueError('p must be "infinity" or a positive prime number.')
## Deal with finite primes
def val_unit(self, p): r""" Returns a pair: the `p`-adic valuation of ``self``, and the `p`-adic unit of ``self``, as a :class:`Rational`.
We do not require the `p` be prime, but it must be at least 2. For more documentation see :meth:`Integer.val_unit()`.
INPUT:
- ``p`` - a prime
OUTPUT:
- ``int`` - the `p`-adic valuation of this rational
- ``Rational`` - `p`-adic unit part of ``self``
EXAMPLES::
sage: (-4/17).val_unit(2) (2, -1/17) sage: (-4/17).val_unit(17) (-1, -4) sage: (0/1).val_unit(17) (+Infinity, 1)
AUTHORS:
- David Roe (2007-04-12) """
# TODO -- change to use cpdef? If so, must fix # code in padics, etc. Do search_src('_val_unit'). cdef _val_unit(Rational self, integer.Integer p): """ This is called by :meth:`val_unit()`.
EXAMPLES::
sage: (-4/17).val_unit(2) # indirect doctest (2, -1/17) """ cdef Rational u raise ValueError("p must be at least 2.") else:
def prime_to_S_part(self, S=[]): r""" Returns ``self`` with all powers of all primes in ``S`` removed.
INPUT:
- ``S`` - list or tuple of primes.
OUTPUT: rational
.. NOTE::
Primality of the entries in `S` is not checked.
EXAMPLES::
sage: QQ(3/4).prime_to_S_part() 3/4 sage: QQ(3/4).prime_to_S_part([2]) 3 sage: QQ(-3/4).prime_to_S_part([3]) -1/4 sage: QQ(700/99).prime_to_S_part([2,3,5]) 7/11 sage: QQ(-700/99).prime_to_S_part([2,3,5]) -7/11 sage: QQ(0).prime_to_S_part([2,3,5]) 0 sage: QQ(-700/99).prime_to_S_part([]) -700/99
"""
def sqrt(self, prec=None, extend=True, all=False): r""" 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.
- ``all`` -- bool (default: ``False``); if ``True``, return all square roots of self, instead of just one.
EXAMPLES::
sage: x = 25/9 sage: x.sqrt() 5/3 sage: sqrt(x) 5/3 sage: x = 64/4 sage: x.sqrt() 4 sage: x = 100/1 sage: x.sqrt() 10 sage: x.sqrt(all=True) [10, -10] sage: x = 81/5 sage: x.sqrt() 9*sqrt(1/5) sage: x = -81/3 sage: x.sqrt() 3*sqrt(-3)
::
sage: n = 2/3 sage: n.sqrt() sqrt(2/3) sage: n.sqrt(prec=10) 0.82 sage: n.sqrt(prec=100) 0.81649658092772603273242802490 sage: n.sqrt(prec=100)^2 0.66666666666666666666666666667 sage: n.sqrt(prec=53, all=True) [0.816496580927726, -0.816496580927726] sage: n.sqrt(extend=False, all=True) Traceback (most recent call last): ... ValueError: square root of 2/3 not a rational number sage: sqrt(-2/3, all=True) [sqrt(-2/3), -sqrt(-2/3)] sage: sqrt(-2/3, prec=53) 0.816496580927726*I sage: sqrt(-2/3, prec=53, all=True) [0.816496580927726*I, -0.816496580927726*I]
AUTHORS:
- Naqi Jaffery (2006-03-05): some examples """
raise ValueError("square root of negative number not rational")
cdef mpz_t tmp
else:
def period(self): r""" Return the period of the repeating part of the decimal expansion of this rational number.
ALGORITHM:
When a rational number `n/d` with `(n,d)=1` is expanded, the period begins after `s` terms and has length `t`, where `s` and `t` are the smallest numbers satisfying `10^s=10^{s+t} \mod d`. In general if `d=2^a 5^b m` where `m` is coprime to 10, then `s=\max(a,b)` and `t` is the order of 10 modulo `d`.
EXAMPLES::
sage: (1/7).period() 6 sage: RR(1/7) 0.142857142857143 sage: (1/8).period() 1 sage: RR(1/8) 0.125000000000000 sage: RR(1/6) 0.166666666666667 sage: (1/6).period() 1 sage: x = 333/106 sage: x.period() 13 sage: RealField(200)(x) 3.1415094339622641509433962264150943396226415094339622641509 """ cdef unsigned int alpha, beta
def nth_root(self, int n): r""" Computes the `n`-th root of ``self``, or raises a ``ValueError`` if ``self`` is not a perfect `n`-th power.
INPUT:
- ``n`` - integer (must fit in C int type)
AUTHORS:
- David Harvey (2006-09-15)
EXAMPLES::
sage: (25/4).nth_root(2) 5/2 sage: (125/8).nth_root(3) 5/2 sage: (-125/8).nth_root(3) -5/2 sage: (25/4).nth_root(-2) 2/5
::
sage: (9/2).nth_root(2) Traceback (most recent call last): ... ValueError: not a perfect 2nd power
::
sage: (-25/4).nth_root(2) Traceback (most recent call last): ... ValueError: cannot take even root of negative number """ # TODO -- this could be quicker, by using GMP directly. cdef integer.Integer num cdef integer.Integer den cdef int negative
else: raise ValueError("n cannot be zero")
raise ValueError("not a perfect %s power" % ZZ(n).ordinal_str())
else:
def is_nth_power(self, int n): r""" Returns ``True`` if self is an `n`-th power, else ``False``.
INPUT:
- ``n`` - integer (must fit in C int type)
.. NOTE::
Use this function when you need to test if a rational number is an `n`-th power, but do not need to know the value of its `n`-th root. If the value is needed, use :meth:`nth_root()`.
AUTHORS:
- John Cremona (2009-04-04)
EXAMPLES::
sage: QQ(25/4).is_nth_power(2) True sage: QQ(125/8).is_nth_power(3) True sage: QQ(-125/8).is_nth_power(3) True sage: QQ(25/4).is_nth_power(-2) True
sage: QQ(9/2).is_nth_power(2) False sage: QQ(-25).is_nth_power(2) False
""" raise ValueError("n cannot be zero")
def str(self, int base=10): """ Return a string representation of ``self`` in the given ``base``.
INPUT:
- ``base`` -- integer (default: 10); base must be between 2 and 36.
OUTPUT: string
EXAMPLES::
sage: (-4/17).str() '-4/17' sage: (-4/17).str(2) '-100/10001'
Note that the base must be at most 36.
::
sage: (-4/17).str(40) Traceback (most recent call last): ... ValueError: base (=40) must be between 2 and 36 sage: (-4/17).str(1) Traceback (most recent call last): ... ValueError: base (=1) must be between 2 and 36 """ cdef size_t n cdef char *s
n = mpz_sizeinbase (mpq_numref(self.value), base) \ raise MemoryError("Unable to allocate enough memory for the string representation of an integer.")
def __float__(self): """ Return floating point approximation to ``self`` as a Python float.
OUTPUT: float
EXAMPLES::
sage: (-4/17).__float__() -0.23529411764705882 sage: float(-4/17) -0.23529411764705882 sage: float(1/3) 0.3333333333333333 sage: float(1/10) 0.1 sage: n = QQ(902834098234908209348209834092834098); float(n) 9.028340982349083e+35
TESTS:
Test that conversion agrees with `RR`::
sage: Q = [a/b for a in [-99..99] for b in [1..99]] sage: all([RDF(q) == RR(q) for q in Q]) True
Test that the conversion has correct rounding on simple rationals::
sage: for p in [-100..100]: ....: for q in [1..100]: ....: r = RDF(p/q) ....: assert (RR(r).exact_rational() - p/q) <= r.ulp()/2
Test larger rationals::
sage: Q = continued_fraction(pi).convergents()[:100] sage: all([RDF(q) == RR(q) for q in Q]) True
At some point, the continued fraction and direct conversion to ``RDF`` should agree::
sage: RDFpi = RDF(pi) sage: all([RDF(q) == RDFpi for q in Q[20:]]) True """
def __hash__(self): """ Return hash of ``self``.
OUTPUT: integer
EXAMPLES::
sage: QQ(42).__hash__() 42 sage: QQ(1/42).__hash__() 1488680910 # 32-bit -7658195599476688946 # 64-bit sage: n = ZZ.random_element(10^100) sage: hash(n) == hash(QQ(n)) or n True sage: hash(-n) == hash(-QQ(n)) or n True sage: hash(-4/17) -47583156 # 32-bit 8709371129873690700 # 64-bit """ # The constant below is (1 + sqrt(5)) << 61
def __getitem__(self, int n): """ Return ``n``-th element of ``self``, viewed as a list. This is for consistency with how number field elements work.
INPUT:
- ``n`` - an integer (error if not 0 or -1)
OUTPUT: Rational
EXAMPLES::
sage: (-4/17)[0] -4/17 sage: (-4/17)[1] Traceback (most recent call last): ... IndexError: index n (=1) out of range; it must be 0 sage: (-4/17)[-1] # indexing from the right -4/17 """
################################################################ # Optimized arithmetic ################################################################ def __add__(left, right): """ Return ``left`` plus ``right``
EXAMPLES::
sage: (2/3) + (1/6) 5/6 sage: (1/3) + (1/2) 5/6 sage: (1/3) + 2 7/3 """ cdef Rational x
cpdef _add_(self, right): """ Return ``right`` plus ``self``.
EXAMPLES::
sage: (2/3)._add_(1/6) 5/6 sage: (1/3)._add_(1/2) 5/6 """ cdef Rational x
def __sub__(left, right): """ Return ``left`` minus ``right``
EXAMPLES::
sage: 11/3 - 5/4 29/12
sage: (2/3) - 2 -4/3 sage: (-2/3) - 1 -5/3 sage: (2/3) - (-3) 11/3 sage: (-2/3) - (-3) 7/3 sage: 2/3 - polygen(QQ) -x + 2/3 """ cdef Rational x (<Integer>right).value) mpq_numref(x.value))
cpdef _sub_(self, right): """ Return ``self`` minus ``right``.
EXAMPLES::
sage: (2/3)._sub_(1/6) 1/2 """ cdef Rational x
cpdef _neg_(self): """ Negate ``self``.
EXAMPLES::
sage: -(2/3) # indirect doctest -2/3 """ cdef Rational x x = <Rational> Rational.__new__(Rational) mpq_neg(x.value, self.value) return x
def __mul__(left, right): """ Return ``left`` times ``right``.
EXAMPLES::
sage: (3/14) * 2/3 1/7 sage: (3/14) * 10 15/7 sage: 3/14 * polygen(QQ) 3/14*x """ cdef Rational x
cpdef _mul_(self, right): """ Return ``self`` times ``right``.
EXAMPLES::
sage: (3/14)._mul_(2/3) 1/7 """ cdef Rational x # We only use the signal handler (to enable ctrl-c out) in case # self is huge, so the product might actually take a while to compute. sig_on() mpq_mul(x.value, self.value, (<Rational>right).value) sig_off() else:
def __div__(left, right): """ Return ``left`` divided by ``right``
EXAMPLES::
sage: QQ((2,3)) / QQ((-5,4)) -8/15 sage: QQ((22,3)) / 4 11/6 sage: QQ((-2,3)) / (-4) 1/6 sage: QQ((2,3)) / QQ.zero() Traceback (most recent call last): ... ZeroDivisionError: rational division by zero """ cdef Rational x raise ZeroDivisionError('rational division by zero') mpq_denref((<Rational>left).value))
cpdef _div_(self, right): """ Return ``self`` divided by ``right``.
EXAMPLES::
sage: 2/3 # indirect doctest 2/3 sage: 3/0 # indirect doctest Traceback (most recent call last): ... ZeroDivisionError: rational division by zero """ cdef Rational x
################################################################ # Other arithmetic operations. ################################################################
def __invert__(self): """ Return the multiplicative inverse of ``self``.
OUTPUT: Rational
EXAMPLES::
sage: (-4/17).__invert__() -17/4 sage: ~(-4/17) -17/4 """ cdef Rational x
def __pow__(self, n, dummy): """ Raise ``self`` to the integer power ``n``.
EXAMPLES::
sage: (2/3)^5 32/243 sage: (-1/1)^(1/3) (-1)^(1/3)
We raise to some interesting powers::
sage: (2/3)^I (2/3)^I sage: (2/3)^sqrt(2) (2/3)^sqrt(2) sage: x,y,z,n = var('x,y,z,n') sage: (2/3)^(x^n + y^n + z^n) (2/3)^(x^n + y^n + z^n) sage: (-7/11)^(tan(x)+exp(x)) (-7/11)^(e^x + tan(x)) sage: (2/3)^(3/4) (2/3)^(3/4) sage: (-1/3)^0 1 sage: a = (0/1)^(0/1); a 1 sage: type(a) <type 'sage.rings.rational.Rational'>
The exponent must fit in a long unless the base is -1, 0, or 1.
::
sage: s = (1/2)^(2^100) Traceback (most recent call last): ... RuntimeError: exponent must be at most 2147483647 # 32-bit RuntimeError: exponent must be at most 9223372036854775807 # 64-bit sage: s = (1/2)^(-2^100) Traceback (most recent call last): ... RuntimeError: exponent must be at most 2147483647 # 32-bit RuntimeError: exponent must be at most 9223372036854775807 # 64-bit sage: (-3/3)^(2^100) 1
This works even if the base is a float or Python complex or other type::
sage: float(1.2)**(1/2) 1.0954451150103321 sage: complex(1,2)**(1/2) (1.272019649514069+0.786151377757423...j) sage: int(2)^(1/2) sqrt(2) sage: a = int(2)^(3/1); a 8 sage: type(a) <type 'sage.rings.rational.Rational'>
If the result is rational, it is returned as a rational::
sage: (4/9)^(1/2) 2/3 sage: parent((4/9)^(1/2)) Rational Field sage: (-27/125)^(1/3) 3/5*(-1)^(1/3) sage: (-27/125)^(1/2) 3/5*sqrt(-3/5)
The result is normalized to have the rational power in the numerator::
sage: 2^(-1/2) 1/2*sqrt(2) sage: 8^(-1/5) 1/8*8^(4/5) sage: 3^(-3/2) 1/9*sqrt(3)
TESTS::
sage: QQ(0)^(-1) Traceback (most recent call last): ... ZeroDivisionError: rational division by zero """ raise ValueError("__pow__ dummy variable not used")
# If the base is not a rational, e.g., it is an int, complex, float, user-defined type, etc. # dangerous coercion -- don't use -- try symbolic result
cdef long nn
# Perhaps it can be done exactly # It was an exact power # Can't simplify the power, return a symbolic expression. # We use the hold=True keyword argument to prevent the # symbolics library from trying to simplify this expression # again. This would lead to infinite loops otherwise. else:
except Exception: raise TypeError("exponent (=%s) must be an integer.\nCoerce your numbers to real or complex numbers first." % n)
return self return self
# mpz_pow_ui(mpq_denref(x.value), mpq_numref(_self.value), <unsigned long int>(-nn)) # mpz_pow_ui(mpq_numref(x.value), mpq_denref(_self.value), <unsigned long int>(-nn)) # The above causes segfaults, so swap after instead... # mpz_swap(mpq_numref(x.value), mpq_denref(x.value)) # still a segfault
if n < 0: # this doesn't make sense unless n is an integer. x = _self**(-n) return ~x
cdef mpz_t num, den
sig_on() mpz_init(num) mpz_init(den) mpz_pow_ui(num, mpq_numref(_self.value), nn) mpz_pow_ui(den, mpq_denref(_self.value), nn) mpq_set_num(x.value, num) mpq_set_den(x.value, den) mpz_clear(num) mpz_clear(den) sig_off()
return x
def __pos__(self): """ Return ``self``.
OUTPUT: Rational
EXAMPLES::
sage: (-4/17).__pos__() -4/17 sage: +(-4/17) -4/17 """
def __neg__(self): """ Return the negative of ``self``.
OUTPUT: Rational
EXAMPLES::
sage: (-4/17).__neg__() 4/17 sage: - (-4/17) 4/17 """ cdef Rational x
def __nonzero__(self): """ Return ``True`` if this rational number is nonzero.
OUTPUT: bool
EXAMPLES::
sage: bool(0/5) False sage: bool(-4/17) True """ # A rational number is zero iff its numerator is zero.
def __abs__(self): """ Return the absolute value of this rational number.
OUTPUT: Rational
EXAMPLES::
sage: (-4/17).__abs__() 4/17 sage: abs(-4/17) 4/17 """ cdef Rational x
def sign(self): """ Returns the sign of this rational number, which is -1, 0, or 1 depending on whether this number is negative, zero, or positive respectively.
OUTPUT: Integer
EXAMPLES::
sage: (2/3).sign() 1 sage: (0/3).sign() 0 sage: (-1/6).sign() -1 """
def mod_ui(Rational self, unsigned long int n): """ Return the remainder upon division of ``self`` by the unsigned long integer ``n``.
INPUT:
- ``n`` - an unsigned long integer
OUTPUT: integer
EXAMPLES::
sage: (-4/17).mod_ui(3) 1 sage: (-4/17).mod_ui(17) Traceback (most recent call last): ... ArithmeticError: The inverse of 0 modulo 17 is not defined. """ cdef unsigned int num, den, a
# Documentation from GMP manual: # "For the ui variants the return value is the remainder, and # in fact returning the remainder is all the div_ui functions do."
def __mod__(x, y): """ Return the remainder of division of ``x`` by ``y``, where ``y`` is something that can be coerced to an integer.
INPUT:
- ``other`` - object that coerces to an integer.
OUTPUT: integer
EXAMPLES::
sage: (-4/17).__mod__(3/1) 1
TESTS:
Check that :trac:`14870` is fixed::
sage: int(4) % QQ(3) 1 """ cdef Rational rat else: raise ZeroDivisionError("Rational modulo by zero")
def norm(self): r""" Returns the norm from `\QQ` to `\QQ` of `x` (which is just `x`). This was added for compatibility with :class:`NumberFields`.
OUTPUT:
- ``Rational`` - reference to ``self``
EXAMPLES::
sage: (1/3).norm() 1/3
AUTHORS:
- Craig Citro """
def relative_norm(self): """ Returns the norm from Q to Q of x (which is just x). This was added for compatibility with NumberFields
EXAMPLES::
sage: (6/5).relative_norm() 6/5
sage: QQ(7/5).relative_norm() 7/5 """
def absolute_norm(self): """ Returns the norm from Q to Q of x (which is just x). This was added for compatibility with NumberFields
EXAMPLES::
sage: (6/5).absolute_norm() 6/5
sage: QQ(7/5).absolute_norm() 7/5 """
def trace(self): r""" Returns the trace from `\QQ` to `\QQ` of `x` (which is just `x`). This was added for compatibility with :class:`NumberFields`.
OUTPUT:
- ``Rational`` - reference to self
EXAMPLES::
sage: (1/3).trace() 1/3
AUTHORS:
- Craig Citro """
def charpoly(self, var='x'): """ Return the characteristic polynomial of this rational number. This will always be just ``var - self``; this is really here so that code written for number fields won't crash when applied to rational numbers.
INPUT:
- ``var`` - a string
OUTPUT: Polynomial
EXAMPLES::
sage: (1/3).charpoly('x') x - 1/3
The default is var='x'. (:trac:`20967`)::
sage: a = QQ(2); a.charpoly('x') x - 2
AUTHORS:
- Craig Citro """
def minpoly(self, var='x'): """ Return the minimal polynomial of this rational number. This will always be just ``x - self``; this is really here so that code written for number fields won't crash when applied to rational numbers.
INPUT:
- ``var`` - a string
OUTPUT: Polynomial
EXAMPLES::
sage: (1/3).minpoly() x - 1/3 sage: (1/3).minpoly('y') y - 1/3
AUTHORS:
- Craig Citro """
def _integer_(self, Z=None): """ Return ``self`` coerced to an integer. Of course this rational number must have a denominator of 1.
OUTPUT: Integer
EXAMPLES::
sage: (-4/17)._integer_() Traceback (most recent call last): ... TypeError: no conversion of this rational to integer sage: (-4/1)._integer_() -4 """
def numerator(self): """ Return the numerator of this rational number. numer is an alias of numerator.
EXAMPLES::
sage: x = 5/11 sage: x.numerator() 5
sage: x = 9/3 sage: x.numerator() 3
sage: x = -5/11 sage: x.numer() -5 """
#Define an alias for numerator numer = numerator
IF PY_MAJOR_VERSION <= 2: def __int__(self): """ Convert this rational to a Python ``int``.
This truncates ``self`` if ``self`` has a denominator (which is consistent with Python's ``long(floats)``).
EXAMPLES::
sage: int(7/3) 2 sage: int(-7/3) -2 """
def __long__(self): """ Convert this rational to a Python ``long`` (``int`` on Python 3).
This truncates ``self`` if ``self`` has a denominator (which is consistent with Python's ``long(floats)``).
EXAMPLES::
sage: long(7/3) 2L sage: long(-7/3) -2L """ cdef mpz_t x else:
def denominator(self): """ Returns the denominator of this rational number. denom is an alias of denominator.
EXAMPLES::
sage: x = -5/11 sage: x.denominator() 11
sage: x = 9/3 sage: x.denominator() 1
sage: x = 5/13 sage: x.denom() 13 """
#Define an alias for denominator denom = denominator
def factor(self): """ Return the factorization of this rational number.
OUTPUT: Factorization
EXAMPLES::
sage: (-4/17).factor() -1 * 2^2 * 17^-1
Trying to factor 0 gives an arithmetic error::
sage: (0/1).factor() Traceback (most recent call last): ... ArithmeticError: factorization of 0 is not defined """
def support(self): """ Return a sorted list of the primes where this rational number has non-zero valuation.
OUTPUT: The set of primes appearing in the factorization of this rational with nonzero exponent, as a sorted list.
EXAMPLES::
sage: (-4/17).support() [2, 17]
Trying to find the support of 0 gives an arithmetic error::
sage: (0/1).support() Traceback (most recent call last): ... ArithmeticError: Support of 0 not defined. """
def log(self, m=None, prec=None): r""" Return the log of ``self``.
INPUT:
- ``m`` -- the base (default: natural log base e)
- ``prec`` -- integer (optional); the precision in bits
OUTPUT:
When ``prec`` is not given, the log as an element in symbolic ring unless the logarithm is exact. Otherwise the log is a :class:`RealField` approximation to ``prec`` bit precision.
EXAMPLES::
sage: (124/345).log(5) log(124/345)/log(5) sage: (124/345).log(5,100) -0.63578895682825611710391773754 sage: log(QQ(125)) 3*log(5) sage: log(QQ(125), 5) 3 sage: log(QQ(125), 3) 3*log(5)/log(3) sage: QQ(8).log(1/2) -3 sage: (1/8).log(1/2) 3 sage: (1/2).log(1/8) 1/3 sage: (1/2).log(8) -1/3 sage: (16/81).log(8/27) 4/3 sage: (8/27).log(16/81) 3/4 sage: log(27/8, 16/81) -3/4 sage: log(16/81, 27/8) -4/3 sage: (125/8).log(5/2) 3 sage: (125/8).log(5/2,prec=53) 3.00000000000000 """ from sage.symbolic.all import SR return SR(self).log() raise ValueError("log base must be positive") return RealField(prec)(self).log()
if de_ratio == ZZ.one(): return nu_ratio if lo_ratio == ZZ.one(): return -up_ratio
def gamma(self, prec=None): """ Return the gamma function evaluated at ``self``. This value is exact for integers and half-integers, and returns a symbolic value otherwise. For a numerical approximation, use keyword ``prec``.
EXAMPLES::
sage: gamma(1/2) sqrt(pi) sage: gamma(7/2) 15/8*sqrt(pi) sage: gamma(-3/2) 4/3*sqrt(pi) sage: gamma(6/1) 120 sage: gamma(1/3) gamma(1/3)
This function accepts an optional precision argument::
sage: (1/3).gamma(prec=100) 2.6789385347077476336556929410 sage: (1/2).gamma(prec=100) 1.7724538509055160272981674833 """ else: else:
def floor(self): """ Return the floor of this rational number as an integer.
OUTPUT: Integer
EXAMPLES::
sage: n = 5/3; n.floor() 1 sage: n = -17/19; n.floor() -1 sage: n = -7/2; n.floor() -4 sage: n = 7/2; n.floor() 3 sage: n = 10/2; n.floor() 5 """ cdef integer.Integer n
def ceil(self): """ Return the ceiling of this rational number.
OUTPUT: Integer
If this rational number is an integer, this returns this number, otherwise it returns the floor of this number +1.
EXAMPLES::
sage: n = 5/3; n.ceil() 2 sage: n = -17/19; n.ceil() 0 sage: n = -7/2; n.ceil() -3 sage: n = 7/2; n.ceil() 4 sage: n = 10/2; n.ceil() 5 """ cdef integer.Integer n
def trunc(self): """ Round this rational number to the nearest integer toward zero.
EXAMPLES::
sage: (5/3).trunc() 1 sage: (-5/3).trunc() -1 sage: QQ(42).trunc() 42 sage: QQ(-42).trunc() -42 """ cdef integer.Integer n
def round(Rational self, mode="away"): """ Returns the nearest integer to ``self``, rounding away from 0 by default, for consistency with the builtin Python round.
INPUT:
- ``self`` - a rational number
- ``mode`` - a rounding mode for half integers:
- 'toward' rounds toward zero - 'away' (default) rounds away from zero - 'up' rounds up - 'down' rounds down - 'even' rounds toward the even integer - 'odd' rounds toward the odd integer
OUTPUT: Integer
EXAMPLES::
sage: (9/2).round() 5 sage: n = 4/3; n.round() 1 sage: n = -17/4; n.round() -4 sage: n = -5/2; n.round() -3 sage: n.round("away") -3 sage: n.round("up") -2 sage: n.round("down") -3 sage: n.round("even") -2 sage: n.round("odd") -3 """ raise ValueError("rounding mode must be one of 'toward', 'away', 'up', 'down', 'even', or 'odd'") # round down: else: else: else:
def real(self): """ Returns the real part of ``self``, which is ``self``.
EXAMPLES::
sage: (1/2).real() 1/2 """
def imag(self): """ Returns the imaginary part of ``self``, which is zero.
EXAMPLES::
sage: (1/239).imag() 0 """
def height(self): """ The max absolute value of the numerator and denominator of ``self``, as an :class:`Integer`.
OUTPUT: Integer
EXAMPLES::
sage: a = 2/3 sage: a.height() 3 sage: a = 34/3 sage: a.height() 34 sage: a = -97/4 sage: a.height() 97
AUTHORS:
- Naqi Jaffery (2006-03-05): examples
.. NOTE::
For the logarithmic height, use :meth:`global_height()`.
"""
def _lcm(self, Rational other): """ Returns the least common multiple, in the rational numbers, of ``self`` and ``other``. This function returns either 0 or 1 (as a rational number).
INPUT:
- ``other`` - Rational
OUTPUT:
- ``Rational`` - 0 or 1
EXAMPLES::
sage: (2/3)._lcm(3/5) 1 sage: (0/1)._lcm(0/1) 0 sage: type((2/3)._lcm(3/5)) <type 'sage.rings.rational.Rational'> """
def additive_order(self): """ Return the additive order of ``self``.
OUTPUT: integer or infinity
EXAMPLES::
sage: QQ(0).additive_order() 1 sage: QQ(1).additive_order() +Infinity """ else:
def multiplicative_order(self): """ Return the multiplicative order of ``self``.
OUTPUT: Integer or ``infinity``
EXAMPLES::
sage: QQ(1).multiplicative_order() 1 sage: QQ('1/-1').multiplicative_order() 2 sage: QQ(0).multiplicative_order() +Infinity sage: QQ('2/3').multiplicative_order() +Infinity sage: QQ('1/2').multiplicative_order() +Infinity """ # if the numerator and the denominator are equal in absolute value, # then the rational number is -1 else:
def is_one(self): r""" Determine if a rational number is one.
OUTPUT: bool
EXAMPLES::
sage: QQ(1/2).is_one() False sage: QQ(4/4).is_one() True """ # A rational number is equal to 1 iff its numerator and denominator are equal
def is_integral(self): r""" Determine if a rational number is integral (i.e is in `\ZZ`).
OUTPUT: bool
EXAMPLES::
sage: QQ(1/2).is_integral() False sage: QQ(4/4).is_integral() True """
def is_rational(self): r""" Return ``True`` since this is a rational number.
EXAMPLES::
sage: (3/4).is_rational() True """
#Function alias for checking if the number is a integer.Added to solve ticket 15500 is_integer = is_integral
def is_S_integral(self, S=[]): r""" Determine if the rational number is ``S``-integral.
``x`` is ``S``-integral if ``x.valuation(p)>=0`` for all ``p`` not in ``S``, i.e., the denominator of ``x`` is divisible only by the primes in ``S``.
INPUT:
- ``S`` -- list or tuple of primes.
OUTPUT: bool
.. NOTE::
Primality of the entries in ``S`` is not checked.
EXAMPLES::
sage: QQ(1/2).is_S_integral() False sage: QQ(1/2).is_S_integral([2]) True sage: [a for a in range(1,11) if QQ(101/a).is_S_integral([2,5])] [1, 2, 4, 5, 8, 10] """
def is_S_unit(self, S=None): r""" Determine if the rational number is an ``S``-unit.
``x`` is an ``S``-unit if ``x.valuation(p)==0`` for all ``p`` not in ``S``, i.e., the numerator and denominator of ``x`` are divisible only by the primes in `S`.
INPUT:
- ``S`` -- list or tuple of primes.
OUTPUT: bool
.. NOTE::
Primality of the entries in ``S`` is not checked.
EXAMPLES::
sage: QQ(1/2).is_S_unit() False sage: QQ(1/2).is_S_unit([2]) True sage: [a for a in range(1,11) if QQ(10/a).is_S_unit([2,5])] [1, 2, 4, 5, 8, 10] """
cdef _lshift(self, long int exp): r""" Return ``self * 2^exp``. """ cdef Rational x mpq_div_2exp(x.value,self.value,-exp) else:
def __lshift__(x,y): """ Left shift operator ``x << y``.
INPUT:
- ``x, y`` -- integer or rational
OUTPUT: Rational
EXAMPLES::
sage: (2/3).__lshift__(4/1) 32/3 sage: (2/3).__lshift__(4/7) Traceback (most recent call last): ... ValueError: denominator must be 1 sage: (2).__lshift__(4/1) 32 sage: (2/3).__lshift__(4) 32/3 sage: (2/3) << (4/1) 32/3 """ return bin_op(x, y, operator.lshift)
cdef _rshift(self, long int exp): r""" Return ``self / 2^exp``. """ cdef Rational x else:
def __rshift__(x,y): """ Right shift operator ``x >> y``.
INPUT:
- ``x, y`` -- integer or rational
OUTPUT: Rational
EXAMPLES::
sage: (2/3).__rshift__(4/1) 1/24 sage: (2/3).__rshift__(4/7) Traceback (most recent call last): ... ValueError: denominator must be 1 sage: (2).__rshift__(4/1) 0 sage: (2/1).__rshift__(4) 1/8 sage: (2/1) >>(4/1) 1/8 """ return bin_op(x, y, operator.rshift)
def conjugate(self): """ Return the complex conjugate of this rational number, which is the number itself.
EXAMPLES::
sage: n = 23/11 sage: n.conjugate() 23/11 """
################################################## # Support for interfaces ##################################################
def __pari__(self): """ Returns the PARI version of this rational number.
EXAMPLES::
sage: n = 9390823/17 sage: m = n.__pari__(); m 9390823/17 sage: type(m) <type 'cypari2.gen.Gen'> sage: m.type() 't_FRAC' """
def _interface_init_(self, I=None): """ Return representation of this rational suitable for coercing into almost any computer algebra system.
OUTPUT: string
EXAMPLES::
sage: (2/3)._interface_init_() '2/3' sage: kash(3/1).Type() # optional - kash elt-fld^rat sage: magma(3/1).Type() # optional - magma FldRatElt """
def _sage_input_(self, sib, coerced): r""" Produce an expression which will reproduce this value when evaluated.
EXAMPLES::
sage: sage_input(QQ(1), verify=True) # Verified QQ(1) sage: sage_input(-22/7, verify=True) # Verified -22/7 sage: sage_input(-22/7, preparse=False) -ZZ(22)/7 sage: sage_input(10^-50, verify=True) # Verified 1/100000000000000000000000000000000000000000000000000 sage: from sage.misc.sage_input import SageInputBuilder sage: (-2/37)._sage_input_(SageInputBuilder(preparse=False), False) {unop:- {binop:/ {call: {atomic:ZZ}({atomic:2})} {atomic:37}}} sage: QQ(5)._sage_input_(SageInputBuilder(preparse=False), True) {atomic:5} """
# This code is extensively described in the docstring # for sage_input.py.
else: else:
# The except value is just some random double, it doesn't matter what it is. cdef double mpq_get_d_nearest(mpq_t x) except? -648555075988944.5: """ Convert a ``mpq_t`` to a ``double``, with round-to-nearest-even. This differs from ``mpq_get_d()`` which does round-to-zero.
TESTS::
sage: q = QQ(); float(q) 0.0 sage: q = 2^-10000; float(q) 0.0 sage: float(-q) -0.0 sage: q = 2^10000/1; float(q) inf sage: float(-q) -inf
::
sage: q = 2^-1075; float(q) 0.0 sage: float(-q) -0.0 sage: q = 2^52 / 2^1074; float(q) # Smallest normal double 2.2250738585072014e-308 sage: float(-q) -2.2250738585072014e-308 sage: q = (2^52 + 1/2) / 2^1074; float(q) 2.2250738585072014e-308 sage: float(-q) -2.2250738585072014e-308 sage: q = (2^52 + 1) / 2^1074; float(q) # Next normal double 2.225073858507202e-308 sage: float(-q) -2.225073858507202e-308 sage: q = (2^52 - 1) / 2^1074; float(q) # Largest denormal double 2.225073858507201e-308 sage: float(-q) -2.225073858507201e-308 sage: q = 1 / 2^1074; float(q) # Smallest denormal double 5e-324 sage: float(-q) -5e-324 sage: q = (1/2) / 2^1074; float(q) 0.0 sage: float(-q) -0.0 sage: q = (3/2) / 2^1074; float(q) 1e-323 sage: float(-q) -1e-323 sage: q = (2/3) / 2^1074; float(q) 5e-324 sage: float(-q) -5e-324 sage: q = (1/3) / 2^1074; float(q) 0.0 sage: float(-q) -0.0 sage: q = (2^53 - 1) * 2^971/1; float(q) # Largest double 1.7976931348623157e+308 sage: float(-q) -1.7976931348623157e+308 sage: q = (2^53) * 2^971/1; float(q) inf sage: float(-q) -inf sage: q = (2^53 - 1/2) * 2^971/1; float(q) inf sage: float(-q) -inf sage: q = (2^53 - 2/3) * 2^971/1; float(q) 1.7976931348623157e+308 sage: float(-q) -1.7976931348623157e+308
AUTHORS:
- Paul Zimmermann, Jeroen Demeyer (:trac:`14416`) """
# Easy case: both numerator and denominator are exactly # representable as doubles.
# General case
# We should shift a right by this amount
# At this point, we know that q0 = a/b / 2^shift satisfies # 2^53 < q0 < 2^55. # The end result d = q0 * 2^shift (rounded).
# Check for obvious overflow/underflow before shifting else: else:
# Compute q = trunc(a / 2^shift) and let remainder_is_zero be True # if and only if no truncation occurred. cdef mpz_t q, r cdef int remainder_is_zero else:
# Now divide by b to get q = trunc(a/b / 2^shift). # remainder_is_zero is True if and only if no truncation occurred # (in neither division).
# 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]
# The quotient q64 has 54 or 55 bits, but we need exactly 54. # Shift it down by 1 one if needed. cdef Py_ssize_t add_shift else:
# The result will be denormal, ensure the final shift is -1075 # to avoid a double rounding.
# Add add_shift to shift and let q = trunc(a/b / 2^shift) # for the new shift value. cdef uint64_t mask # We do an additional division of q by 2^add_shift.
# Round q64 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 q64 <= 2^54, # (with 2^53 <= q64 <= 2^54 unless in the denormal case).
def make_rational(s): """ Make a rational number from ``s`` (a string in base 32)
INPUT:
- ``s`` - string in base 32
OUTPUT: Rational
EXAMPLES::
sage: (-7/15).str(32) '-7/f' sage: sage.rings.rational.make_rational('-7/f') -7/15 """
cdef class Z_to_Q(Morphism): r""" A morphism from `\ZZ` to `\QQ`. """
def __init__(self): """ Create morphism from integers to rationals.
EXAMPLES::
sage: sage.rings.rational.Z_to_Q() Natural morphism: From: Integer Ring To: Rational Field """
cpdef Element _call_(self, x): """ Return the image of the morphism on ``x``.
EXAMPLES::
sage: sage.rings.rational.Z_to_Q()(2) # indirect doctest 2 """ cdef Rational rat
def _repr_type(self): """ Return string that describes the type of morphism.
EXAMPLES::
sage: sage.rings.rational.Z_to_Q()._repr_type() 'Natural' """
def section(self): """ Return a section of this morphism.
EXAMPLES::
sage: f = QQ.coerce_map_from(ZZ).section(); f Generic map: From: Rational Field To: Integer Ring
This map is a morphism in the category of sets with partial maps (see :trac:`15618`)::
sage: f.parent() Set of Morphisms from Rational Field to Integer Ring in Category of sets with partial maps """
def is_surjective(self): r""" Return whether this morphism is surjective.
EXAMPLES::
sage: QQ.coerce_map_from(ZZ).is_surjective() False
"""
cdef class Q_to_Z(Map): r""" A morphism from `\QQ` to `\ZZ`.
TESTS::
sage: type(ZZ.convert_map_from(QQ)) <type 'sage.rings.rational.Q_to_Z'> """ cpdef Element _call_(self, x): """ A fast map from the rationals to the integers.
EXAMPLES::
sage: f = sage.rings.rational.Q_to_Z(QQ, ZZ) sage: f(1/2) # indirect doctest Traceback (most recent call last): ... TypeError: no conversion of this rational to integer sage: f(4/2) # indirect doctest 2 """
def section(self): """ Return a section of this morphism.
EXAMPLES::
sage: sage.rings.rational.Q_to_Z(QQ, ZZ).section() Natural morphism: From: Integer Ring To: Rational Field """
cdef class int_to_Q(Morphism): r""" A morphism from Python 2 ``int`` to `\QQ`. """ def __init__(self): """ Initialize ``self``.
EXAMPLES::
sage: sage.rings.rational.int_to_Q() Native morphism: From: Set of Python objects of class 'int' To: Rational Field """
cpdef Element _call_(self, a): """ Return the image of the morphism on ``a``.
EXAMPLES::
sage: f = sage.rings.rational.int_to_Q() sage: f(int(4)) # indirect doctest 4 sage: f(4^100) # py2 - this will crash on Python 3 Traceback (most recent call last): ... TypeError: must be a Python int object """
cdef Rational rat
def _repr_type(self): """ Return string that describes the type of morphism.
EXAMPLES::
sage: sage.rings.rational.int_to_Q()._repr_type() 'Native' """
cdef class long_to_Q(Morphism): r""" A morphism from Python 2 ``long``/Python 3 ``int`` to `\QQ`. """ def __init__(self): """ Initialize ``self``.
EXAMPLES::
sage: sage.rings.rational.long_to_Q() # py2 Native morphism: From: Set of Python objects of class 'long' To: Rational Field sage: sage.rings.rational.long_to_Q() # py3 Native morphism: From: Set of Python objects of class 'int' To: Rational Field """
cpdef Element _call_(self, a): """ Return the image of the morphism on ``a``.
EXAMPLES::
sage: f = sage.rings.rational.long_to_Q() sage: f(long(4)) # indirect doctest 4 sage: f(long(4^100)) 1606938044258990275541962092341162602522202993782792835301376 """
cdef Rational rat cdef long a_long
else:
def _repr_type(self): """ Return string that describes the type of morphism.
EXAMPLES::
sage: sage.rings.rational.long_to_Q()._repr_type() 'Native' """ |