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
""" Fraction Field Elements
AUTHORS:
- William Stein (input from David Joyner, David Kohel, and Joe Wetherell)
- Sebastian Pancratz (2010-01-06): Rewrite of addition, multiplication and derivative to use Henrici's algorithms [Ho72]
REFERENCES:
.. [Ho72] \E. Horowitz, "Algorithms for Rational Function Arithmetic Operations", Annual ACM Symposium on Theory of Computing, Proceedings of the Fourth Annual ACM Symposium on Theory of Computing, pp. 108--118, 1972
"""
#***************************************************************************** # Copyright (C) 2005 William Stein <wstein@gmail.com> # # This program is free software: you can redistribute it and/or modify # it under the terms of the GNU General Public License 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 sage.structure.element cimport FieldElement, parent from sage.structure.richcmp cimport richcmp
from . import integer_ring from .integer_ring import ZZ from .rational_field import QQ
import sage.misc.latex as latex
def is_FractionFieldElement(x): """ Return whether or not ``x`` is a :class:`FractionFieldElement`.
EXAMPLES::
sage: from sage.rings.fraction_field_element import is_FractionFieldElement sage: R.<x> = ZZ[] sage: is_FractionFieldElement(x/2) False sage: is_FractionFieldElement(2/x) True sage: is_FractionFieldElement(1/3) False """
cdef class FractionFieldElement(FieldElement): """ EXAMPLES::
sage: K = FractionField(PolynomialRing(QQ, 'x')) sage: K Fraction Field of Univariate Polynomial Ring in x over Rational Field sage: loads(K.dumps()) == K True sage: x = K.gen() sage: f = (x^3 + x)/(17 - x^19); f (x^3 + x)/(-x^19 + 17) sage: loads(f.dumps()) == f True
TESTS:
Test if :trac:`5451` is fixed::
sage: A = FiniteField(9,'theta')['t'] sage: K.<t> = FractionField(A) sage: f= 2/(t^2+2*t); g =t^9/(t^18 + t^10 + t^2);f+g (2*t^15 + 2*t^14 + 2*t^13 + 2*t^12 + 2*t^11 + 2*t^10 + 2*t^9 + t^7 + t^6 + t^5 + t^4 + t^3 + t^2 + t + 1)/(t^17 + t^9 + t)
Test if :trac:`8671` is fixed::
sage: P.<n> = QQ[] sage: F = P.fraction_field() sage: P.one()//F.one() 1 sage: F.one().quo_rem(F.one()) (1, 0) """ cdef object __numerator cdef object __denominator
def __init__(self, parent, numerator, denominator=1, coerce=True, reduce=True): """ Initialize ``self``.
EXAMPLES::
sage: from sage.rings.fraction_field_element import FractionFieldElement sage: K.<x> = Frac(ZZ['x']) sage: FractionFieldElement(K, x, 4) x/4 sage: FractionFieldElement(K, x, x, reduce=False) x/x sage: f = FractionFieldElement(K, 'hi', 1, coerce=False, reduce=False) sage: f.numerator() 'hi'
sage: x = var('x') sage: K((x + 1)/(x^2 + x + 1)) (x + 1)/(x^2 + x + 1) sage: K(355/113) 355/113
""" else: pass raise ZeroDivisionError("fraction field element division by zero")
def _im_gens_(self, codomain, im_gens): """ EXAMPLES::
sage: F = ZZ['x,y'].fraction_field() sage: x,y = F.gens() sage: K = GF(7)['a,b'].fraction_field() sage: a,b = K.gens()
::
sage: phi = F.hom([a+b, a*b], K) sage: phi(x+y) # indirect doctest a*b + a + b
::
sage: (x^2/y)._im_gens_(K, [a+b, a*b]) (a^2 + 2*a*b + b^2)/(a*b) sage: (x^2/y)._im_gens_(K, [a, a*b]) a/b """
def reduce(self): """ Divides out the gcd of the numerator and denominator.
Automatically called for exact rings, but because it may be numerically unstable for inexact rings it must be called manually in that case.
EXAMPLES::
sage: R.<x> = RealField(10)[] sage: f = (x^2+2*x+1)/(x+1); f (x^2 + 2.0*x + 1.0)/(x + 1.0) sage: f.reduce(); f x + 1.0 """ else: except Exception: pass
def __copy__(self): """ Make a copy of ``self``.
EXAMPLES::
sage: R.<x,y> = ZZ[] sage: f = x/y+1; f (x + y)/y sage: copy(f) (x + y)/y """
def numerator(self): """ Return the numerator of ``self``.
EXAMPLES::
sage: R.<x,y> = ZZ[] sage: f = x/y+1; f (x + y)/y sage: f.numerator() x + y """
def denominator(self): """ Return the denominator of ``self``.
EXAMPLES::
sage: R.<x,y> = ZZ[] sage: f = x/y+1; f (x + y)/y sage: f.denominator() y """
def is_square(self,root=False): """ Return whether or not ``self`` is a perfect square.
If the optional argument ``root`` is ``True``, then also returns a square root (or ``None``, if the fraction field element is not square).
INPUT:
- ``root`` -- whether or not to also return a square root (default: ``False``)
OUTPUT:
- ``bool`` - whether or not a square
- ``object`` - (optional) an actual square root if found, and None otherwise.
EXAMPLES::
sage: R.<t> = QQ[] sage: (1/t).is_square() False sage: (1/t^6).is_square() True sage: ((1+t)^4/t^6).is_square() True sage: (4*(1+t)^4/t^6).is_square() True sage: (2*(1+t)^4/t^6).is_square() False sage: ((1+t)/t^6).is_square() False
sage: (4*(1+t)^4/t^6).is_square(root=True) (True, (2*t^2 + 4*t + 2)/t^3) sage: (2*(1+t)^4/t^6).is_square(root=True) (False, None)
sage: R.<x> = QQ[] sage: a = 2*(x+1)^2 / (2*(x-1)^2); a (2*x^2 + 4*x + 2)/(2*x^2 - 4*x + 2) sage: a.numerator().is_square() False sage: a.is_square() True sage: (0/x).is_square() True """
def __hash__(self): """ This function hashes in a special way to ensure that generators of a ring `R` and generators of a fraction field of `R` have the same hash. This enables them to be used as keys interchangeably in a dictionary (since ``==`` will claim them equal). This is particularly useful for methods like ``subs`` on ``ParentWithGens`` if you are passing a dictionary of substitutions.
EXAMPLES::
sage: R.<x> = ZZ[] sage: hash(R.0) == hash(FractionField(R).0) True sage: ((x+1)/(x^2+1)).subs({x:1}) 1 sage: d={x:1} sage: d[FractionField(R).0] 1 sage: R.<x>=QQ[] # this probably has a separate implementation from ZZ[] sage: hash(R.0)==hash(FractionField(R).0) True sage: d={x:1} sage: d[FractionField(R).0] 1 sage: R.<x,y,z>=ZZ[] # this probably has a separate implementation from ZZ[] sage: hash(R.0)==hash(FractionField(R).0) True sage: d={x:1} sage: d[FractionField(R).0] 1 sage: R.<x,y,z>=QQ[] # this probably has a separate implementation from ZZ[] sage: hash(R.0)==hash(FractionField(R).0) True sage: ((x+1)/(x^2+1)).subs({x:1}) 1 sage: d={x:1} sage: d[FractionField(R).0] 1 sage: hash(R(1)/R(2))==hash(1/2) True """ # This is same algorithm as used for members of QQ #cdef long n, d
def __call__(self, *x, **kwds): """ Evaluate the fraction at the given arguments.
This assumes that a call function is defined for the numerator and denominator.
EXAMPLES::
sage: x = PolynomialRing(RationalField(),'x',3).gens() sage: f = x[0] + x[1] - 2*x[1]*x[2] sage: f -2*x1*x2 + x0 + x1 sage: f(1,2,5) -17 sage: h = f /(x[1] + x[2]) sage: h (-2*x1*x2 + x0 + x1)/(x1 + x2) sage: h(1,2,5) -17/7 sage: h(x0=1) (-2*x1*x2 + x1 + 1)/(x1 + x2) """
def _is_atomic(self): """ EXAMPLES::
sage: K.<x> = Frac(ZZ['x']) sage: x._is_atomic() True sage: f = 1/(x+1) sage: f._is_atomic() False """
def _repr_(self): """ Return a string representation of ``self``.
EXAMPLES::
sage: K.<x> = Frac(ZZ['x']) sage: repr(x+1) # indirect doctest 'x + 1' sage: repr((x+1)/(x-1)) '(x + 1)/(x - 1)' sage: repr(1/(x-1)) '1/(x - 1)' sage: repr(1/x) '1/x' """ else:
def _latex_(self): r""" Return a latex representation of this fraction field element.
EXAMPLES::
sage: R = PolynomialRing(QQ, 'x') sage: F = R.fraction_field() sage: x = F.gen() sage: a = x^2 / 1 sage: latex(a) # indirect doctest x^{2} sage: latex(x^2/(x^2+1)) \frac{x^{2}}{x^{2} + 1} sage: a = 1/x sage: latex(a) \frac{1}{x}
TESTS::
sage: R = RR['x'] # Inexact, so no reduction. sage: F = Frac(R) sage: from sage.rings.fraction_field_element import FractionFieldElement sage: z = FractionFieldElement(F, 0, R.gen(), coerce=False) sage: z.numerator() == 0 True sage: z.denominator() == R.gen() True sage: latex(z) # indirect doctest 0 """
def _magma_init_(self, magma): """ Return a string representation of ``self`` Magma can understand.
EXAMPLES::
sage: R.<x> = ZZ[] sage: magma((x^2 + x + 1)/(x + 1)) # optional - magma # indirect doctest (x^2 + x + 1)/(x + 1)
::
sage: R.<x,y> = QQ[] sage: magma((x+y)/x) # optional - magma (x + y)/x """ pgens = magma(self._parent).gens()
s = self._repr_() for i, j in zip(self._parent.variable_names(), pgens): s = s.replace(i, j.name())
return s
cpdef _add_(self, right): """ Compute the sum of ``self`` and ``right``.
INPUT:
- ``right`` -- ``ModuleElement`` to add to ``self``
OUTPUT:
- Sum of ``self`` and ``right``
EXAMPLES::
sage: K.<x,y> = Frac(ZZ['x,y']) sage: x+y # indirect doctest x + y sage: 1/x + 1/y (x + y)/(x*y) sage: 1/x + 1/(x*y) (y + 1)/(x*y) sage: Frac(CDF['x']).gen() + 3 x + 3.0
Subtraction is implemented by adding the negative::
sage: K.<t> = Frac(GF(7)['t']) sage: t - 1/t # indirect doctest (t^2 + 6)/t """
else: else: except AttributeError: pass except NotImplementedError: pass pass pass except TypeError: pass
cpdef _mul_(self, right): """ Computes the product of ``self`` and ``right``.
INPUT:
- ``right`` - ``RingElement`` to multiply with ``self``
OUTPUT:
- Product of ``self`` and ``right``
EXAMPLES::
sage: K.<t> = Frac(GF(7)['t']) sage: a = t/(1+t) sage: b = 3/t sage: a*b # indirect doctest 3/(t + 1) """
except AttributeError: pass except NotImplementedError: pass pass pass pass
cpdef _div_(self, right): """ Computes the quotient of ``self`` and ``right``.
INPUT:
- ``right`` -- ``RingElement`` that is the divisor
OUTPUT:
Quotient of ``self`` and ``right``
EXAMPLES::
sage: K.<x,y,z> = Frac(ZZ['x,y,z']) sage: a = (x+1)*(x+y)/(z-3) # indirect doctest sage: b = (x+y)/(z-1) sage: a/b (x*z - x + z - 1)/(z - 3) """
def __int__(self): """ EXAMPLES::
sage: K = Frac(ZZ['x']) sage: int(K(-3)) -3 sage: K.<x> = Frac(RR['x']) sage: x/x x/x sage: int(x/x) 1 sage: int(K(.5)) 0 """ else: raise TypeError("denominator must equal 1")
def _integer_(self, Z=ZZ): """ EXAMPLES::
sage: K = Frac(ZZ['x']) sage: K(5)._integer_() 5 sage: K.<x> = Frac(RR['x']) sage: ZZ(2*x/x) 2 """
def _rational_(self, Q=QQ): """ EXAMPLES::
sage: K.<x> = Frac(QQ['x']) sage: K(1/2)._rational_() 1/2 sage: K(1/2 + x/x)._rational_() 3/2 """
def __long__(self): """ EXAMPLES::
sage: K.<x> = Frac(QQ['x']) sage: long(K(3)) 3L sage: long(K(3/5)) 0L """
def __pow__(self, right, dummy): r""" Returns self raised to the `right^{th}` power.
Note that we need to check whether or not right is negative so we don't set ``__numerator`` or ``__denominator`` to an element of the fraction field instead of the underlying ring.
EXAMPLES::
sage: R = QQ['x','y'] sage: FR = R.fraction_field() sage: x,y = FR.gens() sage: a = x^2; a x^2 sage: type(a.numerator()) <type 'sage.rings.polynomial.multi_polynomial_libsingular.MPolynomial_libsingular'> sage: type(a.denominator()) <type 'sage.rings.polynomial.multi_polynomial_libsingular.MPolynomial_libsingular'> sage: a = x^(-2); a 1/x^2 sage: type(a.numerator()) <type 'sage.rings.polynomial.multi_polynomial_libsingular.MPolynomial_libsingular'> sage: type(a.denominator()) <type 'sage.rings.polynomial.multi_polynomial_libsingular.MPolynomial_libsingular'> sage: x^0 1 sage: ((x+y)/(x-y))^2 (x^2 + 2*x*y + y^2)/(x^2 - 2*x*y + y^2) sage: ((x+y)/(x-y))^-2 (x^2 - 2*x*y + y^2)/(x^2 + 2*x*y + y^2) sage: ((x+y)/(x-y))^0 1 """ else:
def __neg__(self): """ EXAMPLES::
sage: K.<t> = Frac(GF(5)['t']) sage: f = (t^2+t)/(t+2); f (t^2 + t)/(t + 2) sage: -f (4*t^2 + 4*t)/(t + 2) """
def __abs__(self): """ EXAMPLES::
sage: from sage.rings.fraction_field_element import FractionFieldElement sage: abs(FractionFieldElement(QQ, -2, 3, coerce=False)) 2/3 """
def __invert__(self): """ EXAMPLES::
sage: K.<t> = Frac(GF(7)['t']) sage: f = (t^2+5)/(t-1) sage: ~f (t + 6)/(t^2 + 5) """ raise ZeroDivisionError("Cannot invert 0")
def __float__(self): """ EXAMPLES::
sage: K.<x,y> = Frac(ZZ['x,y']) sage: float(x/x + y/y) 2.0 """
cpdef _richcmp_(self, other, int op): """ EXAMPLES::
sage: K.<t> = Frac(GF(7)['t']) sage: t/t == 1 True sage: t+1/t == (t^2+1)/t True sage: t == t/5 False
::
sage: K.<x,y> = Frac(ZZ['x,y']) sage: x > y True sage: 1 > y False """ (<FractionFieldElement>other).__numerator, op)
def valuation(self, v=None): """ Return the valuation of ``self``, assuming that the numerator and denominator have valuation functions defined on them.
EXAMPLES::
sage: x = PolynomialRing(RationalField(),'x').gen() sage: f = (x^3 + x)/(x^2 - 2*x^3) sage: f (x^2 + 1)/(-2*x^2 + x) sage: f.valuation() -1 sage: f.valuation(x^2+1) 1 """
def __nonzero__(self): """ Return ``True`` if this element is nonzero.
EXAMPLES::
sage: F = ZZ['x,y'].fraction_field() sage: x,y = F.gens() sage: t = F(0)/x sage: bool(t) False
::
sage: bool(1/x) True """
def is_zero(self): """ Return ``True`` if this element is equal to zero.
EXAMPLES::
sage: F = ZZ['x,y'].fraction_field() sage: x,y = F.gens() sage: t = F(0)/x sage: t.is_zero() True sage: u = 1/x - 1/x sage: u.is_zero() True sage: u.parent() is F True """
def is_one(self): """ Return ``True`` if this element is equal to one.
EXAMPLES::
sage: F = ZZ['x,y'].fraction_field() sage: x,y = F.gens() sage: (x/x).is_one() True sage: (x/y).is_one() False """
def _symbolic_(self, ring): """ Return ``self`` as a fraction in the ring ``ring``. Used for :func:`symbolic_expression` in creating a symbolic expression of ``self``.
EXAMPLES::
sage: F = ZZ['x,y'].fraction_field() sage: x,y = F.gens() sage: elt = (2*x + 2*y) / (3*x - 3*y); elt (2*x + 2*y)/(3*x - 3*y) sage: elt._symbolic_(SR) 2/3*(x + y)/(x - y) sage: symbolic_expression(elt) 2/3*(x + y)/(x - y) """
def __reduce__(self): """ For pickling.
EXAMPLES::
sage: F = ZZ['x,y'].fraction_field() sage: f = F.random_element() sage: loads(f.dumps()) == f True """
def _evaluate_polynomial(self, pol): """ Evaluate a univariate polynomial on this fraction.
EXAMPLES::
sage: R.<x> = QQ[] sage: pol = x^3 + 1 sage: pol(1/x) (x^3 + 1)/x^3
TESTS::
sage: R.<y,z> = ZZ[] sage: (~(y+z))._evaluate_polynomial(pol) (y^3 + 3*y^2*z + 3*y*z^2 + z^3 + 1)/(y^3 + 3*y^2*z + 3*y*z^2 + z^3) sage: rat = (y+z)/y sage: rat._evaluate_polynomial(pol) Traceback (most recent call last): ... NotImplementedError sage: pol(rat) (2*y^3 + 3*y^2*z + 3*y*z^2 + z^3)/y^3 """ else:
class FractionFieldElement_1poly_field(FractionFieldElement): """ A fraction field element where the parent is the fraction field of a univariate polynomial ring.
Many of the functions here are included for coherence with number fields. """ def is_integral(self): """ Returns whether this element is actually a polynomial.
EXAMPLES::
sage: R.<t> = QQ[] sage: elt = (t^2 + t - 2) / (t + 2); elt # == (t + 2)*(t - 1)/(t + 2) t - 1 sage: elt.is_integral() True sage: elt = (t^2 - t) / (t+2); elt # == t*(t - 1)/(t + 2) (t^2 - t)/(t + 2) sage: elt.is_integral() False """
def support(self): """ Returns a sorted list of primes dividing either the numerator or denominator of this element.
EXAMPLES::
sage: R.<t> = QQ[] sage: h = (t^14 + 2*t^12 - 4*t^11 - 8*t^9 + 6*t^8 + 12*t^6 - 4*t^5 - 8*t^3 + t^2 + 2)/(t^6 + 6*t^5 + 9*t^4 - 2*t^2 - 12*t - 18) sage: h.support() [t - 1, t + 3, t^2 + 2, t^2 + t + 1, t^4 - 2] """
def make_element(parent, numerator, denominator): """ Used for unpickling :class:`FractionFieldElement` objects (and subclasses).
EXAMPLES::
sage: from sage.rings.fraction_field_element import make_element sage: R = ZZ['x,y'] sage: x,y = R.gens() sage: F = R.fraction_field() sage: make_element(F, 1+x, 1+y) (x + 1)/(y + 1) """
def make_element_old(parent, cdict): """ Used for unpickling old :class:`FractionFieldElement` pickles.
EXAMPLES::
sage: from sage.rings.fraction_field_element import make_element_old sage: R.<x,y> = ZZ[] sage: F = R.fraction_field() sage: make_element_old(F, {'_FractionFieldElement__numerator':x+y,'_FractionFieldElement__denominator':x-y}) (x + y)/(x - y) """ |