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
""" Field of Algebraic Numbers
AUTHOR:
- Carl Witty (2007-01-27): initial version - Carl Witty (2007-10-29): massive rewrite to support complex as well as real numbers
This is an implementation of the algebraic numbers (the complex numbers which are the zero of a polynomial in `\ZZ[x]`; in other words, the algebraic closure of `\QQ`, with an embedding into `\CC`). All computations are exact. We also include an implementation of the algebraic reals (the intersection of the algebraic numbers with `\RR`). The field of algebraic numbers `\QQbar` is available with abbreviation ``QQbar``; the field of algebraic reals has abbreviation ``AA``.
As with many other implementations of the algebraic numbers, we try hard to avoid computing a number field and working in the number field; instead, we use floating-point interval arithmetic whenever possible (basically whenever we need to prove non-equalities), and resort to symbolic computation only as needed (basically to prove equalities).
Algebraic numbers exist in one of the following forms:
- a rational number
- the sum, difference, product, or quotient of algebraic numbers
- the negation, inverse, absolute value, norm, real part, imaginary part, or complex conjugate of an algebraic number
- a particular root of a polynomial, given as a polynomial with algebraic coefficients together with an isolating interval (given as a ``RealIntervalFieldElement``) which encloses exactly one root, and the multiplicity of the root
- a polynomial in one generator, where the generator is an algebraic number given as the root of an irreducible polynomial with integral coefficients and the polynomial is given as a ``NumberFieldElement``.
An algebraic number can be coerced into ``ComplexIntervalField`` (or ``RealIntervalField``, for algebraic reals); every algebraic number has a cached interval of the highest precision yet calculated.
In most cases, computations that need to compare two algebraic numbers compute them with 128-bit precision intervals; if this does not suffice to prove that the numbers are different, then we fall back on exact computation.
Note that division involves an implicit comparison of the divisor against zero, and may thus trigger exact computation.
Also, using an algebraic number in the leading coefficient of a polynomial also involves an implicit comparison against zero, which again may trigger exact computation.
Note that we work fairly hard to avoid computing new number fields; to help, we keep a lattice of already-computed number fields and their inclusions.
EXAMPLES::
sage: sqrt(AA(2)) > 0 True sage: (sqrt(5 + 2*sqrt(QQbar(6))) - sqrt(QQbar(3)))^2 == 2 True sage: AA((sqrt(5 + 2*sqrt(6)) - sqrt(3))^2) == 2 True
For a monic cubic polynomial `x^3 + bx^2 + cx + d` with roots `s1`, `s2`, `s3`, the discriminant is defined as `(s1-s2)^2(s1-s3)^2(s2-s3)^2` and can be computed as `b^2c^2 - 4b^3d - 4c^3 + 18bcd - 27d^2`. We can test that these definitions do give the same result::
sage: def disc1(b, c, d): ....: return b^2*c^2 - 4*b^3*d - 4*c^3 + 18*b*c*d - 27*d^2 sage: def disc2(s1, s2, s3): ....: return ((s1-s2)*(s1-s3)*(s2-s3))^2 sage: x = polygen(AA) sage: p = x*(x-2)*(x-4) sage: cp = AA.common_polynomial(p) sage: d, c, b, _ = p.list() sage: s1 = AA.polynomial_root(cp, RIF(-1, 1)) sage: s2 = AA.polynomial_root(cp, RIF(1, 3)) sage: s3 = AA.polynomial_root(cp, RIF(3, 5)) sage: disc1(b, c, d) == disc2(s1, s2, s3) True sage: p = p + 1 sage: cp = AA.common_polynomial(p) sage: d, c, b, _ = p.list() sage: s1 = AA.polynomial_root(cp, RIF(-1, 1)) sage: s2 = AA.polynomial_root(cp, RIF(1, 3)) sage: s3 = AA.polynomial_root(cp, RIF(3, 5)) sage: disc1(b, c, d) == disc2(s1, s2, s3) True sage: p = (x-sqrt(AA(2)))*(x-AA(2).nth_root(3))*(x-sqrt(AA(3))) sage: cp = AA.common_polynomial(p) sage: d, c, b, _ = p.list() sage: s1 = AA.polynomial_root(cp, RIF(1.4, 1.5)) sage: s2 = AA.polynomial_root(cp, RIF(1.7, 1.8)) sage: s3 = AA.polynomial_root(cp, RIF(1.2, 1.3)) sage: disc1(b, c, d) == disc2(s1, s2, s3) True
We can convert from symbolic expressions::
sage: QQbar(sqrt(-5)) 2.236067977499790?*I sage: AA(sqrt(2) + sqrt(3)) 3.146264369941973? sage: QQbar(I) I sage: AA(I) Traceback (most recent call last): ... ValueError: Cannot coerce algebraic number with non-zero imaginary part to algebraic real sage: QQbar(I * golden_ratio) 1.618033988749895?*I sage: AA(golden_ratio)^2 - AA(golden_ratio) 1 sage: QQbar((-8)^(1/3)) 1.000000000000000? + 1.732050807568878?*I sage: AA((-8)^(1/3)) -2 sage: QQbar((-4)^(1/4)) 1 + 1*I sage: AA((-4)^(1/4)) Traceback (most recent call last): ... ValueError: Cannot coerce algebraic number with non-zero imaginary part to algebraic real
The coercion, however, goes in the other direction, since not all symbolic expressions are algebraic numbers::
sage: QQbar(sqrt(2)) + sqrt(3) sqrt(3) + 1.414213562373095? sage: QQbar(sqrt(2) + QQbar(sqrt(3))) 3.146264369941973?
Note the different behavior in taking roots: for ``AA`` we prefer real roots if they exist, but for ``QQbar`` we take the principal root::
sage: AA(-1)^(1/3) -1 sage: QQbar(-1)^(1/3) 0.500000000000000? + 0.866025403784439?*I
We can explicitly coerce from `\QQ[I]`. (Technically, this is not quite kosher, since `\QQ[I]` doesn't come with an embedding; we do not know whether the field generator is supposed to map to `+I` or `-I`. We assume that for any quadratic field with polynomial `x^2+1`, the generator maps to `+I`.)::
sage: K.<im> = QQ[I] sage: pythag = QQbar(3/5 + 4*im/5); pythag 4/5*I + 3/5 sage: pythag.abs() == 1 True
However, implicit coercion from `\QQ[I]` is not allowed::
sage: QQbar(1) + im Traceback (most recent call last): ... TypeError: unsupported operand parent(s) for +: 'Algebraic Field' and 'Number Field in I with defining polynomial x^2 + 1'
We can implicitly coerce from algebraic reals to algebraic numbers::
sage: a = QQbar(1); a, a.parent() (1, Algebraic Field) sage: b = AA(1); b, b.parent() (1, Algebraic Real Field) sage: c = a + b; c, c.parent() (2, Algebraic Field)
Some computation with radicals::
sage: phi = (1 + sqrt(AA(5))) / 2 sage: phi^2 == phi + 1 True sage: tau = (1 - sqrt(AA(5))) / 2 sage: tau^2 == tau + 1 True sage: phi + tau == 1 True sage: tau < 0 True
sage: rt23 = sqrt(AA(2/3)) sage: rt35 = sqrt(AA(3/5)) sage: rt25 = sqrt(AA(2/5)) sage: rt23 * rt35 == rt25 True
The Sage rings ``AA`` and ``QQbar`` can decide equalities between radical expressions (over the reals and complex numbers respectively)::
sage: a = AA((2/(3*sqrt(3)) + 10/27)^(1/3) - 2/(9*(2/(3*sqrt(3)) + 10/27)^(1/3)) + 1/3) sage: a 1.000000000000000? sage: a == 1 True
Algebraic numbers which are known to be rational print as rationals; otherwise they print as intervals (with 53-bit precision)::
sage: AA(2)/3 2/3 sage: QQbar(5/7) 5/7 sage: QQbar(1/3 - 1/4*I) -1/4*I + 1/3 sage: two = QQbar(4).nth_root(4)^2; two 2.000000000000000? sage: two == 2; two True 2 sage: phi 1.618033988749895?
We can find the real and imaginary parts of an algebraic number (exactly)::
sage: r = QQbar.polynomial_root(x^5 - x - 1, CIF(RIF(0.1, 0.2), RIF(1.0, 1.1))); r 0.1812324444698754? + 1.083954101317711?*I sage: r.real() 0.1812324444698754? sage: r.imag() 1.083954101317711? sage: r.minpoly() x^5 - x - 1 sage: r.real().minpoly() x^10 + 3/16*x^6 + 11/32*x^5 - 1/64*x^2 + 1/128*x - 1/1024 sage: r.imag().minpoly() # long time (10s on sage.math, 2013) x^20 - 5/8*x^16 - 95/256*x^12 - 625/1024*x^10 - 5/512*x^8 - 1875/8192*x^6 + 25/4096*x^4 - 625/32768*x^2 + 2869/1048576
We can find the absolute value and norm of an algebraic number exactly. (Note that we define the norm as the product of a number and its complex conjugate; this is the algebraic definition of norm, if we view ``QQbar`` as ``AA[I]``.)::
sage: R.<x> = QQ[] sage: r = (x^3 + 8).roots(QQbar, multiplicities=False)[2]; r 1.000000000000000? + 1.732050807568878?*I sage: r.abs() == 2 True sage: r.norm() == 4 True sage: (r+QQbar(I)).norm().minpoly() x^2 - 10*x + 13 sage: r = AA.polynomial_root(x^2 - x - 1, RIF(-1, 0)); r -0.618033988749895? sage: r.abs().minpoly() x^2 + x - 1
We can compute the multiplicative order of an algebraic number::
sage: QQbar(-1/2 + I*sqrt(3)/2).multiplicative_order() 3 sage: QQbar(-sqrt(3)/2 + I/2).multiplicative_order() 12 sage: (QQbar.zeta(23)**5).multiplicative_order() 23
The paper "ARPREC: An Arbitrary Precision Computation Package" by Bailey, Yozo, Li and Thompson discusses this result. Evidently it is difficult to find, but we can easily verify it. ::
sage: alpha = QQbar.polynomial_root(x^10 + x^9 - x^7 - x^6 - x^5 - x^4 - x^3 + x + 1, RIF(1, 1.2)) sage: lhs = alpha^630 - 1 sage: rhs_num = (alpha^315 - 1) * (alpha^210 - 1) * (alpha^126 - 1)^2 * (alpha^90 - 1) * (alpha^3 - 1)^3 * (alpha^2 - 1)^5 * (alpha - 1)^3 sage: rhs_den = (alpha^35 - 1) * (alpha^15 - 1)^2 * (alpha^14 - 1)^2 * (alpha^5 - 1)^6 * alpha^68 sage: rhs = rhs_num / rhs_den sage: lhs 2.642040335819351?e44 sage: rhs 2.642040335819351?e44 sage: lhs - rhs 0.?e29 sage: lhs == rhs True sage: lhs - rhs 0 sage: lhs._exact_value() -10648699402510886229334132989629606002223831*a^9 + 23174560249100286133718183712802529035435800*a^8 - 27259790692625442252605558473646959458901265*a^7 + 21416469499004652376912957054411004410158065*a^6 - 14543082864016871805545108986578337637140321*a^5 + 6458050008796664339372667222902512216589785*a^4 + 3052219053800078449122081871454923124998263*a^3 - 14238966128623353681821644902045640915516176*a^2 + 16749022728952328254673732618939204392161001*a - 9052854758155114957837247156588012516273410 where a^10 - a^9 + a^7 - a^6 + a^5 - a^4 + a^3 - a + 1 = 0 and a in -1.176280818259918?
Given an algebraic number, we can produce a string that will reproduce that algebraic number if you type the string into Sage. We can see that until exact computation is triggered, an algebraic number keeps track of the computation steps used to produce that number::
sage: rt2 = AA(sqrt(2)) sage: rt3 = AA(sqrt(3)) sage: n = (rt2 + rt3)^5; n 308.3018001722975? sage: sage_input(n) R.<x> = AA[] v1 = AA.polynomial_root(AA.common_polynomial(x^2 - 2), RIF(RR(1.4142135623730949), RR(1.4142135623730951))) + AA.polynomial_root(AA.common_polynomial(x^2 - 3), RIF(RR(1.7320508075688772), RR(1.7320508075688774))) v2 = v1*v1 v2*v2*v1
But once exact computation is triggered, the computation tree is discarded, and we get a way to produce the number directly::
sage: n == 109*rt2 + 89*rt3 True sage: sage_input(n) R.<x> = AA[] v = AA.polynomial_root(AA.common_polynomial(x^4 - 4*x^2 + 1), RIF(RR(0.51763809020504148), RR(0.51763809020504159))) -109*v^3 - 89*v^2 + 327*v + 178
We can also see that some computations (basically, those which are easy to perform exactly) are performed directly, instead of storing the computation tree::
sage: z3_3 = QQbar.zeta(3) * 3 sage: z4_4 = QQbar.zeta(4) * 4 sage: z5_5 = QQbar.zeta(5) * 5 sage: sage_input(z3_3 * z4_4 * z5_5) R.<x> = AA[] 3*QQbar.polynomial_root(AA.common_polynomial(x^2 + x + 1), CIF(RIF(-RR(0.50000000000000011), -RR(0.49999999999999994)), RIF(RR(0.8660254037844386), RR(0.86602540378443871))))*QQbar(4*I)*(5*QQbar.polynomial_root(AA.common_polynomial(x^4 + x^3 + x^2 + x + 1), CIF(RIF(RR(0.3090169943749474), RR(0.30901699437494745)), RIF(RR(0.95105651629515353), RR(0.95105651629515364)))))
Note that the ``verify=True`` argument to ``sage_input`` will always trigger exact computation, so running ``sage_input`` twice in a row on the same number will actually give different answers. In the following, running ``sage_input`` on ``n`` will also trigger exact computation on ``rt2``, as you can see by the fact that the third output is different than the first::
sage: rt2 = AA(sqrt(2)) sage: n = rt2^2 sage: sage_input(n, verify=True) # Verified R.<x> = AA[] v = AA.polynomial_root(AA.common_polynomial(x^2 - 2), RIF(RR(1.4142135623730949), RR(1.4142135623730951))) v*v sage: sage_input(n, verify=True) # Verified AA(2) sage: n = rt2^2 sage: sage_input(n, verify=True) # Verified AA(2)
Just for fun, let's try ``sage_input`` on a very complicated expression. The output of this example changed with the rewriting of polynomial multiplication algorithms in :trac:`10255`::
sage: rt2 = sqrt(AA(2)) sage: rt3 = sqrt(QQbar(3)) sage: x = polygen(QQbar) sage: nrt3 = AA.polynomial_root((x-rt2)*(x+rt3), RIF(-2, -1)) sage: one = AA.polynomial_root((x-rt2)*(x-rt3)*(x-nrt3)*(x-1-rt3-nrt3), RIF(0.9, 1.1)) sage: one 1.000000000000000? sage: sage_input(one, verify=True) # Verified R1 = QQbar['x'] x1 = R1.gen() R2 = AA['x'] x2 = R2.gen() cp1 = AA.common_polynomial(x2^2 - 2) v1 = QQbar.polynomial_root(cp1, RIF(RR(1.4142135623730949), RR(1.4142135623730951))) v2 = QQbar.polynomial_root(AA.common_polynomial(x1^2 - 3), CIF(RIF(RR(1.7320508075688772), RR(1.7320508075688774)), RIF(RR(0)))) v3 = -v1 - v2 v4 = QQbar.polynomial_root(cp1, RIF(RR(1.4142135623730949), RR(1.4142135623730951))) cp2 = AA.common_polynomial(x1^2 + (-v4 + v2)*x1 - v4*v2) v5 = QQbar.polynomial_root(cp2, RIF(-RR(1.7320508075688774), -RR(1.7320508075688772))) v6 = v3 - v5 v7 = -1 - v2 - QQbar.polynomial_root(cp2, RIF(-RR(1.7320508075688774), -RR(1.7320508075688772))) v8 = v1*v2 v9 = v8 - v3*v5 si = v8*v5 AA.polynomial_root(AA.common_polynomial(x1^4 + (v6 + v7)*x1^3 + (v9 + v6*v7)*x1^2 + (-si + v9*v7)*x1 - si*v7), RIF(RR(0.99999999999999989), RR(1.0000000000000002))) sage: one 1
We can pickle and unpickle algebraic fields (and they are globally unique)::
sage: loads(dumps(AlgebraicField())) is AlgebraicField() True sage: loads(dumps(AlgebraicRealField())) is AlgebraicRealField() True
We can pickle and unpickle algebraic numbers::
sage: loads(dumps(QQbar(10))) == QQbar(10) True sage: loads(dumps(QQbar(5/2))) == QQbar(5/2) True sage: loads(dumps(QQbar.zeta(5))) == QQbar.zeta(5) True
sage: t = QQbar(sqrt(2)); type(t._descr) <class 'sage.rings.qqbar.ANRoot'> sage: loads(dumps(t)) == QQbar(sqrt(2)) True
sage: t.exactify(); type(t._descr) <class 'sage.rings.qqbar.ANExtensionElement'> sage: loads(dumps(t)) == QQbar(sqrt(2)) True
sage: t = ~QQbar(sqrt(2)); type(t._descr) <class 'sage.rings.qqbar.ANUnaryExpr'> sage: loads(dumps(t)) == 1/QQbar(sqrt(2)) True
sage: t = QQbar(sqrt(2)) + QQbar(sqrt(3)); type(t._descr) <class 'sage.rings.qqbar.ANBinaryExpr'> sage: loads(dumps(t)) == QQbar(sqrt(2)) + QQbar(sqrt(3)) True
We can convert elements of ``QQbar`` and ``AA`` into the following types: ``float``, ``complex``, ``RDF``, ``CDF``, ``RR``, ``CC``, ``RIF``, ``CIF``, ``ZZ``, and ``QQ``, with a few exceptions. (For the arbitrary-precision types, ``RR``, ``CC``, ``RIF``, and ``CIF``, it can convert into a field of arbitrary precision.)
Converting from ``QQbar`` to a real type (``float``, ``RDF``, ``RR``, ``RIF``, ``ZZ``, or ``QQ``) succeeds only if the ``QQbar`` is actually real (has an imaginary component of exactly zero). Converting from either ``AA`` or ``QQbar`` to ``ZZ`` or ``QQ`` succeeds only if the number actually is an integer or rational. If conversion fails, a ValueError will be raised.
Here are examples of all of these conversions::
sage: all_vals = [AA(42), AA(22/7), AA(golden_ratio), QQbar(-13), QQbar(89/55), QQbar(-sqrt(7)), QQbar.zeta(5)] sage: def convert_test_all(ty): ....: def convert_test(v): ....: try: ....: return ty(v) ....: except (TypeError, ValueError): ....: return None ....: return [convert_test(_) for _ in all_vals] sage: convert_test_all(float) [42.0, 3.1428571428571432, 1.618033988749895, -13.0, 1.6181818181818182, -2.6457513110645907, None] sage: convert_test_all(complex) [(42+0j), (3.1428571428571432+0j), (1.618033988749895+0j), (-13+0j), (1.6181818181818182+0j), (-2.6457513110645907+0j), (0.30901699437494745+0.9510565162951536j)] sage: convert_test_all(RDF) [42.0, 3.1428571428571432, 1.618033988749895, -13.0, 1.6181818181818182, -2.6457513110645907, None] sage: convert_test_all(CDF) [42.0, 3.1428571428571432, 1.618033988749895, -13.0, 1.6181818181818182, -2.6457513110645907, 0.30901699437494745 + 0.9510565162951536*I] sage: convert_test_all(RR) [42.0000000000000, 3.14285714285714, 1.61803398874989, -13.0000000000000, 1.61818181818182, -2.64575131106459, None] sage: convert_test_all(CC) [42.0000000000000, 3.14285714285714, 1.61803398874989, -13.0000000000000, 1.61818181818182, -2.64575131106459, 0.309016994374947 + 0.951056516295154*I] sage: convert_test_all(RIF) [42, 3.142857142857143?, 1.618033988749895?, -13, 1.618181818181819?, -2.645751311064591?, None] sage: convert_test_all(CIF) [42, 3.142857142857143?, 1.618033988749895?, -13, 1.618181818181819?, -2.645751311064591?, 0.3090169943749474? + 0.9510565162951536?*I] sage: convert_test_all(ZZ) [42, None, None, -13, None, None, None] sage: convert_test_all(QQ) [42, 22/7, None, -13, 89/55, None, None]
Compute the exact coordinates of a 34-gon (the formulas used are from Weisstein, Eric W. "Trigonometry Angles--Pi/17." and can be found at http://mathworld.wolfram.com/TrigonometryAnglesPi17.html)::
sage: rt17 = AA(17).sqrt() sage: rt2 = AA(2).sqrt() sage: eps = (17 + rt17).sqrt() sage: epss = (17 - rt17).sqrt() sage: delta = rt17 - 1 sage: alpha = (34 + 6*rt17 + rt2*delta*epss - 8*rt2*eps).sqrt() sage: beta = 2*(17 + 3*rt17 - 2*rt2*eps - rt2*epss).sqrt() sage: x = rt2*(15 + rt17 + rt2*(alpha + epss)).sqrt()/8 sage: y = rt2*(epss**2 - rt2*(alpha + epss)).sqrt()/8
sage: cx, cy = 1, 0 sage: for i in range(34): ....: cx, cy = x*cx-y*cy, x*cy+y*cx sage: cx 1.000000000000000? sage: cy 0.?e-15
sage: ax = polygen(AA) sage: x2 = AA.polynomial_root(256*ax**8 - 128*ax**7 - 448*ax**6 + 192*ax**5 + 240*ax**4 - 80*ax**3 - 40*ax**2 + 8*ax + 1, RIF(0.9829, 0.983)) sage: y2 = (1-x2**2).sqrt() sage: x - x2 0.?e-18 sage: y - y2 0.?e-17
Ideally, in the above example we should be able to test ``x == x2`` and ``y == y2`` but this is currently infinitely long.
TESTS:
Verify that :trac:`10981` is fixed::
sage: x = AA['x'].gen() sage: P = 1/(1+x^4) sage: P.partial_fraction_decomposition() (0, [(-0.3535533905932738?*x + 1/2)/(x^2 - 1.414213562373095?*x + 1), (0.3535533905932738?*x + 1/2)/(x^2 + 1.414213562373095?*x + 1)])
Check that :trac:`22202` is fixed::
sage: R1.<x> = AA[]; R2.<s> = QQbar[] sage: v = QQbar.polynomial_root(x^2 - x + 1, CIF(0.5, RIF(-0.87, -0.85))) sage: a = QQbar.polynomial_root((-4*v + 2)*s + (v - 1/2), CIF(RIF(0.24, 0.26), RIF(0))) sage: QQ(a) 1/4 """
from __future__ import absolute_import, print_function, division from six.moves import range from six import integer_types, iteritems
import itertools import operator
import sage.rings.ring from sage.misc.fast_methods import Singleton from sage.misc.cachefunc import cached_method from sage.structure.sage_object import SageObject from sage.structure.richcmp import (richcmp, richcmp_method, rich_to_bool, richcmp_not_equal, op_EQ, op_NE) from sage.rings.real_mpfr import RR from sage.rings.real_mpfi import RealIntervalField, RIF, is_RealIntervalFieldElement, RealIntervalField_class from sage.rings.complex_field import ComplexField from sage.rings.complex_interval_field import ComplexIntervalField, is_ComplexIntervalField from sage.rings.complex_interval import is_ComplexIntervalFieldElement from sage.rings.polynomial.all import PolynomialRing from sage.rings.polynomial.polynomial_element import is_Polynomial from sage.rings.integer_ring import ZZ from sage.rings.rational_field import QQ from sage.rings.number_field.number_field import NumberField, QuadraticField, CyclotomicField from sage.rings.number_field.number_field_element_quadratic import NumberFieldElement_quadratic from sage.arith.all import factor from . import infinity from sage.categories.action import Action
CC = ComplexField() CIF = ComplexIntervalField()
class AlgebraicField_common(sage.rings.ring.Field): r""" Common base class for the classes :class:`~AlgebraicRealField` and :class:`~AlgebraicField`. """
def default_interval_prec(self): r""" Return the default interval precision used for root isolation.
EXAMPLES::
sage: AA.default_interval_prec() 64 """
def is_finite(self): r""" Check whether this field is finite. Since this class is only used for fields of characteristic 0, always returns False.
EXAMPLES::
sage: QQbar.is_finite() False """
def characteristic(self): r""" Return the characteristic of this field. Since this class is only used for fields of characteristic 0, always returns 0.
EXAMPLES::
sage: AA.characteristic() 0 """
def order(self): r""" Return the cardinality of self. Since this class is only used for fields of characteristic 0, always returns Infinity.
EXAMPLES::
sage: QQbar.order() +Infinity """
def common_polynomial(self, poly): """ Given a polynomial with algebraic coefficients, returns a wrapper that caches high-precision calculations and factorizations. This wrapper can be passed to polynomial_root in place of the polynomial.
Using ``common_polynomial`` makes no semantic difference, but will improve efficiency if you are dealing with multiple roots of a single polynomial.
EXAMPLES::
sage: x = polygen(ZZ) sage: p = AA.common_polynomial(x^2 - x - 1) sage: phi = AA.polynomial_root(p, RIF(1, 2)) sage: tau = AA.polynomial_root(p, RIF(-1, 0)) sage: phi + tau == 1 True sage: phi * tau == -1 True
sage: x = polygen(SR) sage: p = (x - sqrt(-5)) * (x - sqrt(3)); p x^2 + (-sqrt(3) - sqrt(-5))*x + sqrt(3)*sqrt(-5) sage: p = QQbar.common_polynomial(p) sage: a = QQbar.polynomial_root(p, CIF(RIF(-0.1, 0.1), RIF(2, 3))); a 0.?e-18 + 2.236067977499790?*I sage: b = QQbar.polynomial_root(p, RIF(1, 2)); b 1.732050807568878?
These "common polynomials" can be shared between real and complex roots::
sage: p = AA.common_polynomial(x^3 - x - 1) sage: r1 = AA.polynomial_root(p, RIF(1.3, 1.4)); r1 1.324717957244746? sage: r2 = QQbar.polynomial_root(p, CIF(RIF(-0.7, -0.6), RIF(0.5, 0.6))); r2 -0.6623589786223730? + 0.5622795120623013?*I """
def _get_action_(self, G, op, self_on_left): """ EXAMPLES::
sage: QQbar.get_action(QQ, operator.pow) Right Rational Powering by Rational Field on Algebraic Field sage: print(QQbar.get_action(QQ, operator.pow, self_on_left=False)) None sage: print(QQbar.get_action(QQ, operator.mul)) None sage: QQbar.get_action(ZZ, operator.pow) Right Integer Powering by Integer Ring on Algebraic Field """
class AlgebraicRealField(Singleton, AlgebraicField_common): r""" The field of algebraic reals.
TESTS::
sage: AA == loads(dumps(AA)) True """
def __new__(cls): r""" This method is there to ensure that pickles created before this class was made a :class:`~sage.misc.fast_methods.Singleton` still load.
TESTS::
sage: s = loads(b'x\x9cmQ\xcbR\x141\x14\xad\x11A\x083\xe2\x03T|' ....: b'\x82l`\xd3\xff\xe0\x86\x8de/\xba*\xcb\xa9[\xe9\xf4' ....: b'\xa5;e:=\'I+,\xa6J\x17B\xf9\xd7f\x08\xe2s\x95\xa4\xee9\xf7<' ....: b'\xf2\xe5\x8e\x0e\xaa\xe5"D?\xea8z.\x9a\x0b\xa7z\xa3I[\x15' ....: b'\x82\xf8\xf3\x85\xc9\xb1<xg[\xae\xbd2\xbabeO\r\xdb\x86>\x9b' ....: b'\xd8\x91V\x91\xdb\xc1_\xe0f\xa57\xae\r\x05P+/\xfe\xe5\x08' ....: b'\xaci\xa2z46\x1aG$Z\x8e*F/p\xf7oC\xa33\x18\x99</<\x07v\tf' ....: b'\x06\'F\xe7\xb9\x195\x0b\xacg\xc2\x8d\xbc\xe1P\x9c\xad\x04' ....: b'\x828\xcd\x076N\x96W\xb8WaSN\x17\xca\xa7\r9\r\xb6.+\x88Kl' ....: b'\x97e\xb7\x16+LO\xbeb\xb6\xc4\xfdc)\x88\xfb\x9a\x9b&\x05' ....: b'\xc0N)wI\x0f\xee\x13\xfbH=\xc7nh(U\xc2xP\xca\r\xd2\x8d' ....: b'\x8a\n\x0fK\xb9\xf5+\xfe\xa3n3MV\x98\x80\xc7rr\xfe\r\xbbr' ....: b'\x9bZv\xecU\x1c|\xc0\xde\x12O\xe4:\xd5*0\x9ev3\xb9C\x0b' ....: b'\xa3?Z\xa6\xa4\x11R6<{?I\xa2l\xb9\xbf6;\xb8\\\xc6\xe0\xb1' ....: b'\x9f\xb3\xf6&\xe8\xe2,\xb3R\x13\xf9\xf2\xe1\xda\x9c\xc0s' ....: b'\xb9\xf7?.\xe1E7\xeb\xa6W\x15^&\x80q&\x1aeo\x93Y\x13"^\xcd' ....: b'\xf1Z\xee\xdf\x92W\x18Z\xa4\xa6(\xd7\x867\xdf\x93\xad\x9fL' ....: b'\xa5W\xff\x90\x89\x07s\x1c\xfe6\xd2\x03{\xcdy\xf4v\x8e\xa3' ....: b'\xb1.~\x000\xc2\xe0\xa1') sage: s is AA True
""" except BaseException: return AlgebraicField_common.__new__(cls)
def __init__(self): r""" Standard initialization function.
EXAMPLES:
This function calls functions in superclasses which set the category, so we check that.
sage: QQbar.category() # indirect doctest Category of fields """ AlgebraicField_common.__init__(self, self, ('x',), normalize=False)
def _element_constructor_(self, x): r""" Construct an element of the field of algebraic real numbers from ``x``.
EXAMPLES::
sage: QQbar(sqrt(2)) in AA # indirect doctest True sage: QQbar(I) in AA False sage: AA in AA False
The following should both return True (this is a bug). ::
sage: sqrt(2) in AA # not tested False sage: K.<z> = CyclotomicField(5); z + 1/z in AA # not tested False """ return x else:
def _repr_(self): r""" String representation of self.
EXAMPLES::
sage: AA._repr_() 'Algebraic Real Field' """
def _repr_option(self, key): """ Metadata about the :meth:`_repr_` output.
See :meth:`sage.structure.parent._repr_option` for details.
EXAMPLES::
sage: AA._repr_option('element_is_atomic') True """
# Is there a standard representation for this? def _latex_(self): r""" Latex representation of self.
EXAMPLES::
sage: AA._latex_() '\\mathbf{A}' """
def _sage_input_(self, sib, coerce): r""" Produce an expression which will reproduce this value when evaluated.
EXAMPLES::
sage: sage_input(AA, verify=True) # Verified AA sage: from sage.misc.sage_input import SageInputBuilder sage: AA._sage_input_(SageInputBuilder(), False) {atomic:AA} """
def _coerce_map_from_(self, from_par): r""" Set up the coercion model.
TESTS::
sage: AA.has_coerce_map_from(ZZ) # indirect doctest True sage: K.<a> = QuadraticField(7, embedding=AA(7).sqrt()); AA.has_coerce_map_from(K) True sage: a in AA True sage: a + AA(3) 5.645751311064590? sage: AA.has_coerce_map_from(SR) False """ or from_par is AA)
def completion(self, p, prec, extras = {}): r""" Return the completion of self at the place `p`. Only implemented for `p = \infty` at present.
INPUT:
- ``p`` -- either a prime (not implemented at present) or Infinity - ``prec`` -- precision of approximate field to return - ``extras`` -- a dict of extra keyword arguments for the ``RealField`` constructor
EXAMPLES::
sage: AA.completion(infinity, 500) Real Field with 500 bits of precision sage: AA.completion(infinity, prec=53, extras={'type':'RDF'}) Real Double Field sage: AA.completion(infinity, 53) is RR True sage: AA.completion(7, 10) Traceback (most recent call last): ... NotImplementedError """ else:
def algebraic_closure(self): """ Return the algebraic closure of this field, which is the field `\overline{\QQ}` of algebraic numbers.
EXAMPLES::
sage: AA.algebraic_closure() Algebraic Field """
def _is_valid_homomorphism_(self, codomain, im_gens): r""" Attempt to construct a homomorphism from self to codomain sending the generators to ``im_gens``. Since this field is not finitely generated, this cannot be implemented in a mathematically sensible way, and we just test that there exists a canonical coercion.
EXAMPLES::
sage: AA._is_valid_homomorphism_(QQbar, [QQbar(1)]) True sage: AA._is_valid_homomorphism_(QQ, [QQ(1)]) False """
def gens(self): r""" Return a set of generators for this field. As this field is not finitely generated, we opt for just returning 1.
EXAMPLES::
sage: AA.gens() (1,) """
def gen(self, n=0): r""" Return the `n`-th element of the tuple returned by :meth:`gens`.
EXAMPLES::
sage: AA.gen(0) 1 sage: AA.gen(1) Traceback (most recent call last): ... IndexError: n must be 0 """ else:
def ngens(self): r""" Return the size of the tuple returned by :meth:`gens`.
EXAMPLES::
sage: AA.ngens() 1 """
def zeta(self, n=2): r""" Return an `n`-th root of unity in this field. This will raise a ``ValueError`` if `n \ne \{1, 2\}` since no such root exists.
INPUT:
- ``n`` (integer) -- default 2
EXAMPLES::
sage: AA.zeta(1) 1 sage: AA.zeta(2) -1 sage: AA.zeta() -1 sage: AA.zeta(3) Traceback (most recent call last): ... ValueError: no n-th root of unity in algebraic reals
Some silly inputs::
sage: AA.zeta(Mod(-5, 7)) -1 sage: AA.zeta(0) Traceback (most recent call last): ... ValueError: no n-th root of unity in algebraic reals """ else:
def polynomial_root(self, poly, interval, multiplicity=1): r""" Given a polynomial with algebraic coefficients and an interval enclosing exactly one root of the polynomial, constructs an algebraic real representation of that root.
The polynomial need not be irreducible, or even squarefree; but if the given root is a multiple root, its multiplicity must be specified. (IMPORTANT NOTE: Currently, multiplicity-`k` roots are handled by taking the `(k-1)`-st derivative of the polynomial. This means that the interval must enclose exactly one root of this derivative.)
The conditions on the arguments (that the interval encloses exactly one root, and that multiple roots match the given multiplicity) are not checked; if they are not satisfied, an error may be thrown (possibly later, when the algebraic number is used), or wrong answers may result.
Note that if you are constructing multiple roots of a single polynomial, it is better to use ``AA.common_polynomial`` (or ``QQbar.common_polynomial``; the two are equivalent) to get a shared polynomial.
EXAMPLES::
sage: x = polygen(AA) sage: phi = AA.polynomial_root(x^2 - x - 1, RIF(1, 2)); phi 1.618033988749895? sage: p = (x-1)^7 * (x-2) sage: r = AA.polynomial_root(p, RIF(9/10, 11/10), multiplicity=7) sage: r; r == 1 1.000000000000000? True sage: p = (x-phi)*(x-sqrt(AA(2))) sage: r = AA.polynomial_root(p, RIF(1, 3/2)) sage: r; r == sqrt(AA(2)) 1.414213562373095? True
We allow complex polynomials, as long as the particular root in question is real. ::
sage: K.<im> = QQ[I] sage: x = polygen(K) sage: p = (im + 1) * (x^3 - 2); p (I + 1)*x^3 - 2*I - 2 sage: r = AA.polynomial_root(p, RIF(1, 2)); r^3 2.000000000000000? """ raise ValueError("interval argument of .polynomial_root on algebraic real field must be real")
def _factor_univariate_polynomial(self, f): """ Factor the univariate polynomial ``f``.
INPUT:
- ``f`` -- a univariate polynomial defined over the real algebraic field
OUTPUT:
- A factorization of ``f`` over the real algebraic numbers into a unit and monic irreducible factors
.. NOTE::
This is a helper method for :meth:`sage.rings.polynomial.polynomial_element.Polynomial.factor`.
TESTS::
sage: R.<x> = AA[] sage: AA._factor_univariate_polynomial(x) x sage: AA._factor_univariate_polynomial(2*x) (2) * x sage: AA._factor_univariate_polynomial((x^2 + 1)^2) (x^2 + 1)^2 sage: AA._factor_univariate_polynomial(x^8 + 1) (x^2 - 1.847759065022574?*x + 1.000000000000000?) * (x^2 - 0.7653668647301795?*x + 1.000000000000000?) * (x^2 + 0.7653668647301795?*x + 1.000000000000000?) * (x^2 + 1.847759065022574?*x + 1.000000000000000?) sage: AA._factor_univariate_polynomial(R(3)) 3 sage: AA._factor_univariate_polynomial(12*x^2 - 4) (12) * (x - 0.5773502691896258?) * (x + 0.5773502691896258?) sage: AA._factor_univariate_polynomial(12*x^2 + 4) (12) * (x^2 + 0.3333333333333334?) sage: AA._factor_univariate_polynomial(EllipticCurve('11a1').change_ring(AA).division_polynomial(5)) (5) * (x - 16.00000000000000?) * (x - 5.000000000000000?) * (x - 1.959674775249769?) * (x + 2.959674775249769?) * (x^2 - 2.854101966249685?*x + 15.47213595499958?) * (x^2 + 1.909830056250526?*x + 1.660606461254312?) * (x^2 + 3.854101966249685?*x + 6.527864045000421?) * (x^2 + 13.09016994374948?*x + 93.33939353874569?)
"""
[(f.parent()([-r,1]),e) for r,e in rr] + [(f.parent()([r.norm(),-2*r.real(),1]),e) for r,e in cr], unit=f.leading_coefficient())
def is_AlgebraicRealField(F): r""" Check whether ``F`` is an :class:`~AlgebraicRealField` instance. For internal use.
EXAMPLES::
sage: from sage.rings.qqbar import is_AlgebraicRealField sage: [is_AlgebraicRealField(x) for x in [AA, QQbar, None, 0, "spam"]] [True, False, False, False, False] """
# Create the globally unique AlgebraicRealField object. AA = AlgebraicRealField()
class AlgebraicField(Singleton, AlgebraicField_common): """ The field of all algebraic complex numbers. """
def __new__(cls): r""" This method is there to ensure that pickles created before this class was made a :class:`~sage.misc.fast_methods.Singleton` still load.
TESTS::
sage: s = loads(b'x\x9c}RMo\x131\x10U(-\xad\x9b\x92\x16ZJh\x80~' ....: b'\x00MZX~\x03\x97J\x08\xb1\x87H>F\x96\xd7;\xdd\xb1\xd8x3\xb6' ....: b'\x17\xe8!\x12\x1c\xda\xaa\xff\x9aI\xb7\x04\x8a*N\xb65\xef' ....: b'\xcd\xbc\xf7\xc6?\xee\x99\xa0\x0bHB\xf4\xb5\x89\xb5' ....: b'\x87$?szl\x8d2\xa5\x0eA\xdc~Q\xab/{\x1f\xca\x022\xaf\xad9' ....: b'\xb1P\xe6\xea\x9b\x8d\xa8\x8c\x8ePT\xfe\x8cn\xday\xeb\x8a' ....: b'\x90\x10e\xda\x8b\xdbxA\x0bF\xa9\xac\xb6e\xb4N)Q@\xd41zA' ....: b'\xf7\xff\x15R;K5(\x0f\x13\x0f\x01\x1c\xc3l\xe5D\xed<\xe4' ....: b'\xb5\x01A\x8b\r\xe1f\xb4\x85\x90\x9c\xce\x06\x04q\xd2\x1c' ....: b'\xb44\x98^\xd2\x83!-\xcb\xf6D{\xee\xd0\xb8\xa0\x95\x8b!\x89' ....: b'\x0bZMS\\\x88Cj\x0f~\xd2\xda\x94\x1e\xf6\xa5P0\xce \xcfY<uR' ....: b'\xb9\xa9L\xe5\xbe\x82\x8fj\x0c\x11\xab\\q\x14@\xeb\xa9\\R&' ....: b'\xd7Q\xd3F*W\xfeX\x7f\x84\xcb\\\x99a\x02=\x96\xad\x8f\xe7' ....: b'\xb4)WU\x01\x0e\xbc\x8e\x95\x0f\xb45\xa5\'rQe:\x00m#G\xb9;' ....: b'\x8ff\x08\xba\xbc+\xce\xa7\xff\x89s\xce\x11\xd4E\xf6\xf3' ....: b'\x8c\xfdt\xd9\xcf\x0e\xfb\xe9M\xe9y\x1f;)\xae\xa7\xb8' ....: b'\x91"KC\x96\xf4\xfd\x9c^ \xabx\x89\xdb\xd8\x93\x1d5\xb1' ....: b'\xe6K\t\x8a-\x06\x8e\x96v?\xb5\xd83\x940\xbe\xce\xaar' ....: b'\xcd.*O{\x8d\x8c\xb1\r&9mX\xbc\x88\xe6\xf2\xf9:\x1bA\xfbr' ....: b'\xeb.\xae\xa2\x03\xec\xe1\xce\xe5\x90^1\xc0:\x1b\xad.\xe7' ....: b'\xc1\x966Dz=\xa27\xb2;\'\xcf0j\xc2\x8bR\xcd\xd6\xe8\xf0' ....: b'\x8ae\xfdfj3\xfb\x06\r\xb1?\xa2\xc1_%S\x817\xd0\x94' ....: b'\x8eFt\\g\xc8\x96p\x0f\xf7\xf1\x00\xd7\xb0\xcd\x1a\xde"' ....: b'\x0f{\x87\x87W\xc8\xdc\x04\x19\xf5\xbe\xce\x92_p\'\x13\xc5') sage: s is QQbar True """ except BaseException: return AlgebraicField_common.__new__(cls)
def __init__(self): r""" Standard init function.
We test by setting the category::
sage: QQbar.category() # indirect doctest Category of fields sage: QQbar.base_ring() Algebraic Real Field
TESTS::
sage: QQbar._repr_option('element_is_atomic') False """ AlgebraicField_common.__init__(self, AA, ('I',), normalize=False)
def _element_constructor_(self, x): """ Try to construct an element of the field of algebraic numbers from `x`.
EXAMPLES::
sage: sqrt(2) in QQbar # indirect doctest True sage: 22/7 in QQbar True sage: pi in QQbar False """ return x
def _repr_(self): r""" String representation of self.
EXAMPLES::
sage: QQbar._repr_() 'Algebraic Field' """
def _latex_(self): r""" Latex representation of self.
EXAMPLES::
sage: QQbar._latex_() '\\overline{\\QQ}' """
def _sage_input_(self, sib, coerce): r""" Produce an expression which will reproduce this value when evaluated.
EXAMPLES::
sage: sage_input(QQbar, verify=True) # Verified QQbar sage: from sage.misc.sage_input import SageInputBuilder sage: QQbar._sage_input_(SageInputBuilder(), False) {atomic:QQbar} """
def _coerce_map_from_(self, from_par): r""" Set up the coercion model.
TESTS::
sage: QQbar.has_coerce_map_from(ZZ) # indirect doctest True sage: QQbar.has_coerce_map_from(AA) True sage: QQbar.has_coerce_map_from(CC) False sage: QQbar.has_coerce_map_from(SR) False """ or from_par is AA or from_par is QQbar)
def completion(self, p, prec, extras = {}): r""" Return the completion of self at the place `p`. Only implemented for `p = \infty` at present.
INPUT:
- ``p`` -- either a prime (not implemented at present) or Infinity - ``prec`` -- precision of approximate field to return - ``extras`` -- a dict of extra keyword arguments for the ``RealField`` constructor
EXAMPLES::
sage: QQbar.completion(infinity, 500) Complex Field with 500 bits of precision sage: QQbar.completion(infinity, prec=53, extras={'type':'RDF'}) Complex Double Field sage: QQbar.completion(infinity, 53) is CC True sage: QQbar.completion(3, 20) Traceback (most recent call last): ... NotImplementedError """ else:
def algebraic_closure(self): """ Return the algebraic closure of this field. As this field is already algebraically closed, just returns self.
EXAMPLES::
sage: QQbar.algebraic_closure() Algebraic Field """
def construction(self): """ Return a functor that constructs self (used by the coercion machinery).
EXAMPLES::
sage: QQbar.construction() (AlgebraicClosureFunctor, Rational Field) """
def gens(self): r""" Return a set of generators for this field. As this field is not finitely generated over its prime field, we opt for just returning I.
EXAMPLES::
sage: QQbar.gens() (I,) """
def gen(self, n=0): r""" Return the `n`-th element of the tuple returned by :meth:`gens`.
EXAMPLES::
sage: QQbar.gen(0) I sage: QQbar.gen(1) Traceback (most recent call last): ... IndexError: n must be 0 """ else:
def ngens(self): r""" Return the size of the tuple returned by :meth:`gens`.
EXAMPLES::
sage: QQbar.ngens() 1 """
@cached_method def zeta(self, n=4): r""" Returns a primitive `n`'th root of unity, specifically `\exp(2*\pi*i/n)`.
INPUT:
- ``n`` (integer) -- default 4
EXAMPLES::
sage: QQbar.zeta(1) 1 sage: QQbar.zeta(2) -1 sage: QQbar.zeta(3) -0.500000000000000? + 0.866025403784439?*I sage: QQbar.zeta(4) I sage: QQbar.zeta() I sage: QQbar.zeta(5) 0.3090169943749474? + 0.9510565162951536?*I sage: QQbar.zeta(3000) 0.999997806755380? + 0.002094393571219374?*I """ else:
def polynomial_root(self, poly, interval, multiplicity=1): r""" Given a polynomial with algebraic coefficients and an interval enclosing exactly one root of the polynomial, constructs an algebraic real representation of that root.
The polynomial need not be irreducible, or even squarefree; but if the given root is a multiple root, its multiplicity must be specified. (IMPORTANT NOTE: Currently, multiplicity-`k` roots are handled by taking the `(k-1)`-st derivative of the polynomial. This means that the interval must enclose exactly one root of this derivative.)
The conditions on the arguments (that the interval encloses exactly one root, and that multiple roots match the given multiplicity) are not checked; if they are not satisfied, an error may be thrown (possibly later, when the algebraic number is used), or wrong answers may result.
Note that if you are constructing multiple roots of a single polynomial, it is better to use ``QQbar.common_polynomial`` to get a shared polynomial.
EXAMPLES::
sage: x = polygen(QQbar) sage: phi = QQbar.polynomial_root(x^2 - x - 1, RIF(0, 2)); phi 1.618033988749895? sage: p = (x-1)^7 * (x-2) sage: r = QQbar.polynomial_root(p, RIF(9/10, 11/10), multiplicity=7) sage: r; r == 1 1 True sage: p = (x-phi)*(x-sqrt(QQbar(2))) sage: r = QQbar.polynomial_root(p, RIF(1, 3/2)) sage: r; r == sqrt(QQbar(2)) 1.414213562373095? True """
def random_element(self, poly_degree=2, *args, **kwds): r""" Returns a random algebraic number.
INPUT:
- ``poly_degree`` - default: 2 - degree of the random polynomial over the integers of which the returned algebraic number is a root. This is not necessarily the degree of the minimal polynomial of the number. Increase this parameter to achieve a greater diversity of algebraic numbers, at a cost of greater computation time. You can also vary the distribution of the coefficients but that will not vary the degree of the extension containing the element.
- ``args``, ``kwds`` - arguments and keywords passed to the random number generator for elements of ``ZZ``, the integers. See :meth:`~sage.rings.integer_ring.IntegerRing_class.random_element` for details, or see example below.
OUTPUT:
An element of ``QQbar``, the field of algebraic numbers (see :mod:`sage.rings.qqbar`).
ALGORITHM:
A polynomial with degree between 1 and ``poly_degree``, with random integer coefficients is created. A root of this polynomial is chosen at random. The default degree is 2 and the integer coefficients come from a distribution heavily weighted towards `0, \pm 1, \pm 2`.
EXAMPLES::
sage: a = QQbar.random_element() sage: a # random 0.2626138748742799? + 0.8769062830975992?*I sage: a in QQbar True
sage: b = QQbar.random_element(poly_degree=20) sage: b # random -0.8642649077479498? - 0.5995098147478391?*I sage: b in QQbar True
Parameters for the distribution of the integer coefficients of the polynomials can be passed on to the random element method for integers. For example, current default behavior of this method returns zero about 15% of the time; if we do not include zero as a possible coefficient, there will never be a zero constant term, and thus never a zero root. ::
sage: z = [QQbar.random_element(x=1, y=10) for _ in range(20)] sage: QQbar(0) in z False
If you just want real algebraic numbers you can filter them out. Using an odd degree for the polynomials will insure some degree of success. ::
sage: r = [] sage: while len(r) < 3: ....: x = QQbar.random_element(poly_degree=3) ....: if x in AA: ....: r.append(x) sage: (len(r) == 3) and all([z in AA for z in r]) True
TESTS:
sage: QQbar.random_element('junk') Traceback (most recent call last): ... TypeError: polynomial degree must be an integer, not junk sage: QQbar.random_element(poly_degree=0) Traceback (most recent call last): ... ValueError: polynomial degree must be greater than zero, not 0
Random vectors already have a 'degree' keyword, so we cannot use that for the polynomial's degree. ::
sage: v = random_vector(QQbar, degree=2, poly_degree=3) sage: v # random (0.4694381338921299?, -0.500000000000000? + 0.866025403784439?*I) """ # degree zero polynomials have no roots # totally zero poly has degree -1 # add a random leading term g = R.gen(0) m = sage.misc.prandom.randint(1, poly_degree) p = p + g**m
# p will have at least one root; pick one at random # could we instead just compute one root "randomly"?
def _is_irreducible_univariate_polynomial(self, f): r""" Return whether ``f`` is irreducible.
INPUT:
- ``f`` -- a non-constant univariate polynomial defined over the algebraic field
.. NOTE::
This is a helper method for :meth:`sage.rings.polynomial.polynomial_element.Polynomial.is_irreducible`.
EXAMPLES::
sage: R.<x> = QQbar[] sage: (x^2).is_irreducible() # indirect doctest False
Note that this method does not handle constant polynomials::
sage: QQbar._is_irreducible_univariate_polynomial(R(1)) Traceback (most recent call last): ... ValueError: polynomial must not be constant sage: R(1).is_irreducible() False
""" # this case is handled by the caller (PolynomialElement.is_irreducible())
def _factor_univariate_polynomial(self, f): """ Factor the univariate polynomial ``f``.
INPUT:
- ``f`` -- a univariate polynomial defined over the algebraic field
OUTPUT:
- A factorization of ``f`` over the algebraic numbers into a unit and monic irreducible factors
.. NOTE::
This is a helper method for :meth:`sage.rings.polynomial.polynomial_element.Polynomial.factor`.
TESTS::
sage: R.<x> = QQbar[] sage: QQbar._factor_univariate_polynomial(x) x sage: QQbar._factor_univariate_polynomial(2*x) (2) * x sage: QQbar._factor_univariate_polynomial((x^2 + 1)^2) (x - I)^2 * (x + I)^2 sage: QQbar._factor_univariate_polynomial(x^8 - 1) (x - 1) * (x - 0.7071067811865475? - 0.7071067811865475?*I) * (x - 0.7071067811865475? + 0.7071067811865475?*I) * (x - I) * (x + I) * (x + 0.7071067811865475? - 0.7071067811865475?*I) * (x + 0.7071067811865475? + 0.7071067811865475?*I) * (x + 1) sage: QQbar._factor_univariate_polynomial(12*x^2 - 4) (12) * (x - 0.5773502691896258?) * (x + 0.5773502691896258?) sage: QQbar._factor_univariate_polynomial(R(-1)) -1 sage: QQbar._factor_univariate_polynomial(EllipticCurve('11a1').change_ring(QQbar).division_polynomial(5)) (5) * (x - 16) * (x - 5) * (x - 1.959674775249769?) * (x - 1.427050983124843? - 3.665468789467727?*I) * (x - 1.427050983124843? + 3.665468789467727?*I) * (x + 0.9549150281252629? - 0.8652998037182486?*I) * (x + 0.9549150281252629? + 0.8652998037182486?*I) * (x + 1.927050983124843? - 1.677599044300515?*I) * (x + 1.927050983124843? + 1.677599044300515?*I) * (x + 2.959674775249769?) * (x + 6.545084971874737? - 7.106423590645660?*I) * (x + 6.545084971874737? + 7.106423590645660?*I)
"""
def is_AlgebraicField(F): r""" Check whether ``F`` is an :class:`~AlgebraicField` instance.
EXAMPLES::
sage: from sage.rings.qqbar import is_AlgebraicField sage: [is_AlgebraicField(x) for x in [AA, QQbar, None, 0, "spam"]] [False, True, False, False, False] """
# Create the globally unique AlgebraicField object. QQbar = AlgebraicField()
def is_AlgebraicField_common(F): r""" Check whether ``F`` is an :class:`~AlgebraicField_common` instance.
EXAMPLES::
sage: from sage.rings.qqbar import is_AlgebraicField_common sage: [is_AlgebraicField_common(x) for x in [AA, QQbar, None, 0, "spam"]] [True, True, False, False, False] """
def prec_seq(): r""" Return a generator object which iterates over an infinite increasing sequence of precisions to be tried in various numerical computations.
Currently just returns powers of 2 starting at 64.
EXAMPLES::
sage: g = sage.rings.qqbar.prec_seq() sage: [next(g), next(g), next(g)] [64, 128, 256] """ # XXX Should do some testing to see where the efficiency breaks are # in MPFR. We could also test variants like "bits = bits + bits // 2" # (I think this is what MPFR uses internally).
_short_prec_seq = (64, 128, None) def short_prec_seq(): r""" Return a sequence of precisions to try in cases when an infinite-precision computation is possible: returns a couple of small powers of 2 and then ``None``.
EXAMPLES::
sage: from sage.rings.qqbar import short_prec_seq sage: short_prec_seq() (64, 128, None) """
def tail_prec_seq(): r""" A generator over precisions larger than those in :func:`~short_prec_seq`.
EXAMPLES::
sage: from sage.rings.qqbar import tail_prec_seq sage: g = tail_prec_seq() sage: [next(g), next(g), next(g)] [256, 512, 1024] """
def rational_exact_root(r, d): r""" Checks whether the rational `r` is an exact `d`'th power. If so, returns the `d`'th root of `r`; otherwise, returns None.
EXAMPLES::
sage: from sage.rings.qqbar import rational_exact_root sage: rational_exact_root(16/81, 4) 2/3 sage: rational_exact_root(8/81, 3) is None True """
def clear_denominators(poly): """ Takes a monic polynomial and rescales the variable to get a monic polynomial with "integral" coefficients. Works on any univariate polynomial whose base ring has a ``denominator()`` method that returns integers; for example, the base ring might be `\QQ` or a number field.
Returns the scale factor and the new polynomial.
(Inspired by Pari's ``primitive_pol_to_monic()``.)
We assume that coefficient denominators are "small"; the algorithm factors the denominators, to give the smallest possible scale factor.
EXAMPLES::
sage: from sage.rings.qqbar import clear_denominators
sage: _.<x> = QQ['x'] sage: clear_denominators(x + 3/2) (2, x + 3) sage: clear_denominators(x^2 + x/2 + 1/4) (2, x^2 + x + 1)
"""
# This algorithm factors the polynomial denominators. # We should check the size of the denominators and switch to # an alternate, less precise algorithm if we decide factoring # would be too slow.
def do_polred(poly): r""" Find a polynomial of reasonably small discriminant that generates the same number field as ``poly``, using the PARI ``polredbest`` function.
INPUT:
- ``poly`` - a monic irreducible polynomial with integer coefficients.
OUTPUT:
A triple (``elt_fwd``, ``elt_back``, ``new_poly``), where:
- ``new_poly`` is the new polynomial defining the same number field, - ``elt_fwd`` is a polynomial expression for a root of the new polynomial in terms of a root of the original polynomial, - ``elt_back`` is a polynomial expression for a root of the original polynomial in terms of a root of the new polynomial.
EXAMPLES::
sage: from sage.rings.qqbar import do_polred sage: R.<x> = QQ['x'] sage: oldpol = x^2 - 5 sage: fwd, back, newpol = do_polred(oldpol) sage: newpol x^2 - x - 1 sage: Kold.<a> = NumberField(oldpol) sage: Knew.<b> = NumberField(newpol) sage: newpol(fwd(a)) 0 sage: oldpol(back(b)) 0 sage: do_polred(x^2 - x - 11) (1/3*x + 1/3, 3*x - 1, x^2 - x - 1) sage: do_polred(x^3 + 123456) (-1/4*x, -4*x, x^3 - 1929)
This shows that :trac:`13054` has been fixed::
sage: do_polred(x^4 - 4294967296*x^2 + 54265257667816538374400) (1/4*x, 4*x, x^4 - 268435456*x^2 + 211973662764908353025) """
def isolating_interval(intv_fn, pol): """ ``intv_fn`` is a function that takes a precision and returns an interval of that precision containing some particular root of pol. (It must return better approximations as the precision increases.) pol is an irreducible polynomial with rational coefficients.
Returns an interval containing at most one root of pol.
EXAMPLES::
sage: from sage.rings.qqbar import isolating_interval
sage: _.<x> = QQ['x'] sage: isolating_interval(lambda prec: sqrt(RealIntervalField(prec)(2)), x^2 - 2) 1.4142135623730950488?
And an example that requires more precision::
sage: delta = 10^(-70) sage: p = (x - 1) * (x - 1 - delta) * (x - 1 + delta) sage: isolating_interval(lambda prec: RealIntervalField(prec)(1 + delta), p) 1.000000000000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000?
The function also works with complex intervals and complex roots::
sage: p = x^2 - x + 13/36 sage: isolating_interval(lambda prec: ComplexIntervalField(prec)(1/2, 1/3), p) 0.500000000000000000000? + 0.3333333333333333334?*I """
# We need to verify that pol has exactly one root in the # interval intv. We know (because it is a precondition of # calling this function) that it has at least one root in the # interval, so we only need to verify that it has at most one # root (that the interval is sufficiently narrow).
# We do this by computing the derivative of the polynomial # over the interval. If the derivative is bounded away from zero, # then we know there can be at most one root.
def find_zero_result(fn, l): """ ``l`` is a list of some sort. ``fn`` is a function which maps an element of ``l`` and a precision into an interval (either real or complex) of that precision, such that for sufficient precision, exactly one element of ``l`` results in an interval containing 0. Returns that one element of ``l``.
EXAMPLES::
sage: from sage.rings.qqbar import find_zero_result sage: _.<x> = QQ['x'] sage: delta = 10^(-70) sage: p1 = x - 1 sage: p2 = x - 1 - delta sage: p3 = x - 1 + delta sage: p2 == find_zero_result(lambda p, prec: p(RealIntervalField(prec)(1 + delta)), [p1, p2, p3]) True """ raise ValueError('find_zero_result could not find any zeroes')
def conjugate_expand(v): r""" If the interval ``v`` (which may be real or complex) includes some purely real numbers, return ``v'`` containing ``v`` such that ``v' == v'.conjugate()``. Otherwise return ``v`` unchanged. (Note that if ``v' == v'.conjugate()``, and ``v'`` includes one non-real root of a real polynomial, then ``v'`` also includes the conjugate of that root. Also note that the diameter of the return value is at most twice the diameter of the input.)
EXAMPLES::
sage: from sage.rings.qqbar import conjugate_expand sage: conjugate_expand(CIF(RIF(0, 1), RIF(1, 2))).str(style='brackets') '[0.00000000000000000 .. 1.0000000000000000] + [1.0000000000000000 .. 2.0000000000000000]*I' sage: conjugate_expand(CIF(RIF(0, 1), RIF(0, 1))).str(style='brackets') '[0.00000000000000000 .. 1.0000000000000000] + [-1.0000000000000000 .. 1.0000000000000000]*I' sage: conjugate_expand(CIF(RIF(0, 1), RIF(-2, 1))).str(style='brackets') '[0.00000000000000000 .. 1.0000000000000000] + [-2.0000000000000000 .. 2.0000000000000000]*I' sage: conjugate_expand(RIF(1, 2)).str(style='brackets') '[1.0000000000000000 .. 2.0000000000000000]' """
def conjugate_shrink(v): r""" If the interval ``v`` includes some purely real numbers, return a real interval containing only those real numbers. Otherwise return ``v`` unchanged.
If ``v`` includes exactly one root of a real polynomial, and ``v`` was returned by ``conjugate_expand()``, then ``conjugate_shrink(v)`` still includes that root, and is a ``RealIntervalFieldElement`` iff the root in question is real.
EXAMPLES::
sage: from sage.rings.qqbar import conjugate_shrink sage: conjugate_shrink(RIF(3, 4)).str(style='brackets') '[3.0000000000000000 .. 4.0000000000000000]' sage: conjugate_shrink(CIF(RIF(1, 2), RIF(1, 2))).str(style='brackets') '[1.0000000000000000 .. 2.0000000000000000] + [1.0000000000000000 .. 2.0000000000000000]*I' sage: conjugate_shrink(CIF(RIF(1, 2), RIF(0, 1))).str(style='brackets') '[1.0000000000000000 .. 2.0000000000000000]' sage: conjugate_shrink(CIF(RIF(1, 2), RIF(-1, 2))).str(style='brackets') '[1.0000000000000000 .. 2.0000000000000000]' """
def number_field_elements_from_algebraics(numbers, minimal=False): r""" Given a sequence of elements of either ``AA`` or ``QQbar`` (or a mixture), computes a number field containing all of these elements, these elements as members of that number field, and a homomorphism from the number field back to ``AA`` or ``QQbar``.
This may not return the smallest such number field, unless ``minimal=True`` is specified.
Also, a single number can be passed, rather than a sequence; and any values which are not elements of ``AA`` or ``QQbar`` will automatically be coerced to ``QQbar``
This function may be useful for efficiency reasons: doing exact computations in the corresponding number field will be faster than doing exact computations directly in ``AA`` or ``QQbar``.
EXAMPLES:
We can use this to compute the splitting field of a polynomial. (Unfortunately this takes an unreasonably long time for non-toy examples.)::
sage: x = polygen(QQ) sage: p = x^3 + x^2 + x + 17 sage: rts = p.roots(ring=QQbar, multiplicities=False) sage: splitting = number_field_elements_from_algebraics(rts)[0]; splitting Number Field in a with defining polynomial y^6 - 40*y^4 - 22*y^3 + 873*y^2 + 1386*y + 594 sage: p.roots(ring=splitting) [(361/29286*a^5 - 19/3254*a^4 - 14359/29286*a^3 + 401/29286*a^2 + 18183/1627*a + 15930/1627, 1), (49/117144*a^5 - 179/39048*a^4 - 3247/117144*a^3 + 22553/117144*a^2 + 1744/4881*a - 17195/6508, 1), (-1493/117144*a^5 + 407/39048*a^4 + 60683/117144*a^3 - 24157/117144*a^2 - 56293/4881*a - 53033/6508, 1)] sage: rt2 = AA(sqrt(2)); rt2 1.414213562373095? sage: rt3 = AA(sqrt(3)); rt3 1.732050807568878? sage: qqI = QQbar.zeta(4); qqI I sage: z3 = QQbar.zeta(3); z3 -0.500000000000000? + 0.866025403784439?*I sage: rt2b = rt3 + rt2 - rt3; rt2b 1.414213562373095? sage: rt2c = z3 + rt2 - z3; rt2c 1.414213562373095? + 0.?e-19*I
sage: number_field_elements_from_algebraics(rt2) (Number Field in a with defining polynomial y^2 - 2, a, Ring morphism: From: Number Field in a with defining polynomial y^2 - 2 To: Algebraic Real Field Defn: a |--> 1.414213562373095?)
sage: number_field_elements_from_algebraics((rt2,rt3)) (Number Field in a with defining polynomial y^4 - 4*y^2 + 1, [-a^3 + 3*a, -a^2 + 2], Ring morphism: From: Number Field in a with defining polynomial y^4 - 4*y^2 + 1 To: Algebraic Real Field Defn: a |--> 0.5176380902050415?)
We've created ``rt2b`` in such a way that \sage doesn't initially know that it's in a degree-2 extension of `\QQ`::
sage: number_field_elements_from_algebraics(rt2b) (Number Field in a with defining polynomial y^4 - 4*y^2 + 1, -a^3 + 3*a, Ring morphism: From: Number Field in a with defining polynomial y^4 - 4*y^2 + 1 To: Algebraic Real Field Defn: a |--> 0.5176380902050415?)
We can specify ``minimal=True`` if we want the smallest number field::
sage: number_field_elements_from_algebraics(rt2b, minimal=True) (Number Field in a with defining polynomial y^2 - 2, a, Ring morphism: From: Number Field in a with defining polynomial y^2 - 2 To: Algebraic Real Field Defn: a |--> 1.414213562373095?)
Things work fine with rational numbers, too::
sage: number_field_elements_from_algebraics((QQbar(1/2), AA(17))) (Rational Field, [1/2, 17], Ring morphism: From: Rational Field To: Algebraic Real Field Defn: 1 |--> 1)
Or we can just pass in symbolic expressions, as long as they can be coerced into ``QQbar``::
sage: number_field_elements_from_algebraics((sqrt(7), sqrt(9), sqrt(11))) (Number Field in a with defining polynomial y^4 - 9*y^2 + 1, [-a^3 + 8*a, 3, -a^3 + 10*a], Ring morphism: From: Number Field in a with defining polynomial y^4 - 9*y^2 + 1 To: Algebraic Real Field Defn: a |--> 0.3354367396454047?)
Here we see an example of doing some computations with number field elements, and then mapping them back into ``QQbar``::
sage: (fld,nums,hom) = number_field_elements_from_algebraics((rt2, rt3, qqI, z3)) sage: fld,nums,hom # random (Number Field in a with defining polynomial y^8 - y^4 + 1, [-a^5 + a^3 + a, a^6 - 2*a^2, a^6, -a^4], Ring morphism: From: Number Field in a with defining polynomial y^8 - y^4 + 1 To: Algebraic Field Defn: a |--> -0.2588190451025208? - 0.9659258262890683?*I) sage: (nfrt2, nfrt3, nfI, nfz3) = nums sage: hom(nfrt2) 1.414213562373095? + 0.?e-18*I sage: nfrt2^2 2 sage: nfrt3^2 3 sage: nfz3 + nfz3^2 -1 sage: nfI^2 -1 sage: sum = nfrt2 + nfrt3 + nfI + nfz3; sum 2*a^6 + a^5 - a^4 - a^3 - 2*a^2 - a sage: hom(sum) 2.646264369941973? + 1.866025403784439?*I sage: hom(sum) == rt2 + rt3 + qqI + z3 True sage: [hom(n) for n in nums] == [rt2, rt3, qqI, z3] True
TESTS::
sage: number_field_elements_from_algebraics(rt3) (Number Field in a with defining polynomial y^2 - 3, a, Ring morphism: From: Number Field in a with defining polynomial y^2 - 3 To: Algebraic Real Field Defn: a |--> 1.732050807568878?) sage: number_field_elements_from_algebraics((rt2,qqI)) (Number Field in a with defining polynomial y^4 + 1, [-a^3 + a, a^2], Ring morphism: From: Number Field in a with defining polynomial y^4 + 1 To: Algebraic Field Defn: a |--> 0.7071067811865475? + 0.7071067811865475?*I)
Note that for the first example, where \sage doesn't realize that the number is real, we get a homomorphism to ``QQbar``; but with ``minimal=True``, we get a homomorphism to ``AA``. Also note that the exact answer depends on a Pari function that gives different answers for 32-bit and 64-bit machines::
sage: number_field_elements_from_algebraics(rt2c) (Number Field in a with defining polynomial y^4 + 2*y^2 + 4, 1/2*a^3, Ring morphism: From: Number Field in a with defining polynomial y^4 + 2*y^2 + 4 To: Algebraic Field Defn: a |--> -0.7071067811865475? - 1.224744871391589?*I) sage: number_field_elements_from_algebraics(rt2c, minimal=True) (Number Field in a with defining polynomial y^2 - 2, a, Ring morphism: From: Number Field in a with defining polynomial y^2 - 2 To: Algebraic Real Field Defn: a |--> 1.414213562373095?)
"""
# Keep track of whether we were given a single value or a list.
# Cache some commonly-used polynomial rings QQx = QQ['x'] QQx_x = QQx.gen() QQy = QQ['y'] QQy_y = QQy.gen() QQxy = QQ['x', 'y'] QQxy_x = QQxy.gen(0) QQxy_y = QQxy.gen(1)
def cmp_elements_with_same_minpoly(a, b, p): r""" Compare the algebraic elements ``a`` and ``b`` knowing that they have the same minimal polynomial ``p``.
This is an helper function for comparison of algebraic elements (i.e. the methods :meth:`AlgebraicNumber._richcmp_` and :meth:`AlgebraicReal._richcmp_`).
INPUT:
- ``a`` and ``b`` -- elements of the algebraic or the real algebraic field with same minimal polynomial
- ``p`` -- the minimal polynomial
OUTPUT:
`-1`, `0`, `1`, `None` depending on whether `a < b`, `a = b` or `a > b` or the function did not succeed with the given precision of `a` and `b`.
EXAMPLES::
sage: from sage.rings.qqbar import cmp_elements_with_same_minpoly sage: x = polygen(ZZ) sage: p = x^2 - 2 sage: a = AA.polynomial_root(p, RIF(1,2)) sage: b = AA.polynomial_root(p, RIF(-2,-1)) sage: cmp_elements_with_same_minpoly(a, b, p) 1 sage: cmp_elements_with_same_minpoly(-a, b, p) 0 """
else:
and r._value.imag().abs().overlaps(imag)] # There is only a single (real) root matching both descriptors # so they both must be that root and therefore equal. not roots[0]._value.imag().contains_zero()): # There is a complex conjugate pair of roots matching both # descriptors, so compare by imaginary value. a._more_precision() ai = a._value.imag() b._more_precision() bi = b._value.imag()
class AlgebraicGeneratorRelation(SageObject): """ A simple class for maintaining relations in the lattice of algebraic extensions. """ def __init__(self, child1, child1_poly, child2, child2_poly, parent): r""" EXAMPLES::
sage: from sage.rings.qqbar import AlgebraicGeneratorRelation sage: AlgebraicGeneratorRelation(None, None, None, None, None) <sage.rings.qqbar.AlgebraicGeneratorRelation object at ...> """
algebraic_generator_counter = 0
@richcmp_method class AlgebraicGenerator(SageObject): r""" An ``AlgebraicGenerator`` represents both an algebraic number `\alpha` and the number field `\QQ[\alpha]`. There is a single ``AlgebraicGenerator`` representing `\QQ` (with `\alpha=0`).
The ``AlgebraicGenerator`` class is private, and should not be used directly. """
def __init__(self, field, root): """ Construct an ``AlgebraicGenerator`` object.
EXAMPLES::
sage: from sage.rings.qqbar import ANRoot, AlgebraicGenerator, qq_generator sage: y = polygen(QQ, 'y') sage: x = polygen(QQbar) sage: nf = NumberField(y^2 - y - 1, name='a', check=False) sage: root = ANRoot(x^2 - x - 1, RIF(1, 2)) sage: gen = AlgebraicGenerator(nf, root) sage: gen Number Field in a with defining polynomial y^2 - y - 1 with a in 1.618033988749895? sage: gen.field() Number Field in a with defining polynomial y^2 - y - 1 sage: gen.is_trivial() False sage: gen.union(qq_generator) is gen True sage: qq_generator.union(gen) is gen True sage: nf = NumberField(y^2 + 1, name='a', check=False) sage: root = ANRoot(x^2 + 1, CIF(0, 1)) sage: x = AlgebraicGenerator(nf, root); x Number Field in a with defining polynomial y^2 + 1 with a in 1*I """ global algebraic_generator_counter
def __reduce__(self): """ Add customized pickling support.
EXAMPLES::
sage: t = QQbar(sqrt(2)) + QQbar(sqrt(3)) sage: t.exactify() sage: type(t._descr._generator) <class 'sage.rings.qqbar.AlgebraicGenerator'> sage: loads(dumps(t)) == t True """
def __hash__(self): r""" Return a hash value for self. This will depend on the order that commands get executed at load time, so we do not test the value that is returned, just that it doesn't raise an error.
EXAMPLES::
sage: from sage.rings.qqbar import ANRoot, AlgebraicGenerator, qq_generator sage: _.<y> = QQ['y'] sage: x = polygen(QQbar) sage: nf = NumberField(y^2 - y - 1, name='a', check=False) sage: root = ANRoot(x^2 - x - 1, RIF(1, 2)) sage: gen = AlgebraicGenerator(nf, root) sage: hash(gen) # random """
def __richcmp__(self, other, op): r""" Compare ``self`` with another ``AlgebraicGenerator`` object.
EXAMPLES::
sage: from sage.rings.qqbar import ANRoot, AlgebraicGenerator, qq_generator sage: _.<y> = QQ['y'] sage: x = polygen(QQbar) sage: nf = NumberField(y^2 - y - 1, name='a', check=False) sage: root = ANRoot(x^2 - x - 1, RIF(1, 2)) sage: gen = AlgebraicGenerator(nf, root) sage: gen > qq_generator True """
def is_complex(self): r""" Return True if this is a generator for a non-real number field.
EXAMPLES::
sage: z7 = QQbar.zeta(7) sage: g = z7._descr._generator sage: g.is_complex() True
sage: from sage.rings.qqbar import ANRoot, AlgebraicGenerator sage: y = polygen(QQ, 'y') sage: x = polygen(QQbar) sage: nf = NumberField(y^2 - y - 1, name='a', check=False) sage: root = ANRoot(x^2 - x - 1, RIF(1, 2)) sage: gen = AlgebraicGenerator(nf, root) sage: gen.is_complex() False """
def _repr_(self): r""" String representation of self.
EXAMPLES::
sage: from sage.rings.qqbar import qq_generator sage: qq_generator._repr_() 'Trivial generator'
sage: from sage.rings.qqbar import ANRoot, AlgebraicGenerator, qq_generator sage: y = polygen(QQ) sage: x = polygen(QQbar) sage: nf = NumberField(y^2 - y - 1, name='a', check=False) sage: root = ANRoot(x^2 - x - 1, RIF(1, 2)) sage: gen = AlgebraicGenerator(nf, root) sage: gen._repr_() 'Number Field in a with defining polynomial x^2 - x - 1 with a in 1.618033988749895?' """ else:
def root_as_algebraic(self): r""" Return the root attached to self as an algebraic number.
EXAMPLES::
sage: t = sage.rings.qqbar.qq_generator.root_as_algebraic(); t 1 sage: t.parent() Algebraic Real Field """
def is_trivial(self): """ Returns true iff this is the trivial generator (alpha == 1), which does not actually extend the rationals.
EXAMPLES::
sage: from sage.rings.qqbar import qq_generator sage: qq_generator.is_trivial() True """
def field(self): r""" Return the number field attached to self.
EXAMPLES::
sage: from sage.rings.qqbar import qq_generator sage: qq_generator.field() Rational Field """
def pari_field(self): r""" Return the PARI field attached to this generator.
EXAMPLES::
sage: from sage.rings.qqbar import qq_generator sage: qq_generator.pari_field() Traceback (most recent call last): ... ValueError: No PARI field attached to trivial generator
sage: from sage.rings.qqbar import ANRoot, AlgebraicGenerator, qq_generator sage: y = polygen(QQ) sage: x = polygen(QQbar) sage: nf = NumberField(y^2 - y - 1, name='a', check=False) sage: root = ANRoot(x^2 - x - 1, RIF(1, 2)) sage: gen = AlgebraicGenerator(nf, root) sage: gen.pari_field() [y^2 - y - 1, [2, 0], ...] """
def conjugate(self): r""" If this generator is for the algebraic number `\alpha`, return a generator for the complex conjugate of `\alpha`.
EXAMPLES::
sage: from sage.rings.qqbar import AlgebraicGenerator sage: x = polygen(QQ); f = x^4 + x + 17 sage: nf = NumberField(f,name='a') sage: b = f.roots(QQbar)[0][0] sage: root = b._descr sage: gen = AlgebraicGenerator(nf, root) sage: gen.conjugate() Number Field in a with defining polynomial x^4 + x + 17 with a in -1.436449997483091? + 1.374535713065812?*I """ self._conjugate = self else: conj_rel = QQx_x ** (self._cyclotomic_order - 1) rel = AlgebraicGeneratorRelation(self, conj_rel, conj, conj_rel, self) self._unions[conj] = rel conj._unions[self] = rel
def _interval_fast(self, prec): """ Returns an interval containing this generator, to the specified precision.
EXAMPLES::
sage: from sage.rings.qqbar import ANRoot, AlgebraicGenerator, qq_generator sage: y = polygen(QQ, 'y') sage: x = polygen(QQbar) sage: nf = NumberField(y^2 - y - 1, name='a', check=False) sage: root = ANRoot(x^2 - x - 1, RIF(1, 2)) sage: gen = AlgebraicGenerator(nf, root) sage: gen._interval_fast(128) 1.61803398874989484820458683436563811773? """
def union(self, other): r""" Given generators ``alpha`` and ``beta``, ``alpha.union(beta)`` gives a generator for the number field `\QQ[\alpha][\beta]`.
EXAMPLES::
sage: from sage.rings.qqbar import ANRoot, AlgebraicGenerator, qq_generator sage: _.<y> = QQ['y'] sage: x = polygen(QQbar) sage: nf2 = NumberField(y^2 - 2, name='a', check=False) sage: root2 = ANRoot(x^2 - 2, RIF(1, 2)) sage: gen2 = AlgebraicGenerator(nf2, root2) sage: gen2 Number Field in a with defining polynomial y^2 - 2 with a in 1.414213562373095? sage: nf3 = NumberField(y^2 - 3, name='a', check=False) sage: root3 = ANRoot(x^2 - 3, RIF(1, 2)) sage: gen3 = AlgebraicGenerator(nf3, root3) sage: gen3 Number Field in a with defining polynomial y^2 - 3 with a in 1.732050807568878? sage: gen2.union(qq_generator) is gen2 True sage: qq_generator.union(gen3) is gen3 True sage: gen2.union(gen3) Number Field in a with defining polynomial y^4 - 4*y^2 + 1 with a in 0.5176380902050415? """ self, other = other, self
# pari_nf = self._field.pari_nf()
other, value, self)
# XXX need more caching here
other, (QQx_x - k*self_pol_sage)(red_back_x), new_gen)
def super_poly(self, super, checked=None): r""" Given a generator ``gen`` and another generator ``super``, where ``super`` is the result of a tree of ``union()`` operations where one of the leaves is ``gen``, ``gen.super_poly(super)`` returns a polynomial expressing the value of ``gen`` in terms of the value of ``super`` (except that if ``gen`` is ``qq_generator``, ``super_poly()`` always returns None.)
EXAMPLES::
sage: from sage.rings.qqbar import AlgebraicGenerator, ANRoot, qq_generator sage: _.<y> = QQ['y'] sage: x = polygen(QQbar) sage: nf2 = NumberField(y^2 - 2, name='a', check=False) sage: root2 = ANRoot(x^2 - 2, RIF(1, 2)) sage: gen2 = AlgebraicGenerator(nf2, root2) sage: gen2 Number Field in a with defining polynomial y^2 - 2 with a in 1.414213562373095? sage: nf3 = NumberField(y^2 - 3, name='a', check=False) sage: root3 = ANRoot(x^2 - 3, RIF(1, 2)) sage: gen3 = AlgebraicGenerator(nf3, root3) sage: gen3 Number Field in a with defining polynomial y^2 - 3 with a in 1.732050807568878? sage: gen2_3 = gen2.union(gen3) sage: gen2_3 Number Field in a with defining polynomial y^4 - 4*y^2 + 1 with a in 0.5176380902050415? sage: qq_generator.super_poly(gen2) is None True sage: gen2.super_poly(gen2_3) -a^3 + 3*a sage: gen3.super_poly(gen2_3) -a^2 + 2
"""
def __call__(self, elt): """ Takes an algebraic number which is represented as either a rational or a number field element, and which is in a subfield of the field generated by this generator. Lifts the number into the field of this generator, and returns either a ``Rational`` or a ``NumberFieldElement`` depending on whether this is the trivial generator.
EXAMPLES::
sage: from sage.rings.qqbar import ANRoot, AlgebraicGenerator, ANExtensionElement, ANRational sage: _.<y> = QQ['y'] sage: x = polygen(QQbar) sage: nf2 = NumberField(y^2 - 2, name='a', check=False) sage: root2 = ANRoot(x^2 - 2, RIF(1, 2)) sage: gen2 = AlgebraicGenerator(nf2, root2) sage: gen2 Number Field in a with defining polynomial y^2 - 2 with a in 1.414213562373095? sage: sqrt2 = ANExtensionElement(gen2, nf2.gen()) sage: nf3 = NumberField(y^2 - 3, name='a', check=False) sage: root3 = ANRoot(x^2 - 3, RIF(1, 2)) sage: gen3 = AlgebraicGenerator(nf3, root3) sage: gen3 Number Field in a with defining polynomial y^2 - 3 with a in 1.732050807568878? sage: sqrt3 = ANExtensionElement(gen3, nf3.gen()) sage: gen2_3 = gen2.union(gen3) sage: gen2_3 Number Field in a with defining polynomial y^4 - 4*y^2 + 1 with a in 0.5176380902050415? sage: gen2_3(sqrt2) -a^3 + 3*a sage: gen2_3(ANRational(1/7)) 1/7 sage: gen2_3(sqrt3) -a^2 + 2 """
# dictionary for multimethod dispatch _binop_algo = {}
class ANDescr(SageObject): r""" An ``AlgebraicNumber`` or ``AlgebraicReal`` is a wrapper around an ``ANDescr`` object. ``ANDescr`` is an abstract base class, which should never be directly instantiated; its concrete subclasses are ``ANRational``, ``ANBinaryExpr``, ``ANUnaryExpr``, ``ANRoot``, and ``ANExtensionElement``. ``ANDescr`` and all of its subclasses are for internal use, and should not be used directly. """ def is_simple(self): r""" Checks whether this descriptor represents a value with the same algebraic degree as the number field associated with the descriptor.
Returns ``True`` if self is an ``ANRational``, or a minimal ``ANExtensionElement``.
EXAMPLES::
sage: from sage.rings.qqbar import ANRational sage: ANRational(1/2).is_simple() True sage: rt2 = AA(sqrt(2)) sage: rt3 = AA(sqrt(3)) sage: rt2b = rt3 + rt2 - rt3 sage: rt2.exactify() sage: rt2._descr.is_simple() True sage: rt2b.exactify() sage: rt2b._descr.is_simple() False sage: rt2b.simplify() sage: rt2b._descr.is_simple() True """ return False
# Unitary operators: the second argument "n" is an AlgebraicNumber_base # wrapper around self.
def neg(self, n): r""" Negation of self.
EXAMPLES::
sage: a = QQbar(sqrt(2)) sage: b = a._descr sage: b.neg(a) <sage.rings.qqbar.ANUnaryExpr object at ...> """
def invert(self, n): r""" 1/self.
EXAMPLES::
sage: a = QQbar(sqrt(2)) sage: b = a._descr sage: b.invert(a) <sage.rings.qqbar.ANUnaryExpr object at ...> """
def abs(self, n): r""" Absolute value of self.
EXAMPLES::
sage: a = QQbar(sqrt(2)) sage: b = a._descr sage: b.abs(a) <sage.rings.qqbar.ANUnaryExpr object at ...> """
def real(self, n): r""" Real part of self.
EXAMPLES::
sage: a = QQbar(sqrt(-7)) sage: b = a._descr sage: b.real(a) <sage.rings.qqbar.ANUnaryExpr object at ...> """ else:
def imag(self, n): r""" Imaginary part of self.
EXAMPLES::
sage: a = QQbar(sqrt(-7)) sage: b = a._descr sage: b.imag(a) <sage.rings.qqbar.ANUnaryExpr object at ...> """ else:
def conjugate(self, n): r""" Complex conjugate of self.
EXAMPLES::
sage: a = QQbar(sqrt(-7)) sage: b = a._descr sage: b.conjugate(a) <sage.rings.qqbar.ANUnaryExpr object at ...> """ else:
def norm(self, n): r""" Field norm of self from `\overline{\QQ}` to its real subfield `\mathbf{A}`, i.e.~the square of the usual complex absolute value.
EXAMPLES::
sage: a = QQbar(sqrt(-7)) sage: b = a._descr sage: b.norm(a) <sage.rings.qqbar.ANUnaryExpr object at ...> """ else:
class AlgebraicNumber_base(sage.structure.element.FieldElement): r""" This is the common base class for algebraic numbers (complex numbers which are the zero of a polynomial in `\ZZ[x]`) and algebraic reals (algebraic numbers which happen to be real).
``AlgebraicNumber`` objects can be created using ``QQbar`` (== ``AlgebraicNumberField()``), and ``AlgebraicReal`` objects can be created using ``AA`` (== ``AlgebraicRealField()``). They can be created either by coercing a rational or a symbolic expression, or by using the ``QQbar.polynomial_root()`` or ``AA.polynomial_root()`` method to construct a particular root of a polynomial with algebraic coefficients. Also, ``AlgebraicNumber`` and ``AlgebraicReal`` are closed under addition, subtraction, multiplication, division (except by 0), and rational powers (including roots), except that for a negative ``AlgebraicReal``, taking a power with an even denominator returns an ``AlgebraicNumber`` instead of an ``AlgebraicReal``.
``AlgebraicNumber`` and ``AlgebraicReal`` objects can be approximated to any desired precision. They can be compared exactly; if the two numbers are very close, or are equal, this may require exact computation, which can be extremely slow.
As long as exact computation is not triggered, computation with algebraic numbers should not be too much slower than computation with intervals. As mentioned above, exact computation is triggered when comparing two algebraic numbers which are very close together. This can be an explicit comparison in user code, but the following list of actions (not necessarily complete) can also trigger exact computation:
- Dividing by an algebraic number which is very close to 0.
- Using an algebraic number which is very close to 0 as the leading coefficient in a polynomial.
- Taking a root of an algebraic number which is very close to 0.
The exact definition of "very close" is subject to change; currently, we compute our best approximation of the two numbers using 128-bit arithmetic, and see if that's sufficient to decide the comparison. Note that comparing two algebraic numbers which are actually equal will always trigger exact computation, unless they are actually the same object.
EXAMPLES::
sage: sqrt(QQbar(2)) 1.414213562373095? sage: sqrt(QQbar(2))^2 == 2 True sage: x = polygen(QQbar) sage: phi = QQbar.polynomial_root(x^2 - x - 1, RIF(1, 2)) sage: phi 1.618033988749895? sage: phi^2 == phi+1 True sage: AA(sqrt(65537)) 256.0019531175495? """
def __init__(self, parent, x): r""" Initialize an algebraic number. The argument must be either a rational number, a Gaussian rational, or a subclass of ``ANDescr``.
EXAMPLES::
sage: AlgebraicReal(22/7) 22/7 """ sage.rings.rational.Rational)): isinstance(x, NumberFieldElement_quadratic) and \ list(x.parent().polynomial()) == [1, 0, 1]: else:
def _repr_(self): """ Returns the print representation of this number.
EXAMPLES::
sage: AA(22/7) # indirect doctest 22/7 sage: QQbar(1/3 + 2/7*I) 2/7*I + 1/3 sage: QQbar.zeta(4) + 5 I + 5 sage: QQbar.zeta(4) I sage: 3*QQbar.zeta(4) 3*I sage: QQbar.zeta(17) 0.9324722294043558? + 0.3612416661871530?*I sage: AA(19).sqrt() 4.358898943540674? """ else:
def _latex_(self): r""" Returns the latex representation of this number.
EXAMPLES::
sage: latex(AA(22/7)) \frac{22}{7} sage: latex(QQbar(1/3 + 2/7*I)) \frac{2}{7} i + \frac{1}{3} sage: latex(QQbar.zeta(4) + 5) i + 5 sage: latex(QQbar.zeta(4)) i sage: latex(3*QQbar.zeta(4)) 3 i sage: latex(QQbar.zeta(17)) 0.9324722294043558? + 0.3612416661871530? \sqrt{-1} sage: latex(AA(19).sqrt()) 4.358898943540674? """
def _sage_input_(self, sib, coerce): r""" Produce an expression which will reproduce this value when evaluated.
EXAMPLES:
These examples are mostly copied from the doctests of the ``handle_sage_input`` functions; see those for more examples::
sage: sage_input(QQbar(3)) QQbar(3) sage: sage_input(AA(22/7)) AA(22/7) sage: sage_input(22/7*QQbar.zeta(4)) QQbar(22/7*I) sage: sage_input(QQbar.zeta(5)^3) R.<x> = AA[] QQbar.polynomial_root(AA.common_polynomial(x^4 + x^3 + x^2 + x + 1), CIF(RIF(RR(0.3090169943749474), RR(0.30901699437494745)), RIF(RR(0.95105651629515353), RR(0.95105651629515364))))^3 sage: sage_input((AA(3)^(1/2))^(1/3)) R.<x> = AA[] AA.polynomial_root(AA.common_polynomial(x^3 - AA.polynomial_root(AA.common_polynomial(x^2 - 3), RIF(RR(1.7320508075688772), RR(1.7320508075688774)))), RIF(RR(1.2009369551760025), RR(1.2009369551760027))) sage: sage_input(QQbar(3+4*I)) QQbar(3 + 4*I) sage: sage_input(-sqrt(AA(2))) R.<x> = AA[] -AA.polynomial_root(AA.common_polynomial(x^2 - 2), RIF(RR(1.4142135623730949), RR(1.4142135623730951))) sage: sage_input(2 + sqrt(AA(2))) R.<x> = AA[] 2 + AA.polynomial_root(AA.common_polynomial(x^2 - 2), RIF(RR(1.4142135623730949), RR(1.4142135623730951)))
And a nice big example::
sage: K.<x> = QQ[] sage: p = K.random_element(4); p 1/2*x^4 - 1/95*x^3 - 1/2*x^2 - 4 sage: rts = p.roots(ring=QQbar, multiplicities=False); rts [-1.830225346898784?, 1.842584249981426?, 0.004346864248152390? - 1.540200655088741?*I, 0.004346864248152390? + 1.540200655088741?*I] sage: sage_input(rts, verify=True) # long time (2s on sage.math, 2013) # Verified R.<x> = AA[] cp = AA.common_polynomial(1/2*x^4 - 1/95*x^3 - 1/2*x^2 - 4) [QQbar.polynomial_root(cp, CIF(RIF(-RR(1.8302253468987832), -RR(1.830225346898783)), RIF(RR(0)))), QQbar.polynomial_root(cp, CIF(RIF(RR(1.8425842499814258), RR(1.842584249981426)), RIF(RR(0)))), QQbar.polynomial_root(cp, CIF(RIF(RR(0.0043468642481523899), RR(0.0043468642481523908)), RIF(-RR(1.5402006550887404), -RR(1.5402006550887402)))), QQbar.polynomial_root(cp, CIF(RIF(RR(0.0043468642481523899), RR(0.0043468642481523908)), RIF(RR(1.5402006550887402), RR(1.5402006550887404))))]
sage: from sage.misc.sage_input import SageInputBuilder sage: sib = SageInputBuilder() sage: sqrt(QQbar(7))._sage_input_(sib, False) {call: {getattr: {atomic:QQbar}.polynomial_root}({call: {getattr: {atomic:AA}.common_polynomial}({binop:- {binop:** {gen:x {constr_parent: {subscr: {atomic:QQbar}[{atomic:'x'}]} with gens: ('x',)}} {atomic:2}} {atomic:7}})}, {call: {atomic:CIF}({call: {atomic:RIF}({call: {atomic:RR}({atomic:2.6457513110645903})}, {call: {atomic:RR}({atomic:2.6457513110645907})})}, {call: {atomic:RIF}({call: {atomic:RR}({atomic:0})})})})} """ self._descr.handle_sage_input(sib, coerce, self.parent() is QQbar)
def _mul_(self, other): """ TESTS::
sage: AA(sqrt(2)) * AA(sqrt(8)) # indirect doctest 4.000000000000000? """
def _div_(self, other): """ TESTS::
sage: AA(sqrt(2)) / AA(sqrt(8)) # indirect doctest 0.500000000000000? """
def __invert__(self): """ TESTS::
sage: ~AA(sqrt(~2)) 1.414213562373095? """
def _add_(self, other): """ TESTS::
sage: x = polygen(ZZ) sage: rt1, rt2 = (x^2 - x - 1).roots(ring=AA, multiplicities=False) sage: rt1 + rt2 # indirect doctest 1.000000000000000? """
def _sub_(self, other): """ TESTS::
sage: AA(golden_ratio) * 2 - AA(5).sqrt() # indirect doctest 1.000000000000000? """
def _neg_(self): """ TESTS::
sage: -QQbar(I) # indirect doctest -I """
def __abs__(self): """ TESTS::
sage: abs(AA(sqrt(2) - sqrt(3))) 0.3178372451957823? sage: abs(QQbar(3+4*I)) 5 sage: v = QQbar.zeta(3) + 1 sage: v.exactify() sage: v.abs().minpoly() x - 1 """
def __hash__(self): """ Compute a hash code for this number (equal algebraic numbers will have the same hash code, different algebraic numbers are likely to have different hash codes).
This may trigger exact computation, but that is very unlikely.
TESTS:
The hash code is stable, even when the representation changes::
sage: two = QQbar(4).nth_root(4)^2 sage: two 2.000000000000000? sage: h1 = hash(two) sage: two == 2 True sage: two 2 sage: h2 = hash(two) sage: h1 == h2 True
sage: h1 = hash(QQbar.zeta(6)) sage: h2 = hash(QQbar(1/2 + I*sqrt(3)/2)) sage: h1 == h2 True
Unfortunately, the hash code for algebraic numbers which are close enough to each other are the same. (This is inevitable, if equal algebraic reals give the same hash code and hashing does not always trigger exact computation.)::
sage: h1 = hash(QQbar(0)) sage: h2 = hash(QQbar(1/2^100)) sage: hash(h1) == hash(h2) True
"""
# The only way I can think of to hash algebraic numbers without # always triggering exact computation is to use interval_exact(). # However, interval_exact() always triggers exact computation # if the number is exactly representable in floating point, which # is presumably not too unlikely (algebraic reals like 0, 1/2, # 1, or 2 are presumably not uncommon).
# So I modify the algebraic real by adding 1/123456789 to it before # calling interval_exact(). Then, exact computation will be triggered # by algebraic reals which are sufficiently close to # (some floating point number minus 1/123456789). Hopefully, # -1/123456789 comes up in algebraic real computations far less # often than 0 does. Algebraic numbers have a similar offset added, # with an additional complex component of 1/987654321*I.
# All of this effort to avoid exact computation is probably wasted, # anyway... in almost all uses of hash codes, if the hash codes # match, the next step is to compare for equality; and comparing # for equality often requires exact computation. (If a==b, # then checking a==b requires exact computation unless (a is b).)
else:
def __bool__(self): """ Check whether ``self`` is nonzero.
This is fast if interval arithmetic proves it and in many other cases. Though, it might be slow in very particular cases where the number is actually zero or very close to zero.
EXAMPLES::
sage: bool(QQbar.zeta(2) + 1) False sage: bool(QQbar.zeta(7) / (2^500)) True
sage: bool(QQbar(I).imag()) True sage: bool(QQbar(I).real()) False
The following is very fast, even though the number is really small::
sage: a1 = QQbar(2).sqrt() - 16616132878186749607/11749380235262596085 sage: a2 = QQbar(2).sqrt() - 16616132878186749607/11749380235262596085 sage: bool(a1 + a2) True sage: bool(a1 - a2) False
sage: a = QQbar(2).sqrt() - 16616132878186749607/11749380235262596085 sage: b = QQbar(2).sqrt() - 6882627592338442563/4866752642924153522 sage: c = QQbar(3).sqrt() - 142437039878091970439/82236063316189858921 sage: d = (59/2)**(1000/7) sage: e = (a + b + c) * (a + b - c) * (a - b) * (a - b - c) / d sage: bool(e) True sage: bool(e.abs() < 2**-500) True
An identity between roots of unity::
sage: z3 = QQbar.zeta(3) sage: z4 = QQbar.zeta(4) sage: z5 = QQbar.zeta(5) sage: p1 = (z3 + z4 + z5)**2 sage: p2 = (z3 - z4 - z5)**2 sage: p3 = (z3 - z4 + z5)**2 sage: p4 = (z3 + z4 - z5)**2 sage: bool(p1 - p2 + p3 - p4 - 8 * QQbar.zeta(15)**8) False
Test some non-trivial zeros::
sage: x = polygen(ZZ) sage: a = (AA(2).sqrt() + AA(3).sqrt() + AA(5).sqrt())^2 sage: b = 10 + 2*max((x^4 - 62*x^2 - 240*x - 239).roots(AA, False)) sage: bool(a - b) False
sage: d = sum(AA(k)**(1/k) for k in [2..100]) sage: bool(d * (a - b)) False sage: bool((a - b) * d) False sage: bool(d * (a - b) * d) False sage: bool((a - b) / d) False
sage: d = sum(QQbar(-k)**(1/k) for k in [2..100]) sage: bool(d * (a - b)) False sage: bool((a - b) * d) False sage: bool(d * (a - b) * d) False sage: bool((a - b) / d) False """ # case 0: trivial tests
# case 1: cheap tests # The ANExtensionElement returns an ANRational # instead, if the number is zero. return bool(sd._value)
# case 2: try more precision
# case 3: try with minpoly in case of x+y or x-y
# Sigh...
__nonzero__ = __bool__
def is_square(self): """ Return whether or not this number is square.
OUTPUT:
(boolean) True in all cases for elements of QQbar; True for non-negative elements of AA, otherwise False.
EXAMPLES::
sage: AA(2).is_square() True sage: AA(-2).is_square() False sage: QQbar(-2).is_square() True sage: QQbar(I).is_square() True """ else:
def is_integer(self): """ Return True if this number is a integer
EXAMPLES::
sage: QQbar(2).is_integer() True sage: QQbar(1/2).is_integer() False """
def sqrt(self, all=False, extend=True): """ Return the square root(s) of this number.
INPUT:
- ``extend`` - bool (default: True); ignored if self is in QQbar, or positive in AA. If self is negative in AA, do the following: if True, return a square root of self in QQbar, otherwise raise a ValueError.
- ``all`` - bool (default: False); if True, return a list of all square roots. If False, return just one square root, or raise an ValueError if self is a negative element of AA and extend=False.
OUTPUT:
Either the principal square root of self, or a list of its square roots (with the principal one first).
EXAMPLES::
sage: AA(2).sqrt() 1.414213562373095?
sage: QQbar(I).sqrt() 0.7071067811865475? + 0.7071067811865475?*I sage: QQbar(I).sqrt(all=True) [0.7071067811865475? + 0.7071067811865475?*I, -0.7071067811865475? - 0.7071067811865475?*I]
sage: a = QQbar(0) sage: a.sqrt() 0 sage: a.sqrt(all=True) [0]
sage: a = AA(0) sage: a.sqrt() 0 sage: a.sqrt(all=True) [0]
This second example just shows that the program doesn't care where 0 is defined, it gives the same answer regardless. After all, how many ways can you square-root zero?
::
sage: AA(-2).sqrt() 1.414213562373095?*I
sage: AA(-2).sqrt(all=True) [1.414213562373095?*I, -1.414213562373095?*I]
sage: AA(-2).sqrt(extend=False) Traceback (most recent call last): ... ValueError: -2 is not a square in AA, being negative. Use extend = True for a square root in QQbar.
""" # deal with 0 first:
else:
# raise an error if appropriate:
else: return []
else:
def nth_root(self, n, all=False): r""" Return the ``n``-th root of this number.
INPUT:
- ``all`` - bool (default: ``False``). If ``True``, return a list of all `n`-th roots as complex algebraic numbers.
.. WARNING::
Note that for odd `n`, all=`False` and negative real numbers, ``AlgebraicReal`` and ``AlgebraicNumber`` values give different answers: ``AlgebraicReal`` values prefer real results, and ``AlgebraicNumber`` values return the principal root.
EXAMPLES::
sage: AA(-8).nth_root(3) -2 sage: QQbar(-8).nth_root(3) 1.000000000000000? + 1.732050807568878?*I sage: QQbar.zeta(12).nth_root(15) 0.9993908270190957? + 0.03489949670250097?*I
You can get all ``n``-th roots of algebraic numbers::
sage: AA(-8).nth_root(3, all=True) [1.000000000000000? + 1.732050807568878?*I, -2.000000000000000? + 0.?e-18*I, 1.000000000000000? - 1.732050807568878?*I]
sage: QQbar(1+I).nth_root(4, all=True) [1.069553932363986? + 0.2127475047267431?*I, -0.2127475047267431? + 1.069553932363986?*I, -1.069553932363986? - 0.2127475047267431?*I, 0.2127475047267431? - 1.069553932363986?*I]
TESTS::
sage: AA(-8).nth_root(3, all=True)[1] -2.000000000000000? + 0.?e-18*I sage: _.parent() Algebraic Field
sage: AA(-2).nth_root(5, all=True) == QQbar(-2).nth_root(5, all=True) # long time True """ else:
def as_number_field_element(self, minimal=False): r""" Returns a number field containing this value, a representation of this value as an element of that number field, and a homomorphism from the number field back to ``AA`` or ``QQbar``.
This may not return the smallest such number field, unless ``minimal=True`` is specified.
To compute a single number field containing multiple algebraic numbers, use the function ``number_field_elements_from_algebraics`` instead.
EXAMPLES::
sage: QQbar(sqrt(8)).as_number_field_element() (Number Field in a with defining polynomial y^2 - 2, 2*a, Ring morphism: From: Number Field in a with defining polynomial y^2 - 2 To: Algebraic Real Field Defn: a |--> 1.414213562373095?) sage: x = polygen(ZZ) sage: p = x^3 + x^2 + x + 17 sage: (rt,) = p.roots(ring=AA, multiplicities=False); rt -2.804642726932742? sage: (nf, elt, hom) = rt.as_number_field_element() sage: nf, elt, hom (Number Field in a with defining polynomial y^3 - 2*y^2 - 31*y - 50, a^2 - 5*a - 19, Ring morphism: From: Number Field in a with defining polynomial y^3 - 2*y^2 - 31*y - 50 To: Algebraic Real Field Defn: a |--> 7.237653139801104?) sage: hom(elt) == rt True
We see an example where we do not get the minimal number field unless we specify ``minimal=True``::
sage: rt2 = AA(sqrt(2)) sage: rt3 = AA(sqrt(3)) sage: rt3b = rt2 + rt3 - rt2 sage: rt3b.as_number_field_element() (Number Field in a with defining polynomial y^4 - 4*y^2 + 1, -a^2 + 2, Ring morphism: From: Number Field in a with defining polynomial y^4 - 4*y^2 + 1 To: Algebraic Real Field Defn: a |--> 0.5176380902050415?) sage: rt3b.as_number_field_element(minimal=True) (Number Field in a with defining polynomial y^2 - 3, a, Ring morphism: From: Number Field in a with defining polynomial y^2 - 3 To: Algebraic Real Field Defn: a |--> 1.732050807568878?) """
def exactify(self): """ Compute an exact representation for this number.
EXAMPLES::
sage: two = QQbar(4).nth_root(4)^2 sage: two 2.000000000000000? sage: two.exactify() sage: two 2 """
def _set_descr(self, new_descr): """ Set ``self._descr`` to ``new_descr``, and update ``self._value`` accordingly.
EXAMPLES::
sage: c = QQbar(-1)**(1/3) - QQbar(3)**(1/2)/2*QQbar.gen() sage: c._value 0.5000000000000000000? + 0.?e-19*I sage: c.exactify() # indirect doctest sage: c._value 0.500000000000000000000? """ else:
def simplify(self): """ Compute an exact representation for this number, in the smallest possible number field.
EXAMPLES::
sage: rt2 = AA(sqrt(2)) sage: rt3 = AA(sqrt(3)) sage: rt2b = rt3 + rt2 - rt3 sage: rt2b.exactify() sage: rt2b._exact_value() a^3 - 3*a where a^4 - 4*a^2 + 1 = 0 and a in 1.931851652578137? sage: rt2b.simplify() sage: rt2b._exact_value() a where a^2 - 2 = 0 and a in 1.414213562373095? """
def _exact_field(self): """ Returns a generator for a number field that includes this number (not necessarily the smallest such number field).
EXAMPLES::
sage: QQbar(2)._exact_field() Trivial generator sage: (sqrt(QQbar(2)) + sqrt(QQbar(19)))._exact_field() Number Field in a with defining polynomial y^4 - 20*y^2 + 81 with a in 2.375100220297941? sage: (QQbar(7)^(3/5))._exact_field() Number Field in a with defining polynomial y^5 - 2*y^4 - 18*y^3 + 38*y^2 + 82*y - 181 with a in 2.554256611698490? """
def _exact_value(self): r""" Returns an ``ANRational`` or an ``ANExtensionElement`` representing this value.
EXAMPLES::
sage: QQbar(2)._exact_value() 2 sage: (sqrt(QQbar(2)) + sqrt(QQbar(19)))._exact_value() -1/9*a^3 - a^2 + 11/9*a + 10 where a^4 - 20*a^2 + 81 = 0 and a in 2.375100220297941? sage: (QQbar(7)^(3/5))._exact_value() 2*a^4 + 2*a^3 - 34*a^2 - 17*a + 150 where a^5 - 2*a^4 - 18*a^3 + 38*a^2 + 82*a - 181 = 0 and a in 2.554256611698490? """
def _more_precision(self): """ Recompute the interval bounding this number with higher-precision interval arithmetic.
EXAMPLES::
sage: rt2 = sqrt(QQbar(2)) sage: rt2._value 1.4142135623730950488? sage: rt2._more_precision() sage: rt2._value 1.41421356237309504880168872420969807857? sage: rt2._more_precision() sage: rt2._value 1.41421356237309504880168872420969807856967187537694807317667973799073247846211? """
def minpoly(self): """ Compute the minimal polynomial of this algebraic number. The minimal polynomial is the monic polynomial of least degree having this number as a root; it is unique.
EXAMPLES::
sage: QQbar(4).sqrt().minpoly() x - 2 sage: ((QQbar(2).nth_root(4))^2).minpoly() x^2 - 2 sage: v = sqrt(QQbar(2)) + sqrt(QQbar(3)); v 3.146264369941973? sage: p = v.minpoly(); p x^4 - 10*x^2 + 1 sage: p(RR(v.real())) 1.31006316905768e-14 """
def degree(self): """ Return the degree of this algebraic number (the degree of its minimal polynomial, or equivalently, the degree of the smallest algebraic extension of the rationals containing this number).
EXAMPLES::
sage: QQbar(5/3).degree() 1 sage: sqrt(QQbar(2)).degree() 2 sage: QQbar(17).nth_root(5).degree() 5 sage: sqrt(3+sqrt(QQbar(8))).degree() 2 """
def interval_fast(self, field): r""" Given a :class:`RealIntervalField` or :class:`ComplexIntervalField`, compute the value of this number using interval arithmetic of at least the precision of the field, and return the value in that field. (More precision may be used in the computation.) The returned interval may be arbitrarily imprecise, if this number is the result of a sufficiently long computation chain.
EXAMPLES::
sage: x = AA(2).sqrt() sage: x.interval_fast(RIF) 1.414213562373095? sage: x.interval_fast(RealIntervalField(200)) 1.414213562373095048801688724209698078569671875376948073176680? sage: x = QQbar(I).sqrt() sage: x.interval_fast(CIF) 0.7071067811865475? + 0.7071067811865475?*I sage: x.interval_fast(RIF) Traceback (most recent call last): ... TypeError: unable to convert complex interval 0.7071067811865475244? + 0.7071067811865475244?*I to real interval """
def interval_diameter(self, diam): """ Compute an interval representation of self with ``diameter()`` at most ``diam``. The precision of the returned value is unpredictable.
EXAMPLES::
sage: AA(2).sqrt().interval_diameter(1e-10) 1.4142135623730950488? sage: AA(2).sqrt().interval_diameter(1e-30) 1.41421356237309504880168872420969807857? sage: QQbar(2).sqrt().interval_diameter(1e-10) 1.4142135623730950488? sage: QQbar(2).sqrt().interval_diameter(1e-30) 1.41421356237309504880168872420969807857? """ raise ValueError('diameter must be positive in interval_diameter')
def interval(self, field): r""" Given an interval field (real or complex, as appropriate) of precision `p`, compute an interval representation of self with ``diameter()`` at most `2^{-p}`; then round that representation into the given field. Here ``diameter()`` is relative diameter for intervals not containing 0, and absolute diameter for intervals that do contain 0; thus, if the returned interval does not contain 0, it has at least `p-1` good bits.
EXAMPLES::
sage: RIF64 = RealIntervalField(64) sage: x = AA(2).sqrt() sage: y = x*x sage: y = 1000 * y - 999 * y sage: y.interval_fast(RIF64) 2.000000000000000? sage: y.interval(RIF64) 2.000000000000000000? sage: CIF64 = ComplexIntervalField(64) sage: x = QQbar.zeta(11) sage: x.interval_fast(CIF64) 0.8412535328311811689? + 0.5406408174555975821?*I sage: x.interval(CIF64) 0.8412535328311811689? + 0.5406408174555975822?*I
The following implicitly use this method::
sage: RIF(AA(5).sqrt()) 2.236067977499790? sage: AA(-5).sqrt().interval(RIF) Traceback (most recent call last): ... TypeError: unable to convert 2.236067977499790?*I to real interval
TESTS:
Check that :trac:`20209` is fixed::
sage: RIF(QQbar(2).sqrt()) 1.414213562373095? sage: RIF(QQbar.gen() + QQbar(2).sqrt() - QQbar.gen()) 1.414213562373095? sage: RIF((QQbar.gen() + QQbar(2).sqrt() - QQbar.gen()).sqrt()) 1.189207115002722?
sage: RealIntervalField(129)(QQbar(3).sqrt()) 1.73205080756887729352744634150587236695? sage: RIF(QQbar.gen()) Traceback (most recent call last): ... TypeError: unable to convert I to real interval """ return field(self.real()) else: else:
_complex_mpfi_ = _real_mpfi_ = interval
def radical_expression(self): r""" Attempt to obtain a symbolic expression using radicals. If no exact symbolic expression can be found, the algebraic number will be returned without modification.
EXAMPLES::
sage: AA(1/sqrt(5)).radical_expression() sqrt(1/5) sage: AA(sqrt(5 + sqrt(5))).radical_expression() sqrt(sqrt(5) + 5) sage: QQbar.zeta(5).radical_expression() 1/4*sqrt(5) + 1/2*sqrt(-1/2*sqrt(5) - 5/2) - 1/4 sage: a = QQ[x](x^7 - x - 1).roots(AA, False)[0] sage: a.radical_expression() 1.112775684278706? sage: a.radical_expression().parent() == SR False sage: a = sorted(QQ[x](x^7-x-1).roots(QQbar, False), key=imag)[0] sage: a.radical_expression() -0.3636235193291805? - 0.9525611952610331?*I sage: QQbar.zeta(5).imag().radical_expression() 1/2*sqrt(1/2*sqrt(5) + 5/2) sage: AA(5/3).radical_expression() 5/3 sage: AA(5/3).radical_expression().parent() == SR True sage: QQbar(0).radical_expression() 0
TESTS:
In this example we find the correct answer despite the fact that multiple roots overlap with the current value. As a consequence, the precision of the evaluation will have to be increased.
::
sage: a = AA(sqrt(2) + 10^25) sage: p = a.minpoly() sage: v = a._value sage: f = ComplexIntervalField(v.prec()) sage: [f(b.rhs()).overlaps(f(v)) for b in SR(p).solve(x)] [True, True] sage: a.radical_expression() sqrt(2) + 10000000000000000000000000 """
# Adapted from NumberFieldElement._symbolic_() else:
class AlgebraicNumber(AlgebraicNumber_base): r""" The class for algebraic numbers (complex numbers which are the roots of a polynomial with integer coefficients). Much of its functionality is inherited from ``AlgebraicNumber_base``.
.. automethod:: _richcmp_ """ def __init__(self, x): r""" Initialize this AlgebraicNumber object.
EXAMPLES::
sage: t = QQbar.zeta(5) sage: type(t) <class 'sage.rings.qqbar.AlgebraicNumber'> """
def __reduce__(self): """ Add customized pickling support.
EXAMPLES::
sage: t = QQbar.zeta(5) sage: loads(dumps(t)) == t True """
def _richcmp_(self, other, op): r""" Compare two algebraic numbers, lexicographically. (That is, first compare the real components; if the real components are equal, compare the imaginary components.)
EXAMPLES::
sage: x = QQbar.zeta(3); x -0.500000000000000? + 0.866025403784439?*I sage: QQbar(-1) < x True sage: QQbar(-1/2) < x True sage: QQbar(0) > x True
One problem with this lexicographic ordering is the fact that if two algebraic numbers have the same real component, that real component has to be compared for exact equality, which can be a costly operation. For the special case where both numbers have the same minimal polynomial, that cost can be avoided, though (see :trac:`16964`)::
sage: x = polygen(ZZ) sage: p = 69721504*x^8 + 251777664*x^6 + 329532012*x^4 + 184429548*x^2 + 37344321 sage: sorted(p.roots(QQbar,False)) [-0.0221204634374361? - 1.090991904211621?*I, -0.0221204634374361? + 1.090991904211621?*I, -0.8088604911480535?*I, 0.?e-79 - 0.7598602580415435?*I, 0.?e-79 + 0.7598602580415435?*I, 0.8088604911480535?*I, 0.0221204634374361? - 1.090991904211621?*I, 0.0221204634374361? + 1.090991904211621?*I]
It also works for comparison of conjugate roots even in a degenerate situation where many roots have the same real part. In the following example, the polynomial ``p2`` is irreducible and all its roots have real part equal to `1`::
sage: p1 = x^8 + 74*x^7 + 2300*x^6 + 38928*x^5 + \ ....: 388193*x^4 + 2295312*x^3 + 7613898*x^2 + \ ....: 12066806*x + 5477001 sage: p2 = p1((x-1)^2) sage: sum(1 for r in p2.roots(CC,False) if abs(r.real() - 1) < 0.0001) 16 sage: r1 = QQbar.polynomial_root(p2, CIF(1, (-4.1,-4.0))) sage: r2 = QQbar.polynomial_root(p2, CIF(1, (4.0, 4.1))) sage: all([r1<r2, r1==r1, r2==r2, r2>r1]) True
Though, comparing roots which are not equal or conjugate is much slower because the algorithm needs to check the equality of the real parts::
sage: sorted(p2.roots(QQbar,False)) # long time - 3 secs [1.000000000000000? - 4.016778562562223?*I, 1.000000000000000? - 3.850538755978243?*I, 1.000000000000000? - 3.390564396412898?*I, ... 1.000000000000000? + 3.390564396412898?*I, 1.000000000000000? + 3.850538755978243?*I, 1.000000000000000? + 4.016778562562223?*I]
TESTS::
sage: QQbar.zeta(6) == QQbar(1/2 + I*sqrt(3)/2) True sage: QQbar(I) == QQbar(I * (2^100+1)/(2^100)) False sage: QQbar(2) == 2 True sage: QQbar(2) == GF(7)(2) False sage: GF(7)(2) in QQbar False
sage: QQbar.zeta(6) != QQbar(1/2 + I*sqrt(3)/2) False sage: QQbar(I) != QQbar(I * (2^100+1)/(2^100)) True sage: QQbar(2) != 2 False sage: QQbar(2) != GF(7)(2) True
sage: QQbar.zeta(3).real() == -1/2 True """ # note: we can assume that self is not other here
# some cheap and quite common tests where we can decide # equality or difference self._value.imag().overlaps(other._value.imag())): isinstance(od, ANExtensionElement) and sd._generator is od._generator):
# case 0: real parts are clearly distinct
# case 1: rationals return richcmp(sd._value, od._value, op)
# case 2: possibly equal or conjugate values # (this case happen a lot when sorting the roots of a real polynomial)
# case 3: try hard to compare real parts and imaginary parts
def _mpfr_(self, field): r""" Given a ``RealField``, compute a good approximation to self in that field. Works only if the imaginary component of self is exactly zero; otherwise it raises a ``ValueError``.
EXAMPLES::
sage: QQbar(sqrt(2))._mpfr_(RR) 1.41421356237309 sage: QQbar(-22/7)._mpfr_(RR) -3.14285714285714 sage: QQbar.zeta(3)._mpfr_(RR) Traceback (most recent call last): ... ValueError: Cannot coerce algebraic number with non-zero imaginary part to algebraic real """
def __float__(self): r""" Compute a good float approximation to self. Works only if the imaginary component of self is exactly zero; otherwise it raises a ``ValueError``.
EXAMPLES::
sage: QQbar(sqrt(2)).__float__() 1.414213562373095 sage: float(QQbar(-22/7)) -3.1428571428571432 sage: float(QQbar.zeta(3)) Traceback (most recent call last): ... ValueError: Cannot coerce algebraic number with non-zero imaginary part to algebraic real """
def __complex__(self): r""" Compute a good complex approximation to self.
EXAMPLES::
sage: QQbar(sqrt(2)).__complex__() (1.414213562373095+0j) sage: complex(QQbar.zeta(3)) (-0.5+0.8660254037844386j) """
def _complex_double_(self, cdf): r""" Compute a good approximation to self in CDF.
EXAMPLES::
sage: QQbar(sqrt(-5))._complex_double_(CDF) 2.23606797749979*I sage: CDF(QQbar.zeta(12)) 0.8660254037844386 + 0.5*I """
def _interval_fast(self, prec): r""" Shortcut for :meth:`AlgebraicNumber_base.interval_fast` which uses the complex interval field.
EXAMPLES::
sage: QQbar(sqrt(-5))._interval_fast(100) 2.236067977499789696409173...?*I """
def _integer_(self, ZZ=None): """ Return self as an Integer.
EXAMPLES::
sage: QQbar(0)._integer_() 0 sage: QQbar(0)._integer_().parent() Integer Ring sage: QQbar.zeta(6)._integer_() Traceback (most recent call last): ... ValueError: Cannot coerce algebraic number with non-zero imaginary part to algebraic real sage: QQbar(sqrt(17))._integer_() Traceback (most recent call last): ... ValueError: Cannot coerce non-integral Algebraic Real 4.123105625617660? to Integer sage: QQbar(sqrt(16))._integer_() 4 sage: v = QQbar(1 + I*sqrt(3))^5 + QQbar(16*sqrt(3)*I); v 16.00000000000000? + 0.?e-17*I sage: v._integer_() 16 """
def _rational_(self): """ Return self as a Rational.
EXAMPLES::
sage: QQbar(-22/7)._rational_() -22/7 sage: QQbar(3)._rational_().parent() Rational Field sage: (QQbar.zeta(7)^3)._rational_() Traceback (most recent call last): ... ValueError: Cannot coerce algebraic number with non-zero imaginary part to algebraic real sage: QQbar(sqrt(2))._rational_() Traceback (most recent call last): ... ValueError: Cannot coerce irrational Algebraic Real 1.414213562373095? to Rational sage: v1 = QQbar(1/3 + I*sqrt(5))^7 sage: v2 = QQbar((100336/729*golden_ratio - 50168/729)*I) sage: v = v1 + v2; v -259.6909007773206? + 0.?e-15*I sage: v._rational_() -567944/2187 """
def real(self): r""" Return the real part of self.
EXAMPLES::
sage: QQbar.zeta(5).real() 0.3090169943749474? """
def imag(self): r""" Return the imaginary part of self.
EXAMPLES::
sage: QQbar.zeta(7).imag() 0.7818314824680299? """
def conjugate(self): """ Returns the complex conjugate of self.
EXAMPLES::
sage: QQbar(3 + 4*I).conjugate() 3 - 4*I sage: QQbar.zeta(7).conjugate() 0.6234898018587335? - 0.7818314824680299?*I sage: QQbar.zeta(7) + QQbar.zeta(7).conjugate() 1.246979603717467? + 0.?e-18*I """
def norm(self): r""" Returns ``self * self.conjugate()``. This is the algebraic definition of norm, if we view ``QQbar`` as ``AA[I]``.
EXAMPLES::
sage: QQbar(3 + 4*I).norm() 25 sage: type(QQbar(I).norm()) <class 'sage.rings.qqbar.AlgebraicReal'> sage: QQbar.zeta(1007).norm() 1.000000000000000? """
def interval_exact(self, field): r""" Given a ``ComplexIntervalField``, compute the best possible approximation of this number in that field. Note that if either the real or imaginary parts of this number are sufficiently close to some floating-point number (and, in particular, if either is exactly representable in floating-point), then this will trigger exact computation, which may be very slow.
EXAMPLES::
sage: a = QQbar(I).sqrt(); a 0.7071067811865475? + 0.7071067811865475?*I sage: a.interval_exact(CIF) 0.7071067811865475? + 0.7071067811865475?*I sage: b = QQbar((1+I)*sqrt(2)/2) sage: (a - b).interval(CIF) 0.?e-19 + 0.?e-18*I sage: (a - b).interval_exact(CIF) 0 """ raise ValueError("AlgebraicNumber interval_exact requires a ComplexIntervalField")
def _complex_mpfr_field_(self, field): r""" Compute an approximation to self in the given field, which must be a complex field.
EXAMPLES::
sage: a = QQbar(1 + I).sqrt() sage: t = a._complex_mpfr_field_(ComplexField(100)); t 1.0986841134678099660398011952 + 0.45508986056222734130435775782*I sage: parent(t) Complex Field with 100 bits of precision """
def complex_number(self, field): r""" Given the complex field ``field`` compute an accurate approximation of this element in that field.
The approximation will be off by at most two ulp's in each component, except for components which are very close to zero, which will have an absolute error at most `2^{-prec+1}` where `prec` is the precision of the field.
EXAMPLES::
sage: a = QQbar.zeta(5) sage: a.complex_number(CC) 0.309016994374947 + 0.951056516295154*I
sage: b = QQbar(2).sqrt() + QQbar(3).sqrt() * QQbar.gen() sage: b.complex_number(ComplexField(128)) 1.4142135623730950488016887242096980786 + 1.7320508075688772935274463415058723669*I """
def complex_exact(self, field): r""" Given a ``ComplexField``, return the best possible approximation of this number in that field. Note that if either component is sufficiently close to the halfway point between two floating-point numbers in the corresponding ``RealField``, then this will trigger exact computation, which may be very slow.
EXAMPLES::
sage: a = QQbar.zeta(9) + QQbar(I) + QQbar.zeta(9).conjugate(); a 1.532088886237957? + 1.000000000000000?*I sage: a.complex_exact(CIF) 1.532088886237957? + 1*I """
def multiplicative_order(self): r""" Compute the multiplicative order of this algebraic real number. That is, find the smallest positive integer `n` such that `x^n = 1`. If there is no such `n`, returns ``+Infinity``.
We first check that ``abs(x)`` is very close to 1. If so, we compute `x` exactly and examine its argument.
EXAMPLES::
sage: QQbar(-sqrt(3)/2 - I/2).multiplicative_order() 12 sage: QQbar(1).multiplicative_order() 1 sage: QQbar(-I).multiplicative_order() 4 sage: QQbar(707/1000 + 707/1000*I).multiplicative_order() +Infinity sage: QQbar(3/5 + 4/5*I).multiplicative_order() +Infinity """ return infinity.infinity
def rational_argument(self): r""" Returns the argument of self, divided by `2\pi`, as long as this result is rational. Otherwise returns None. Always triggers exact computation.
EXAMPLES::
sage: QQbar((1+I)*(sqrt(2)+sqrt(5))).rational_argument() 1/8 sage: QQbar(-1 + I*sqrt(3)).rational_argument() 1/3 sage: QQbar(-1 - I*sqrt(3)).rational_argument() -1/3 sage: QQbar(3+4*I).rational_argument() is None True sage: (QQbar(2)**(1/5) * QQbar.zeta(7)**2).rational_argument() 2/7 sage: (QQbar.zeta(73)**5).rational_argument() 5/73 sage: (QQbar.zeta(3)^65536).rational_argument() 1/3 """ # This always triggers exact computation. An alternate method # could almost always avoid exact computation when the result # is None: if we can compute an upper bound on the degree of # this algebraic number without exact computation, we can use # the method of ANExtensionElement.rational_argument().
# Even a very loose upper bound would suffice; for instance, # an upper bound of 2^100, when the true degree was 8, would # still be efficient.
def _pow_(self, other): """ Powering for ``QQbar(1)``.
EXAMPLES::
sage: QQbar(1) ^ QQbar(sqrt(2)) 1 sage: 1 ^ QQbar(sqrt(2)) 1 sage: QQbar(2) ^ QQbar(2) Traceback (most recent call last): ... TypeError: unsupported operand parent(s) for ^: 'Algebraic Field' and 'Algebraic Field' sage: AA(1) ^ AA(1) Traceback (most recent call last): ... TypeError: unsupported operand parent(s) for ^: 'Algebraic Real Field' and 'Algebraic Real Field' """ # For some crazy unspecified reason, we must allow this if the # base is QQbar(1). See Trac #22120 and #24490.
class AlgebraicReal(AlgebraicNumber_base): r""" A real algebraic number.
.. automethod:: _richcmp_ """ def __init__(self, x): """ Create an algebraic real from x, possibly taking the real part of x.
TESTS:
Both of the following examples, from :trac:`11728`, trigger taking the real part below. This is necessary because sometimes a very small (e.g., 1e-17) complex part appears in a complex interval used to create an AlgebraicReal.::
sage: a = QQbar((-1)^(1/4)); b = AA(a^3-a); t = b.as_number_field_element() sage: b*1 -1.414213562373095? """
def _ensure_real(self): """ This is used internally by some methods to check if self._value is a complex interval, and if so, take the real part.
EXAMPLES::
sage: a = QQbar((-1)^(1/4)); b = AA(a^3-a); b._value -1.4142135623730950488? sage: b._value = a._value; b._value 0.7071067811865475244? + 0.7071067811865475244?*I sage: b._ensure_real() sage: b._value 0.7071067811865475244? sage: type(b._value) <type 'sage.rings.real_mpfi.RealIntervalFieldElement'> """
def _more_precision(self): """ Recompute the interval bounding this number with higher-precision interval arithmetic.
EXAMPLES::
sage: a = QQbar(sqrt(2)) sage: a._more_precision()
TESTS:
We have to ensure after doing this that self._value is still real which isn't the case without calling _ensure_real (see :trac:`11728`)::
sage: P = AA['x'](1+x^4); a1,a2 = P.factor()[0][0],P.factor()[1][0]; a1*a2 x^4 + 1.000000000000000? sage: a1,a2 (x^2 - 1.414213562373095?*x + 1, x^2 + 1.414213562373095?*x + 1) sage: a1*a2 x^4 + 1 """
def __reduce__(self): """ Add customized pickling support.
EXAMPLES::
sage: t = AA(sqrt(2)) sage: loads(dumps(t)) == t True """
def _richcmp_(self, other, op): """ Compare two algebraic reals.
EXAMPLES::
sage: AA(2).sqrt() < AA(3).sqrt() True sage: ((5+AA(5).sqrt())/2).sqrt() == 2*QQbar.zeta(5).imag() True sage: AA(3).sqrt() + AA(2).sqrt() < 3 False
TESTS::
sage: AA(golden_ratio) < AA(sqrt(5)) True sage: AA(golden_ratio) == AA((sqrt(5)+1)/2) True sage: AA(7) >= AA(50/7) False """ # note: we can assume that self is not other here
# some cheap and quite common tests where we can decide equality or difference type(od) is ANExtensionElement and sd._generator is od._generator): return op == op_NE
# case 0: real parts are clearly distinct
# case 1: rationals
def _integer_(self, Z=None): """ Return self as an Integer.
EXAMPLES::
sage: AA(42)._integer_() 42 sage: AA(42)._integer_().parent() Integer Ring sage: AA(golden_ratio)._integer_() Traceback (most recent call last): ... ValueError: Cannot coerce non-integral Algebraic Real 1.618033988749895? to Integer sage: (AA(golden_ratio)^10 + AA(1-golden_ratio)^10)._integer_() 123 sage: AA(-22/7)._integer_() Traceback (most recent call last): ... ValueError: Cannot coerce non-integral Algebraic Real -22/7 to Integer """ # The value is known to be non-integral.
def _floor_ceil(self, method): r""" Helper method used by :meth:`floor()`, :meth:`ceil()`, :meth:`round()`, and :meth:`trunc()`.
TESTS::
sage: x = polygen(QQ) sage: a = AA.polynomial_root(x^5 - (1-2^(-80)), RIF((0,2))) sage: b = AA.polynomial_root(x^5 - (1+2^(-80)), RIF((0,2))) sage: two = (a+b)^5 - 5*(a^4*b+a*b^4) - 10*(a^3*b^2+a^2*b^3) sage: one_half = 1/two sage: [[z.floor(), z.ceil(), z.round(), z.trunc()] # indirect doctest ....: for z in [a, -a, b, -b, 6*(a+two), ....: AA(0), AA(1), AA(-1), AA(1/2), AA(-1/2)]] [[0, 1, 1, 0], [-1, 0, -1, 0], [1, 2, 1, 1], [-2, -1, -1, -1], [17, 18, 18, 17], [0, 0, 0, 0], [1, 1, 1, 1], [-1, -1, -1, -1], [0, 1, 1, 0], [-1, 0, -1, 0]] sage: [[z.floor(), z.ceil(), z.trunc()] for z in [two, a*b]] # long time [[2, 2, 2], [0, 1, 0]] sage: [one_half.round(), (-one_half).round()] # long time [1, -1] """ # field elements are irrational by construction except (ValueError, TypeError): pass
def floor(self): r""" Return the largest integer not greater than ``self``.
EXAMPLES::
sage: AA(sqrt(2)).floor() 1 sage: AA(-sqrt(2)).floor() -2 sage: AA(42).floor() 42
TESTS:
Check that :trac:`15501` is fixed::
sage: a = QQbar((-1)^(1/4)).real() sage: (floor(a-a) + a).parent() Algebraic Real Field """
def ceil(self): r""" Return the smallest integer not smaller than ``self``.
EXAMPLES::
sage: AA(sqrt(2)).ceil() 2 sage: AA(-sqrt(2)).ceil() -1 sage: AA(42).ceil() 42 """
def round(self): r""" Round ``self`` to the nearest integer.
EXAMPLES::
sage: AA(sqrt(2)).round() 1 sage: AA(1/2).round() 1 sage: AA(-1/2).round() -1 """
def trunc(self): r""" Round ``self`` to the nearest integer toward zero.
EXAMPLES::
sage: AA(sqrt(2)).trunc() 1 sage: AA(-sqrt(2)).trunc() -1 sage: AA(1).trunc() 1 sage: AA(-1).trunc() -1 """
def _rational_(self): """ Return self as a Rational.
EXAMPLES::
sage: AA(42)._rational_().parent() Rational Field sage: AA(-22/7)._rational_() -22/7 sage: AA(sqrt(7))._rational_() Traceback (most recent call last): ... ValueError: Cannot coerce irrational Algebraic Real 2.645751311064591? to Rational sage: v = AA(1/2 + sqrt(2))^3 - AA(11/4*sqrt(2)); v 3.125000000000000? sage: v._rational_() 25/8 """
def real(self): """ Returns the real part of this algebraic real (so it always returns self).
EXAMPLES::
sage: a = AA(sqrt(2) + sqrt(3)) sage: a.real() 3.146264369941973? sage: a.real() is a True """
def imag(self): """ Returns the imaginary part of this algebraic real (so it always returns 0).
EXAMPLES::
sage: a = AA(sqrt(2) + sqrt(3)) sage: a.imag() 0 sage: parent(a.imag()) Algebraic Real Field """
def conjugate(self): """ Returns the complex conjugate of self, i.e. returns itself.
EXAMPLES::
sage: a = AA(sqrt(2) + sqrt(3)) sage: a.conjugate() 3.146264369941973? sage: a.conjugate() is a True """
def sign(self): """ Compute the sign of this algebraic number (return -1 if negative, 0 if zero, or 1 if positive).
Computes an interval enclosing this number using 128-bit interval arithmetic; if this interval includes 0, then fall back to exact computation (which can be very slow).
EXAMPLES::
sage: AA(-5).nth_root(7).sign() -1 sage: (AA(2).sqrt() - AA(2).sqrt()).sign() 0
sage: a = AA(2).sqrt() + AA(3).sqrt() - 58114382797550084497/18470915334626475921 sage: a.sign() 1 sage: b = AA(2).sqrt() + AA(3).sqrt() - 2602510228533039296408/827174681630786895911 sage: b.sign() -1
sage: c = AA(5)**(1/3) - 1437624125539676934786/840727688792155114277 sage: c.sign() 1
sage: (((a+b)*(a+c)*(b+c))**9 / (a*b*c)).sign() 1 sage: (a-b).sign() 1 sage: (b-a).sign() -1 sage: (a*b).sign() -1 sage: ((a*b).abs() + a).sign() 1 sage: (a*b - b*a).sign() 0 """
# All field elements are irrational by construction # (the ANExtensionElement constructor will return an ANRational # instead, if the number is actually rational). # An irrational number must eventually be different from 0 else: c = 1 if bool(sd._arg) else 0 if not c: self._set_descr(ANRational(QQ.zero())) return c return -(sd._arg.sign()) return sd._arg.sign()
# OK, we'll try adding precision one more time return self._value.unique_sign()
# Sigh...
def _interval_fast(self, prec): r""" Compute an approximation to this ``AlgebraicReal`` object in a real interval field of precision prec.
EXAMPLES::
sage: t = AA(sqrt(7)) sage: t._interval_fast(100) 2.64575131106459059050161575364? """
def interval_exact(self, field): """ Given a ``RealIntervalField``, compute the best possible approximation of this number in that field. Note that if this number is sufficiently close to some floating-point number (and, in particular, if this number is exactly representable in floating-point), then this will trigger exact computation, which may be very slow.
EXAMPLES::
sage: x = AA(2).sqrt() sage: y = x*x sage: x.interval(RIF) 1.414213562373095? sage: x.interval_exact(RIF) 1.414213562373095? sage: y.interval(RIF) 2.000000000000000? sage: y.interval_exact(RIF) 2 sage: z = 1 + AA(2).sqrt() / 2^200 sage: z.interval(RIF) 1.000000000000001? sage: z.interval_exact(RIF) 1.000000000000001? """ # p==precise; pr==precise rounded prbot < pbot and ptop < prtop):
# Even 40 extra bits of precision aren't enough to prove that # self is not an exactly representable float. # p==precise; pr==precise rounded prbot < pbot and ptop < prtop):
def real_number(self, field): """ Given a ``RealField``, compute a good approximation to self in that field. The approximation will be off by at most two ulp's, except for numbers which are very close to 0, which will have an absolute error at most ``2**(-(field.prec()-1))``. Also, the rounding mode of the field is respected.
EXAMPLES::
sage: x = AA(2).sqrt()^2 sage: x.real_number(RR) 2.00000000000000 sage: x.real_number(RealField(53, rnd='RNDD')) 1.99999999999999 sage: x.real_number(RealField(53, rnd='RNDU')) 2.00000000000001 sage: x.real_number(RealField(53, rnd='RNDZ')) 1.99999999999999 sage: (-x).real_number(RR) -2.00000000000000 sage: (-x).real_number(RealField(53, rnd='RNDD')) -2.00000000000001 sage: (-x).real_number(RealField(53, rnd='RNDU')) -1.99999999999999 sage: (-x).real_number(RealField(53, rnd='RNDZ')) -1.99999999999999 sage: (x-2).real_number(RR) 5.42101086242752e-20 sage: (x-2).real_number(RealField(53, rnd='RNDD')) -1.08420217248551e-19 sage: (x-2).real_number(RealField(53, rnd='RNDU')) 2.16840434497101e-19 sage: (x-2).real_number(RealField(53, rnd='RNDZ')) 0.000000000000000 sage: y = AA(2).sqrt() sage: y.real_number(RR) 1.41421356237309 sage: y.real_number(RealField(53, rnd='RNDD')) 1.41421356237309 sage: y.real_number(RealField(53, rnd='RNDU')) 1.41421356237310 sage: y.real_number(RealField(53, rnd='RNDZ')) 1.41421356237309 """
_mpfr_ = real_number
def __float__(self): r""" Compute a good float approximation to self.
EXAMPLES::
sage: AA(golden_ratio).__float__() 1.618033988749895 sage: float(AA(sqrt(11))) 3.3166247903554 """
def _complex_mpfr_field_(self, field): r""" Compute an approximation to this ``AlgebraicReal`` in the given field, which may be an interval field (in which case ``self.interval()`` is called) or any other real number field (in which case ``self.real_number()`` is called.
Note that the field ``field`` should be a *complex* field (whose ``_real_field()`` method will be called to obtain a real subfield.)
EXAMPLES::
sage: AA(golden_ratio)._complex_mpfr_field_(ComplexIntervalField(100)) 1.618033988749894848204586834365? sage: AA(golden_ratio)._complex_mpfr_field_(ComplexField(100)) 1.6180339887498948482045868344 """ else:
def real_exact(self, field): r""" Given a ``RealField``, compute the best possible approximation of this number in that field. Note that if this number is sufficiently close to the halfway point between two floating-point numbers in the field (for the default round-to-nearest mode) or if the number is sufficiently close to a floating-point number in the field (for directed rounding modes), then this will trigger exact computation, which may be very slow.
The rounding mode of the field is respected.
EXAMPLES::
sage: x = AA(2).sqrt()^2 sage: x.real_exact(RR) 2.00000000000000 sage: x.real_exact(RealField(53, rnd='RNDD')) 2.00000000000000 sage: x.real_exact(RealField(53, rnd='RNDU')) 2.00000000000000 sage: x.real_exact(RealField(53, rnd='RNDZ')) 2.00000000000000 sage: (-x).real_exact(RR) -2.00000000000000 sage: (-x).real_exact(RealField(53, rnd='RNDD')) -2.00000000000000 sage: (-x).real_exact(RealField(53, rnd='RNDU')) -2.00000000000000 sage: (-x).real_exact(RealField(53, rnd='RNDZ')) -2.00000000000000 sage: y = (x-2).real_exact(RR).abs() sage: y == 0.0 or y == -0.0 # the sign of 0.0 is not significant in MPFI True sage: y = (x-2).real_exact(RealField(53, rnd='RNDD')) sage: y == 0.0 or y == -0.0 # same as above True sage: y = (x-2).real_exact(RealField(53, rnd='RNDU')) sage: y == 0.0 or y == -0.0 # idem True sage: y = (x-2).real_exact(RealField(53, rnd='RNDZ')) sage: y == 0.0 or y == -0.0 # ibidem True sage: y = AA(2).sqrt() sage: y.real_exact(RR) 1.41421356237310 sage: y.real_exact(RealField(53, rnd='RNDD')) 1.41421356237309 sage: y.real_exact(RealField(53, rnd='RNDU')) 1.41421356237310 sage: y.real_exact(RealField(53, rnd='RNDZ')) 1.41421356237309 """
# Even 40 extra bits of precision aren't enough to determine the # answer.
# Call the largest floating-point number <= self 'x'. Then # val may be [x .. x], [x .. x + 1/2 ulp], # [x + 1/2 ulp .. x + 1/2 ulp], or [x + 1/2 ulp .. x + 1 ulp]; # in the second and fourth cases, the true value is not equal # to either of the interval endpoints.
# Now mid may be x, x + 1/4 ulp, x + 1/2 ulp, or x + 3/4 ulp; in # the first and third cases, mid is the exact, true value of self; # in the second and fourth cases, self is close to mid, and is # neither x, x + 1/2 ulp, nor x + 1 ulp.
# In all of these cases, in all rounding modes, the rounded value # of mid is the same as the rounded value of self.
class AlgebraicNumberPowQQAction(Action): """ Implement powering of an algebraic number (an element of ``QQbar`` or ``AA``) by a rational.
This is always a right action.
INPUT:
- ``G`` -- must be ``QQ``
- ``S`` -- the parent on which to act, either ``AA`` or ``QQbar``.
.. NOTE::
To compute ``x ^ (a/b)``, we take the `b`'th root of `x`; then we take that to the `a`'th power. If `x` is a negative algebraic real and `b` is odd, take the real `b`'th root; otherwise take the principal `b`'th root.
EXAMPLES:
In ``QQbar``::
sage: QQbar(2)^(1/2) 1.414213562373095? sage: QQbar(8)^(2/3) 4 sage: QQbar(8)^(2/3) == 4 True sage: x = polygen(QQbar) sage: phi = QQbar.polynomial_root(x^2 - x - 1, RIF(1, 2)) sage: tau = QQbar.polynomial_root(x^2 - x - 1, RIF(-1, 0)) sage: rt5 = QQbar(5)^(1/2) sage: phi^10 / rt5 55.00363612324742? sage: tau^10 / rt5 0.003636123247413266? sage: (phi^10 - tau^10) / rt5 55.00000000000000? sage: (phi^10 - tau^10) / rt5 == fibonacci(10) True sage: (phi^50 - tau^50) / rt5 == fibonacci(50) True sage: QQbar(-8)^(1/3) 1.000000000000000? + 1.732050807568878?*I sage: (QQbar(-8)^(1/3))^3 -8 sage: QQbar(32)^(1/5) 2 sage: a = QQbar.zeta(7)^(1/3); a 0.9555728057861407? + 0.2947551744109043?*I sage: a == QQbar.zeta(21) True sage: QQbar.zeta(7)^6 0.6234898018587335? - 0.7818314824680299?*I sage: (QQbar.zeta(7)^6)^(1/3) * QQbar.zeta(21) 1.000000000000000? + 0.?e-17*I
In ``AA``::
sage: AA(2)^(1/2) 1.414213562373095? sage: AA(8)^(2/3) 4 sage: AA(8)^(2/3) == 4 True sage: x = polygen(AA) sage: phi = AA.polynomial_root(x^2 - x - 1, RIF(0, 2)) sage: tau = AA.polynomial_root(x^2 - x - 1, RIF(-2, 0)) sage: rt5 = AA(5)^(1/2) sage: phi^10 / rt5 55.00363612324742? sage: tau^10 / rt5 0.003636123247413266? sage: (phi^10 - tau^10) / rt5 55.00000000000000? sage: (phi^10 - tau^10) / rt5 == fibonacci(10) True sage: (phi^50 - tau^50) / rt5 == fibonacci(50) True
TESTS::
sage: AA(-8)^(1/3) -2 sage: AA(-8)^(2/3) 4 sage: AA(32)^(3/5) 8 sage: AA(-16)^(1/2) 4*I sage: AA(-16)^(1/4) 1.414213562373095? + 1.414213562373095?*I sage: AA(-16)^(1/4)/QQbar.zeta(8) 2
We check that :trac:`7859` is fixed::
sage: (AA(2)^(1/2)-AA(2)^(1/2))^(1/2) 0 """ def __init__(self, G, S): """ EXAMPLES::
sage: from sage.rings.qqbar import AlgebraicNumberPowQQAction sage: act = AlgebraicNumberPowQQAction(QQ, AA); act Right Rational Powering by Rational Field on Algebraic Real Field sage: act(AA(-2), 1/3) -1.259921049894873?
::
sage: act = AlgebraicNumberPowQQAction(QQ, QQbar); act Right Rational Powering by Rational Field on Algebraic Field sage: act(QQbar(-2), 1/3) 0.6299605249474365? + 1.091123635971722?*I """
def _call_(self, x, e): r""" Return the power ``x ^ e``.
INPUT:
- ``x`` -- an algebraic number
- ``e`` -- a rational number """
# Parent of the result
# First, check for exact roots. else:
# Result lies in AA else:
# Result lies in QQbar
# Determine whether arg(x) equals pi. # We know that x.real() < 0, since x._value # crosses the negative real line and x._value # is known to be non-zero. isgn = x.imag().sign() val = x._value argument = val.argument() if isgn == 0: argument = argument.parent().pi() argument_is_pi = True elif isgn > 0: if argument < 0: argument = argument + 2 * argument.parent().pi() else: if argument > 0: argument = argument - 2 * argument.parent().pi() else:
val = x._interval_fast(prec)
target_abs = abs(val) ** e argument = val.argument() if argument_is_pi: argument = argument.parent().pi() target_arg = argument * e
else: target_arg.sin() * target_abs)
def _repr_name_(self):
class ANRational(ANDescr): r""" The subclass of ``ANDescr`` that represents an arbitrary rational. This class is private, and should not be used directly. """
def __init__(self, x): """ TESTS::
sage: polygen(QQbar) / int(3) 1/3*x sage: QQbar(int(7)) / QQbar(long(2)) 7/2 """ sage.rings.rational.Rational)): else: raise TypeError("Illegal initializer for algebraic number rational")
def __reduce__(self): """ Add customized pickling support.
EXAMPLES::
sage: t = AA(5/2); type(t._descr) <class 'sage.rings.qqbar.ANRational'> sage: loads(dumps(t)) == t True """
def _repr_(self): r""" String representation of self.
EXAMPLES::
sage: QQbar(2/3)._repr_() '2/3' """
def handle_sage_input(self, sib, coerce, is_qqbar): r""" Produce an expression which will reproduce this value when evaluated, and an indication of whether this value is worth sharing (always False, for rationals).
EXAMPLES::
sage: sage_input(QQbar(22/7), verify=True) # Verified QQbar(22/7) sage: sage_input(-AA(3)/5, verify=True) # Verified AA(-3/5) sage: sage_input(vector(AA, (0, 1/2, 1/3)), verify=True) # Verified vector(AA, [0, 1/2, 1/3]) sage: from sage.rings.qqbar import * sage: from sage.misc.sage_input import SageInputBuilder sage: sib = SageInputBuilder() sage: rat = ANRational(9/10) sage: rat.handle_sage_input(sib, False, True) ({call: {atomic:QQbar}({binop:/ {atomic:9} {atomic:10}})}, False) """
def _interval_fast(self, prec): r""" Return an approximation to self in a real interval field of precision prec.
EXAMPLES::
sage: QQbar(355/113)._descr._interval_fast(30) 3.14159292? """
def generator(self): r""" Return an :class:`AlgebraicGenerator` object associated to this element. Returns the trivial generator, since self is rational.
EXAMPLES::
sage: QQbar(0)._descr.generator() Trivial generator """
def is_complex(self): r""" Return False, since rational numbers are real
EXAMPLES::
sage: QQbar(1/7)._descr.is_complex() False """
def exactify(self): r""" Calculate self exactly. Since self is a rational number, return self.
EXAMPLES::
sage: a = QQbar(1/3)._descr sage: a.exactify() is a True """
def is_simple(self): """ Checks whether this descriptor represents a value with the same algebraic degree as the number field associated with the descriptor.
This is always true for rational numbers.
EXAMPLES::
sage: AA(1/2)._descr.is_simple() True """
def minpoly(self): r""" Return the min poly of self over `\QQ`.
EXAMPLES::
sage: QQbar(7)._descr.minpoly() x - 7 """
def neg(self, n): r""" Negation of self.
EXAMPLES::
sage: a = QQbar(3) sage: b = a._descr sage: type(b) <class 'sage.rings.qqbar.ANRational'> sage: b.neg(a) -3 """
def invert(self, n): r""" 1/self.
EXAMPLES::
sage: a = QQbar(3) sage: b = a._descr sage: b.invert(a) 1/3 """
def abs(self, n): r""" Absolute value of self.
EXAMPLES::
sage: a = QQbar(3) sage: b = a._descr sage: b.abs(a) 3 """
def rational_argument(self, n): r""" Return the argument of self divided by `2 \pi`, or ``None`` if this element is 0.
EXAMPLES::
sage: QQbar(3)._descr.rational_argument(None) 0 sage: QQbar(-3)._descr.rational_argument(None) 1/2 sage: QQbar(0)._descr.rational_argument(None) is None True """
def angle(self): r""" Return a rational number `q \in (-1/2, 1/2]` such that ``self`` is a rational multiple of `e^{2\pi i q}`. Always returns 0, since this element is rational.
EXAMPLES::
sage: QQbar(3)._descr.angle() 0 sage: QQbar(-3)._descr.angle() 0 sage: QQbar(0)._descr.angle() 0 """
def scale(self): r""" Return a rational number `r` such that ``self`` is equal to `r e^{2 \pi i q}` for some `q \in (-1/2, 1/2]`. In other words, just return self as a rational number.
EXAMPLES::
sage: QQbar(-3)._descr.scale() -3 """
def is_AlgebraicReal(x): r""" Test if ``x`` is an instance of :class:`~AlgebraicReal`. For internal use.
EXAMPLES::
sage: from sage.rings.qqbar import is_AlgebraicReal sage: is_AlgebraicReal(AA(sqrt(2))) True sage: is_AlgebraicReal(QQbar(sqrt(2))) False sage: is_AlgebraicReal("spam") False """
def is_AlgebraicNumber(x): r""" Test if ``x`` is an instance of :class:`~AlgebraicNumber`. For internal use.
EXAMPLES::
sage: from sage.rings.qqbar import is_AlgebraicNumber sage: is_AlgebraicNumber(AA(sqrt(2))) False sage: is_AlgebraicNumber(QQbar(sqrt(2))) True sage: is_AlgebraicNumber("spam") False """
QQbarPoly = PolynomialRing(QQbar, 'x') AAPoly = PolynomialRing(AA, 'x')
class AlgebraicPolynomialTracker(SageObject): r""" Keeps track of a polynomial used for algebraic numbers.
If multiple algebraic numbers are created as roots of a single polynomial, this allows the polynomial and information about the polynomial to be shared. This reduces work if the polynomial must be recomputed at higher precision, or if it must be factored.
This class is private, and should only be constructed by ``AA.common_polynomial()`` or ``QQbar.common_polynomial()``, and should only be used as an argument to ``AA.polynomial_root()`` or ``QQbar.polynomial_root()``. (It doesn't matter whether you create the common polynomial with ``AA.common_polynomial()`` or ``QQbar.common_polynomial()``.)
EXAMPLES::
sage: x = polygen(QQbar) sage: P = QQbar.common_polynomial(x^2 - x - 1) sage: P x^2 - x - 1 sage: QQbar.polynomial_root(P, RIF(1, 2)) 1.618033988749895? """
def __init__(self, poly): r""" Initialize this AlgebraicPolynomialTracker object.
EXAMPLES::
sage: x = polygen(QQbar) sage: P = QQbar.common_polynomial(x^2 - x - 1) sage: type(P) # indirect doctest <class 'sage.rings.qqbar.AlgebraicPolynomialTracker'> """ raise ValueError("Trying to create AlgebraicPolynomialTracker on non-Polynomial") else:
def __reduce__(self): """ Add customized pickling support.
EXAMPLES::
sage: x = polygen(QQ) sage: v = (x^2 - x - 1).roots(ring=AA, multiplicities=False)[1] sage: type(v._descr._poly) <class 'sage.rings.qqbar.AlgebraicPolynomialTracker'> sage: loads(dumps(v)) == v True """
def _sage_input_(self, sib, coerce): r""" Produce an expression which will reproduce this value when evaluated.
EXAMPLES::
sage: x = polygen(QQ) sage: sage_input(AA.common_polynomial(x^3 - 7)) R.<x> = AA[] AA.common_polynomial(x^3 - 7) sage: x = polygen(AA) sage: p = sqrt(AA(2)) * x^2 - sqrt(AA(3)) sage: cp = AA.common_polynomial(p) sage: sage_input((cp, cp)) R.<x> = AA[] cp = AA.common_polynomial(AA.polynomial_root(AA.common_polynomial(x^2 - 2), RIF(RR(1.4142135623730949), RR(1.4142135623730951)))*x^2 - AA.polynomial_root(AA.common_polynomial(x^2 - 3), RIF(RR(1.7320508075688772), RR(1.7320508075688774)))) (cp, cp) sage: from sage.misc.sage_input import SageInputBuilder sage: sib = SageInputBuilder() sage: cp._sage_input_(sib, False) {call: {getattr: {atomic:AA}.common_polynomial}({binop:- {binop:* {call: {getattr: {atomic:AA}.polynomial_root}({call: {getattr: {atomic:AA}.common_polynomial}({binop:- {binop:** {gen:x {constr_parent: {subscr: {atomic:AA}[{atomic:'x'}]} with gens: ('x',)}} {atomic:2}} {atomic:2}})}, {call: {atomic:RIF}({call: {atomic:RR}({atomic:1.4142135623730949})}, {call: {atomic:RR}({atomic:1.4142135623730951})})})} {binop:** {gen:x {constr_parent: {subscr: {atomic:AA}[{atomic:'x'}]} with gens: ('x',)}} {atomic:2}}} {call: {getattr: {atomic:AA}.polynomial_root}({call: {getattr: {atomic:AA}.common_polynomial}({binop:- {binop:** {gen:x {constr_parent: {subscr: {atomic:AA}[{atomic:'x'}]} with gens: ('x',)}} {atomic:2}} {atomic:3}})}, {call: {atomic:RIF}({call: {atomic:RR}({atomic:1.7320508075688772})}, {call: {atomic:RR}({atomic:1.7320508075688774})})})}})} """ # XXX It would be nicer to skip the "AA.common_polynomial()" # wrapper if the polynomial is not actually shared. But # sage_input.py isn't quite that generic.
def _repr_(self): r""" String representation of self.
EXAMPLES::
sage: x = polygen(QQ) sage: AA.common_polynomial(x^3 - 7)._repr_() 'x^3 - 7' """
def poly(self): r""" Return the underlying polynomial of self.
EXAMPLES::
sage: x = polygen(QQ); f = x^3 - 7 sage: g = AA.common_polynomial(f) sage: g.poly() == f True """
def is_complex(self): r""" Return True if the coefficients of this polynomial are non-real.
EXAMPLES::
sage: x = polygen(QQ); f = x^3 - 7 sage: g = AA.common_polynomial(f) sage: g.is_complex() False sage: QQbar.common_polynomial(x^3 - QQbar(I)).is_complex() True """
def complex_roots(self, prec, multiplicity): """ Find the roots of self in the complex field to precision prec.
EXAMPLES::
sage: x = polygen(ZZ) sage: cp = AA.common_polynomial(x^4 - 2)
Note that the precision is not guaranteed to find the tightest possible interval since complex_roots() depends on the underlying BLAS implementation. ::
sage: cp.complex_roots(30, 1) [-1.18920711500272...?, 1.189207115002721?, -1.189207115002721?*I, 1.189207115002721?*I] """
p = p.derivative()
def exactify(self): """ Compute a common field that holds all of the algebraic coefficients of this polynomial, then factor the polynomial over that field. Store the factors for later use (ignoring multiplicity).
EXAMPLES::
sage: x = polygen(AA) sage: p = sqrt(AA(2)) * x^2 - sqrt(AA(3)) sage: cp = AA.common_polynomial(p) sage: cp._exact False sage: cp.exactify() sage: cp._exact True """
else:
def factors(self): r""" EXAMPLES::
sage: x=polygen(QQ); f=QQbar.common_polynomial(x^4 + 4) sage: f.factors() [y^2 - 2*y + 2, y^2 + 2*y + 2] """
def generator(self): r""" Return an :class:`AlgebraicGenerator` for a number field containing all the coefficients of self.
EXAMPLES::
sage: x = polygen(AA) sage: p = sqrt(AA(2)) * x^2 - sqrt(AA(3)) sage: cp = AA.common_polynomial(p) sage: cp.generator() Number Field in a with defining polynomial y^4 - 4*y^2 + 1 with a in 1.931851652578137? """
class ANRoot(ANDescr): """ The subclass of ``ANDescr`` that represents a particular root of a polynomial with algebraic coefficients. This class is private, and should not be used directly. """ def __init__(self, poly, interval, multiplicity=1): r""" Initialize this ``ANRoot`` object.
EXAMPLES::
sage: x = polygen(QQ); f = (x^3 + x + 1).roots(AA,multiplicities=False)[0]._descr sage: type(f) # indirect doctest <class 'sage.rings.qqbar.ANRoot'> """
def __reduce__(self): """ Add customized pickling support.
EXAMPLES::
sage: x = polygen(QQ) sage: v = (x^2 - x - 1).roots(ring=AA, multiplicities=False)[1] sage: type(v._descr) <class 'sage.rings.qqbar.ANRoot'> sage: loads(dumps(v)) == v True """
def _repr_(self): r""" String representation of self.
EXAMPLES::
sage: x=polygen(QQ); v = (x^2 - x - 1).roots(ring=AA, multiplicities=False)[1] sage: v._descr._repr_() 'Root 1.618033988749894849? of x^2 - x - 1' """
def handle_sage_input(self, sib, coerce, is_qqbar): r""" Produce an expression which will reproduce this value when evaluated, and an indication of whether this value is worth sharing (always True, for ``ANRoot``).
EXAMPLES::
sage: sage_input((AA(3)^(1/2))^(1/3), verify=True) # Verified R.<x> = AA[] AA.polynomial_root(AA.common_polynomial(x^3 - AA.polynomial_root(AA.common_polynomial(x^2 - 3), RIF(RR(1.7320508075688772), RR(1.7320508075688774)))), RIF(RR(1.2009369551760025), RR(1.2009369551760027)))
These two examples are too big to verify quickly. (Verification would create a field of degree 28.)::
sage: sage_input((sqrt(AA(3))^(5/7))^(9/4)) R.<x> = AA[] v1 = AA.polynomial_root(AA.common_polynomial(x^2 - 3), RIF(RR(1.7320508075688772), RR(1.7320508075688774))) v2 = v1*v1 v3 = AA.polynomial_root(AA.common_polynomial(x^7 - v2*v2*v1), RIF(RR(1.4804728524798112), RR(1.4804728524798114))) v4 = v3*v3 v5 = v4*v4 AA.polynomial_root(AA.common_polynomial(x^4 - v5*v5*v3), RIF(RR(2.4176921938267877), RR(2.4176921938267881))) sage: sage_input((sqrt(QQbar(-7))^(5/7))^(9/4)) R.<x> = QQbar[] v1 = QQbar.polynomial_root(AA.common_polynomial(x^2 + 7), CIF(RIF(RR(0)), RIF(RR(2.6457513110645903), RR(2.6457513110645907)))) v2 = v1*v1 v3 = QQbar.polynomial_root(AA.common_polynomial(x^7 - v2*v2*v1), CIF(RIF(RR(0.8693488875796217), RR(0.86934888757962181)), RIF(RR(1.8052215661454434), RR(1.8052215661454436)))) v4 = v3*v3 v5 = v4*v4 QQbar.polynomial_root(AA.common_polynomial(x^4 - v5*v5*v3), CIF(RIF(-RR(3.8954086044650791), -RR(3.8954086044650786)), RIF(RR(2.7639398015408925), RR(2.7639398015408929)))) sage: x = polygen(QQ) sage: sage_input(AA.polynomial_root(x^2-x-1, RIF(1, 2)), verify=True) # Verified R.<x> = AA[] AA.polynomial_root(AA.common_polynomial(x^2 - x - 1), RIF(RR(1.6180339887498947), RR(1.6180339887498949))) sage: sage_input(QQbar.polynomial_root(x^3-5, CIF(RIF(-3, 0), RIF(0, 3))), verify=True) # Verified R.<x> = AA[] QQbar.polynomial_root(AA.common_polynomial(x^3 - 5), CIF(RIF(-RR(0.85498797333834853), -RR(0.85498797333834842)), RIF(RR(1.4808826096823642), RR(1.4808826096823644)))) sage: from sage.rings.qqbar import * sage: from sage.misc.sage_input import SageInputBuilder sage: sib = SageInputBuilder() sage: rt = ANRoot(x^3 - 2, RIF(0, 4)) sage: rt.handle_sage_input(sib, False, True) ({call: {getattr: {atomic:QQbar}.polynomial_root}({call: {getattr: {atomic:AA}.common_polynomial}({binop:- {binop:** {gen:x {constr_parent: {subscr: {atomic:AA}[{atomic:'x'}]} with gens: ('x',)}} {atomic:3}} {atomic:2}})}, {call: {atomic:RIF}({call: {atomic:RR}({atomic:1.259921049894873})}, {call: {atomic:RR}({atomic:1.2599210498948732})})})}, True) """ # Check whether a 53-bit interval actually isolates the root. # If so, use it, because 53-bit intervals print prettier. else: # If the derivative of the polynomial is bounded away from 0 # over this interval, then it definitely isolates a root. else: good_intv = intv
def is_complex(self): r""" Whether this is a root in `\overline{\QQ}` (rather than `\mathbf{A}`). Note that this may return True even if the root is actually real, as the second example shows; it does *not* trigger exact computation to see if the root is real.
EXAMPLES::
sage: x = polygen(QQ) sage: (x^2 - x - 1).roots(ring=AA, multiplicities=False)[1]._descr.is_complex() False sage: (x^2 - x - 1).roots(ring=QQbar, multiplicities=False)[1]._descr.is_complex() True """
def conjugate(self, n): r""" Complex conjugate of this ANRoot object.
EXAMPLES::
sage: a = (x^2 + 23).roots(ring=QQbar, multiplicities=False)[0] sage: b = a._descr sage: type(b) <class 'sage.rings.qqbar.ANRoot'> sage: c = b.conjugate(a); c <sage.rings.qqbar.ANUnaryExpr object at ...> sage: c.exactify() -2*a + 1 where a^2 - a + 6 = 0 and a in 0.50000000000000000? - 2.397915761656360?*I """ return self
def refine_interval(self, interval, prec): r""" Takes an interval which is assumed to enclose exactly one root of the polynomial (or, with multiplicity=`k`, exactly one root of the `k-1`-st derivative); and a precision, in bits.
Tries to find a narrow interval enclosing the root using interval arithmetic of the given precision. (No particular number of resulting bits of precision is guaranteed.)
Uses a combination of Newton's method (adapted for interval arithmetic) and bisection. The algorithm will converge very quickly if started with a sufficiently narrow interval.
EXAMPLES::
sage: from sage.rings.qqbar import ANRoot sage: x = polygen(AA) sage: rt2 = ANRoot(x^2 - 2, RIF(0, 2)) sage: rt2.refine_interval(RIF(0, 2), 75) 1.4142135623730950488017? """ else: else:
def _real_refine_interval(self, interval, prec): r""" Does the calculation for ``refine_interval``.
EXAMPLES::
sage: from sage.rings.qqbar import ANRoot sage: x = polygen(AA) sage: rt2 = ANRoot(x^2 - 2, RIF(0, 2)) sage: rt2.refine_interval(RIF(0, 2), 75) # indirect doctest 1.4142135623730950488017? """ # Don't throw away bits in the original interval; doing so might # invalidate it (include an extra root)
# interval_p = poly_ring(p)
# This special case is important: this is the only way we could # refine "infinitely deep" (we could get an interval of diameter # about 2^{-2^31}, and then hit floating-point underflow); avoiding # this case here means we do not have to worry about iterating too # many times later
# interval_dp = poly_ring(dp)
# sign == 1 if val is bounded greater than 0 # sign == -1 if val is bounded less than 0 # sign == 0 if val might be 0 else:
# We take it on faith that there is a root in interval, # even though we can't prove it at the current precision. # We can't do any more refining...
# Oops... raise ValueError("Refining interval that does not bound unique root!")
# Use a simple algorithm: # Try an interval Newton-Raphson step. If this does not add at # least one bit of information, or if it fails (because the # slope is not bounded away from zero), then try bisection. # If this fails because the value at the midpoint is not # bounded away from zero, then also try the 1/4 and 3/4 points. # If all of these fail, then return the current interval.
# OK, we try Newton-Raphson. # I have no idea if it helps, but each time through the loop, # we either do Newton-Raphson from the left endpoint or # the right endpoint, alternating.
else:
# Wow, we managed to find the answer exactly. # (I think this can only happen with a linear polynomial, # in which case we shouldn't have been in this # function at all; but oh well.)
# We got at least one bit.
# We check to make sure the new interval is actually # narrower; this might not be true if the interval # is less than 4 ulp's wide
# OK, we've refined about as much as we can. # (We might be able to trim a little more off the edges, # but the interval is no more than twice as wide as the # narrowest possible.)
def _complex_refine_interval(self, interval, prec): r""" Takes an interval which is assumed to enclose exactly one root of the polynomial (or, with multiplicity=`k`, exactly one root of the `k-1`-st derivative); and a precision, in bits.
Tries to find a narrow interval enclosing the root using interval arithmetic of the given precision. (No particular number of resulting bits of precision is guaranteed.)
Uses Newton's method (adapted for interval arithmetic). The algorithm will converge very quickly if started with a sufficiently narrow interval. If Newton's method fails, then we falls back on computing all the roots of the polynomial numerically, and select the appropriate root.
EXAMPLES::
sage: from sage.rings.qqbar import ANRoot sage: x = polygen(QQbar) sage: intv = CIF(RIF(0, 1), RIF(0.1, 1)) sage: rt = ANRoot(x^5 - 1, intv) sage: new_intv = rt.refine_interval(intv, 53); new_intv # indirect doctest 0.3090169943749474241? + 0.951056516295153573?*I sage: rt.refine_interval(new_intv, 70) 0.30901699437494742411? + 0.95105651629515357212?*I """ # Don't throw away bits in the original interval; doing so might # invalidate it (include an extra root)
# interval_p = poly_ring(p)
# This special case is important: this is the only way we could # refine "infinitely deep" (we could get an interval of diameter # about 2^{-2^31}, and then hit floating-point underflow); avoiding # this case here means we do not have to worry about iterating too # many times later return zero
# interval_dp = poly_ring(dp)
# Give up and fall back on root isolation.
# Wow; we nailed it exactly. (This may happen # whenever the root is exactly equal to some # floating-point number, and cannot happen # if the root is not equal to a floating-point # number.) We just return the perfect answer.
# We're not getting any better. There are two # possible reasons for this. Either we have # refined as much as possible given the imprecision # of our interval polynomial, and we have the best # answer we're going to get at this precision; # or we started with a poor approximation to the # root, resulting in a broad range of possible # slopes in this interval, and Newton-Raphson refining # is not going to help.
# I do not have a formal proof, but I believe the # following test differentiates between these two # behaviors. (If I'm wrong, we might get bad behavior # like infinite loops, but we still won't actually # return a wrong answer.)
# OK, center must be a good approximation # to the root (in the current precision, anyway). # And the expression "center - val / slope" # above means that we have a pretty good interval, # even if slope is a poor estimate.
# The center of the current interval is known # not to be a root. This should let us divide # the interval in half, and improve on our previous # estimates. I can only think of two reasons why # it might not: # 1) the "center" of the interval is actually # on one of the edges of the interval (because the # interval is only one ulp wide), or # 2) the slope estimate is so bad that # "center - val / slope" doesn't give us information.
# With complex intervals implemented as # rectangular regions of the complex plane, it's # possible that "val / slope" includes zero even # if both "val" and "slope" are bounded away from # zero, if the diameter of the (interval) argument # of val or slope is large enough.
# So we test the diameter of the argument of # slope; if it's small, we decide that we must # have a good interval, but if it's big, we decide # that we probably can't make progress with # Newton-Raphson.
# I think the relevant measure of "small" is # whether the diameter is less than pi/2; in that # case, no matter the value of "val" (as long as # "val" is fairly precise), "val / slope" should # be bounded away from zero. But we compare # against 1 instead, in the hopes that this might # be slightly faster.
# And now it's time to give up. return self._complex_isolate_interval(interval, prec)
def _complex_isolate_interval(self, interval, prec): """ Find a precise approximation to the unique root in interval, by finding a precise approximation to all roots of the polynomial, and checking which one is in interval. Slow but sure.
EXAMPLES::
sage: from sage.rings.qqbar import ANRoot sage: x = polygen(QQbar) sage: intv = CIF(RIF(0, 1), RIF(0.1, 1)) sage: rt = ANRoot(x^5 - 1, intv) sage: rt._complex_isolate_interval(intv, 53) 0.3090169943749474241? + 0.951056516295153573?*I """
# Find all the roots that overlap interval.
raise ValueError("Complex root interval does not include any roots")
# We have more than one root that overlap the current interval. # Technically, this might not be an error; perhaps the actual # root is just outside our interval, even though the (presumably # tight) interval containing that root touches our interval.
# But it seems far more likely that the provided interval is # just too big.
def exactify(self): """ Returns either an ``ANRational`` or an ``ANExtensionElement`` with the same value as this number.
EXAMPLES::
sage: from sage.rings.qqbar import ANRoot sage: x = polygen(QQbar) sage: two = ANRoot((x-2)*(x-sqrt(QQbar(2))), RIF(1.9, 2.1)) sage: two.exactify() 2 sage: strange = ANRoot(x^2 + sqrt(QQbar(3))*x - sqrt(QQbar(2)), RIF(-0, 1)) sage: strange.exactify() a where a^8 - 6*a^6 + 5*a^4 - 12*a^2 + 4 = 0 and a in 0.6051012265139511?
TESTS:
Verify that :trac:`12727` is fixed::
sage: m = sqrt(sin(pi/5)); a = QQbar(m); b = AA(m) sage: a.minpoly() x^8 - 5/4*x^4 + 5/16 sage: b.minpoly() x^8 - 5/4*x^4 + 5/16 """
# Factoring always returns monic polynomials over the rationals
else:
# XXX # This try/except can be triggered if ifield is Real # but the entries in v have some imaginary part that # is only known to be 0 to very low precision, e.g., # as in Trac #12727. In such cases, we instead create # the polynomial over the appropriate complex interval # field, which is mathematically safe, unlike taking # real parts would be.
# rnfequation needs a monic polynomial with integral coefficients. # We achieve this with a change of variables.
# XXX much duplicate code with AlgebraicGenerator.union()
# XXX need more caching here
def _more_precision(self): """ Recompute the interval enclosing this ``ANRoot`` object at higher precision.
EXAMPLES::
sage: x = polygen(QQ); y = (x^3 + x + 1).roots(AA,multiplicities=False)[0] sage: z = y._descr sage: z._interval.prec() 64 sage: z._more_precision() sage: z._interval.prec() 128 """
def _interval_fast(self, prec): """ Given a RealIntervalField, compute the value of this number using interval arithmetic of at least the precision of the field, and return the value in that field. (More precision may be used in the computation.)
EXAMPLES::
sage: x = polygen(QQ); y = (x^3 + x + 1).roots(AA,multiplicities=False)[0]._descr sage: y._interval_fast(128) -0.68232780382801932736948373971104825689?
Check that :trac:`15493` is fixed::
sage: y._interval_fast(20).parent() is RealIntervalField(20) True """
class ANExtensionElement(ANDescr): r""" The subclass of ``ANDescr`` that represents a number field element in terms of a specific generator. Consists of a polynomial with rational coefficients in terms of the generator, and the generator itself, an ``AlgebraicGenerator``. """
def __new__(self, generator, value): else:
def __init__(self, generator, value):
def __reduce__(self): """ Add customized pickling support.
EXAMPLES::
sage: x = polygen(QQ) sage: v = (x^2 - x - 1).roots(ring=AA, multiplicities=False)[1] sage: v.exactify() sage: type(v._descr) <class 'sage.rings.qqbar.ANExtensionElement'> sage: loads(dumps(v)) == v True """
def _repr_(self): self._generator.field().polynomial()._repr(name=sgen), sgen, self._generator._interval_fast(53))
def handle_sage_input(self, sib, coerce, is_qqbar): r""" Produce an expression which will reproduce this value when evaluated, and an indication of whether this value is worth sharing (always True, for ``ANExtensionElement``).
EXAMPLES::
sage: I = QQbar(I) sage: sage_input(3+4*I, verify=True) # Verified QQbar(3 + 4*I) sage: v = QQbar.zeta(3) + QQbar.zeta(5) sage: v - v == 0 True sage: sage_input(vector(QQbar, (4-3*I, QQbar.zeta(7))), verify=True) # Verified R.<x> = AA[] vector(QQbar, [4 - 3*I, QQbar.polynomial_root(AA.common_polynomial(x^6 + x^5 + x^4 + x^3 + x^2 + x + 1), CIF(RIF(RR(0.62348980185873348), RR(0.62348980185873359)), RIF(RR(0.7818314824680298), RR(0.78183148246802991))))]) sage: sage_input(v, verify=True) # Verified R.<x> = AA[] v = QQbar.polynomial_root(AA.common_polynomial(x^8 - x^7 + x^5 - x^4 + x^3 - x + 1), CIF(RIF(RR(0.91354545764260087), RR(0.91354545764260098)), RIF(RR(0.40673664307580015), RR(0.40673664307580021)))) v^5 + v^3 sage: v = QQbar(sqrt(AA(2))) sage: v.exactify() sage: sage_input(v, verify=True) # Verified R.<x> = AA[] QQbar(AA.polynomial_root(AA.common_polynomial(x^2 - 2), RIF(RR(1.4142135623730949), RR(1.4142135623730951)))) sage: from sage.rings.qqbar import * sage: from sage.misc.sage_input import SageInputBuilder sage: sib = SageInputBuilder() sage: extel = ANExtensionElement(QQbar_I_generator, QQbar_I_generator.field().gen() + 1) sage: extel.handle_sage_input(sib, False, True) ({call: {atomic:QQbar}({binop:+ {atomic:1} {atomic:I}})}, True) """
# For the best fidelity, we really ought to somehow ensure # that rt is exactified, but sage_input doesn't support that # nicely. Skip it for now. # The following is copied with slight mods from polynomial_element.pyx else: else:
def is_complex(self): r""" Return True if the number field that defines this element is not real. This does not imply that the element itself is definitely non-real, as in the example below.
EXAMPLES::
sage: rt2 = QQbar(sqrt(2)) sage: rtm3 = QQbar(sqrt(-3)) sage: x = rtm3 + rt2 - rtm3 sage: x.exactify() sage: y = x._descr sage: type(y) <class 'sage.rings.qqbar.ANExtensionElement'> sage: y.is_complex() True sage: x.imag() == 0 True """
def is_simple(self): r""" Checks whether this descriptor represents a value with the same algebraic degree as the number field associated with the descriptor.
For ``ANExtensionElement`` elements, we check this by comparing the degree of the minimal polynomial to the degree of the field.
EXAMPLES::
sage: rt2 = AA(sqrt(2)) sage: rt3 = AA(sqrt(3)) sage: rt2b = rt3 + rt2 - rt3 sage: rt2.exactify() sage: rt2._descr a where a^2 - 2 = 0 and a in 1.414213562373095? sage: rt2._descr.is_simple() True
sage: rt2b.exactify() sage: rt2b._descr a^3 - 3*a where a^4 - 4*a^2 + 1 = 0 and a in 1.931851652578137? sage: rt2b._descr.is_simple() False """
def generator(self): r""" Return the :class:`~AlgebraicGenerator` object corresponding to self.
EXAMPLES::
sage: v = (x^2 - x - 1).roots(ring=AA, multiplicities=False)[1]._descr.exactify() sage: v.generator() Number Field in a with defining polynomial y^2 - y - 1 with a in 1.618033988749895? """
def exactify(self): r""" Return an exact representation of self. Since self is already exact, just return self.
EXAMPLES::
sage: v = (x^2 - x - 1).roots(ring=AA, multiplicities=False)[1]._descr.exactify() sage: type(v) <class 'sage.rings.qqbar.ANExtensionElement'> sage: v.exactify() is v True """
def field_element_value(self): r""" Return the underlying number field element.
EXAMPLES::
sage: v = (x^2 - x - 1).roots(ring=AA, multiplicities=False)[1]._descr.exactify() sage: v.field_element_value() a """
def minpoly(self): """ Compute the minimal polynomial of this algebraic number.
EXAMPLES::
sage: v = (x^2 - x - 1).roots(ring=AA, multiplicities=False)[1]._descr.exactify() sage: type(v) <class 'sage.rings.qqbar.ANExtensionElement'> sage: v.minpoly() x^2 - x - 1 """
def simplify(self, n): """ Compute an exact representation for this descriptor, in the smallest possible number field.
INPUT:
- ``n`` -- The element of ``AA`` or ``QQbar`` corresponding to this descriptor.
EXAMPLES::
sage: rt2 = AA(sqrt(2)) sage: rt3 = AA(sqrt(3)) sage: rt2b = rt3 + rt2 - rt3 sage: rt2b.exactify() sage: rt2b._descr a^3 - 3*a where a^4 - 4*a^2 + 1 = 0 and a in 1.931851652578137? sage: rt2b._descr.simplify(rt2b) a where a^2 - 2 = 0 and a in 1.414213562373095? """
return self
# This is very inefficient... # for instance, the .exactify() call will try to factor poly, # even though we know that poly is irreducible
def _interval_fast(self, prec):
# for these three functions the argument n is not used (but it is there # anyway for compatibility)
def neg(self, n): r""" Negation of self.
EXAMPLES::
sage: a = QQbar(sqrt(-2)) + QQbar(sqrt(-3)) sage: a.exactify() sage: b = a._descr sage: type(b) <class 'sage.rings.qqbar.ANExtensionElement'> sage: b.neg(a) 1/3*a^3 - 2/3*a^2 + 4/3*a - 2 where a^4 - 2*a^3 + a^2 - 6*a + 9 = 0 and a in -0.7247448713915890? - 1.573132184970987?*I sage: b.neg("ham spam and eggs") 1/3*a^3 - 2/3*a^2 + 4/3*a - 2 where a^4 - 2*a^3 + a^2 - 6*a + 9 = 0 and a in -0.7247448713915890? - 1.573132184970987?*I """
def invert(self, n): r""" 1/self.
EXAMPLES::
sage: a = QQbar(sqrt(-2)) + QQbar(sqrt(-3)) sage: a.exactify() sage: b = a._descr sage: type(b) <class 'sage.rings.qqbar.ANExtensionElement'> sage: b.invert(a) 7/3*a^3 - 2/3*a^2 + 4/3*a - 12 where a^4 - 2*a^3 + a^2 - 6*a + 9 = 0 and a in -0.7247448713915890? - 1.573132184970987?*I sage: b.invert("ham spam and eggs") 7/3*a^3 - 2/3*a^2 + 4/3*a - 12 where a^4 - 2*a^3 + a^2 - 6*a + 9 = 0 and a in -0.7247448713915890? - 1.573132184970987?*I """
def conjugate(self, n): r""" Negation of self.
EXAMPLES::
sage: a = QQbar(sqrt(-2)) + QQbar(sqrt(-3)) sage: a.exactify() sage: b = a._descr sage: type(b) <class 'sage.rings.qqbar.ANExtensionElement'> sage: b.conjugate(a) -1/3*a^3 + 2/3*a^2 - 4/3*a + 2 where a^4 - 2*a^3 + a^2 - 6*a + 9 = 0 and a in -0.7247448713915890? + 1.573132184970987?*I sage: b.conjugate("ham spam and eggs") -1/3*a^3 + 2/3*a^2 - 4/3*a + 2 where a^4 - 2*a^3 + a^2 - 6*a + 9 = 0 and a in -0.7247448713915890? + 1.573132184970987?*I """ else:
# The rest of these unary operations do actually use n, which is an # AlgebraicNumber pointing to self.
def norm(self, n): r""" Norm of self (square of complex absolute value)
EXAMPLES::
sage: a = QQbar(sqrt(-2)) + QQbar(sqrt(-3)) sage: a.exactify() sage: b = a._descr sage: type(b) <class 'sage.rings.qqbar.ANExtensionElement'> sage: b.norm(a) <sage.rings.qqbar.ANUnaryExpr object at ...> """ else:
def abs(self, n): r""" Return the absolute value of self (square root of the norm).
EXAMPLES::
sage: a = QQbar(sqrt(-2)) + QQbar(sqrt(-3)) sage: a.exactify() sage: b = a._descr sage: type(b) <class 'sage.rings.qqbar.ANExtensionElement'> sage: b.abs(a) Root 3.146264369941972342? of x^2 - 9.89897948556636? """
def rational_argument(self, n): r""" If the argument of self is `2\pi` times some rational number in `[1/2, -1/2)`, return that rational; otherwise, return ``None``.
EXAMPLES::
sage: a = QQbar(sqrt(-2)) + QQbar(sqrt(3)) sage: a.exactify() sage: b = a._descr sage: type(b) <class 'sage.rings.qqbar.ANExtensionElement'> sage: b.rational_argument(a) is None True sage: x = polygen(QQ) sage: a = (x^4 + 1).roots(QQbar, multiplicities=False)[0] sage: a.exactify() sage: b = a._descr sage: b.rational_argument(a) -3/8 """ # If the argument of self is 2*pi times some rational number a/b, # then self/abs(self) is a root of the b'th cyclotomic polynomial. # This implies that the algebraic degree of self is at least # phi(b). Working backward, we know that the algebraic degree # of self is at most the degree of the generator, so that gives # an upper bound on phi(b). According to # http://mathworld.wolfram.com/TotientFunction.html, # phi(b) >= sqrt(b) for b > 6; this gives us an upper bound on b. # We then check to see if this is possible; if so, we test # to see if it actually holds.
if n > 0: return QQ.zero() else: return QQ((1,2))
else: # Strictly speaking, we need to look for the second-simplest # rational in rat_arg_fl and make sure its denominator is > max_b. # For now, we just punt. raise NotImplementedError
class ANUnaryExpr(ANDescr): def __init__(self, arg, op): r""" Initialize this ANUnaryExpr.
EXAMPLES::
sage: t = ~QQbar(sqrt(2)); type(t._descr) # indirect doctest <class 'sage.rings.qqbar.ANUnaryExpr'> """
def __reduce__(self): """ Add customized pickling support.
EXAMPLES::
sage: t = ~QQbar(sqrt(2)); type(t._descr) <class 'sage.rings.qqbar.ANUnaryExpr'> sage: loads(dumps(t)) == 1/QQbar(sqrt(2)) True """
def handle_sage_input(self, sib, coerce, is_qqbar): r""" Produce an expression which will reproduce this value when evaluated, and an indication of whether this value is worth sharing (always True for ``ANUnaryExpr``).
EXAMPLES::
sage: sage_input(-sqrt(AA(2)), verify=True) # Verified R.<x> = AA[] -AA.polynomial_root(AA.common_polynomial(x^2 - 2), RIF(RR(1.4142135623730949), RR(1.4142135623730951))) sage: sage_input(~sqrt(AA(2)), verify=True) # Verified R.<x> = AA[] ~AA.polynomial_root(AA.common_polynomial(x^2 - 2), RIF(RR(1.4142135623730949), RR(1.4142135623730951))) sage: sage_input(sqrt(QQbar(-3)).conjugate(), verify=True) # Verified R.<x> = QQbar[] QQbar.polynomial_root(AA.common_polynomial(x^2 + 3), CIF(RIF(RR(0)), RIF(RR(1.7320508075688772), RR(1.7320508075688774)))).conjugate() sage: sage_input(QQbar.zeta(3).real(), verify=True) # Verified R.<x> = AA[] QQbar.polynomial_root(AA.common_polynomial(x^2 + x + 1), CIF(RIF(-RR(0.50000000000000011), -RR(0.49999999999999994)), RIF(RR(0.8660254037844386), RR(0.86602540378443871)))).real() sage: sage_input(QQbar.zeta(3).imag(), verify=True) # Verified R.<x> = AA[] QQbar.polynomial_root(AA.common_polynomial(x^2 + x + 1), CIF(RIF(-RR(0.50000000000000011), -RR(0.49999999999999994)), RIF(RR(0.8660254037844386), RR(0.86602540378443871)))).imag() sage: sage_input(abs(sqrt(QQbar(-3))), verify=True) # Verified R.<x> = QQbar[] abs(QQbar.polynomial_root(AA.common_polynomial(x^2 + 3), CIF(RIF(RR(0)), RIF(RR(1.7320508075688772), RR(1.7320508075688774))))) sage: sage_input(sqrt(QQbar(-3)).norm(), verify=True) # Verified R.<x> = QQbar[] QQbar.polynomial_root(AA.common_polynomial(x^2 + 3), CIF(RIF(RR(0)), RIF(RR(1.7320508075688772), RR(1.7320508075688774)))).norm() sage: sage_input(QQbar(QQbar.zeta(3).real()), verify=True) # Verified R.<x> = AA[] QQbar(QQbar.polynomial_root(AA.common_polynomial(x^2 + x + 1), CIF(RIF(-RR(0.50000000000000011), -RR(0.49999999999999994)), RIF(RR(0.8660254037844386), RR(0.86602540378443871)))).real()) sage: from sage.rings.qqbar import * sage: from sage.misc.sage_input import SageInputBuilder sage: sib = SageInputBuilder() sage: unexp = ANUnaryExpr(sqrt(AA(2)), '~') sage: unexp.handle_sage_input(sib, False, False) ({unop:~ {call: {getattr: {atomic:AA}.polynomial_root}({call: {getattr: {atomic:AA}.common_polynomial}({binop:- {binop:** {gen:x {constr_parent: {subscr: {atomic:AA}[{atomic:'x'}]} with gens: ('x',)}} {atomic:2}} {atomic:2}})}, {call: {atomic:RIF}({call: {atomic:RR}({atomic:1.4142135623730949})}, {call: {atomic:RR}({atomic:1.4142135623730951})})})}}, True) sage: unexp.handle_sage_input(sib, False, True) ({call: {atomic:QQbar}({unop:~ {call: {getattr: {atomic:AA}.polynomial_root}({call: {getattr: {atomic:AA}.common_polynomial}({binop:- {binop:** {gen:x {constr_parent: {subscr: {atomic:AA}[{atomic:'x'}]} with gens: ('x',)}} {atomic:2}} {atomic:2}})}, {call: {atomic:RIF}({call: {atomic:RR}({atomic:1.4142135623730949})}, {call: {atomic:RR}({atomic:1.4142135623730951})})})}})}, True) """ else: raise NotImplementedError
# The following version is not safe with respect to caching; # with the current sage_input.py, anything that gets entered # into the cache must be safe at all coercion levels. # if is_qqbar and not coerce: # v = sib.name('QQbar')(v) # if not is_qqbar and coerce != 2: # v = sib.name('AA')(v)
def is_complex(self): r""" Return whether or not this element is complex. Note that this is a data type check, and triggers no computations -- if it returns False, the element might still be real, it just doesn't know it yet.
EXAMPLES::
sage: t = AA(sqrt(2)) sage: s = (-t)._descr sage: s <sage.rings.qqbar.ANUnaryExpr object at ...> sage: s.is_complex() False sage: QQbar(-sqrt(2))._descr.is_complex() True """
def _interval_fast(self, prec): r""" Calculate an approximation to this ``ANUnaryExpr`` object in an interval field of precision ``prec``.
EXAMPLES::
sage: t = AA(sqrt(2)) sage: s = (-t)._descr sage: s <sage.rings.qqbar.ANUnaryExpr object at ...> sage: s._interval_fast(150) -1.414213562373095048801688724209698078569671876? """
else: return v
else: return v
else: return RealIntervalField(prec)(0)
else:
raise NotImplementedError
def exactify(self): r""" Trigger exact computation of self.
EXAMPLES::
sage: v = (-QQbar(sqrt(2)))._descr sage: type(v) <class 'sage.rings.qqbar.ANUnaryExpr'> sage: v.exactify() -a where a^2 - 2 = 0 and a in 1.414213562373095? """
else:
class ANBinaryExpr(ANDescr): def __init__(self, left, right, op): r""" Initialize this ANBinaryExpr.
EXAMPLES::
sage: t = QQbar(sqrt(2)) + QQbar(sqrt(3)); type(t._descr) # indirect doctest <class 'sage.rings.qqbar.ANBinaryExpr'> """
def __reduce__(self): """ Add customized pickling support.
EXAMPLES::
sage: t = QQbar(sqrt(2)) + QQbar(sqrt(3)); type(t._descr) <class 'sage.rings.qqbar.ANBinaryExpr'> sage: loads(dumps(t)) == QQbar(sqrt(2)) + QQbar(sqrt(3)) True """
def handle_sage_input(self, sib, coerce, is_qqbar): r""" Produce an expression which will reproduce this value when evaluated, and an indication of whether this value is worth sharing (always True for ``ANBinaryExpr``).
EXAMPLES::
sage: sage_input(2 + sqrt(AA(2)), verify=True) # Verified R.<x> = AA[] 2 + AA.polynomial_root(AA.common_polynomial(x^2 - 2), RIF(RR(1.4142135623730949), RR(1.4142135623730951))) sage: sage_input(sqrt(AA(2)) + 2, verify=True) # Verified R.<x> = AA[] AA.polynomial_root(AA.common_polynomial(x^2 - 2), RIF(RR(1.4142135623730949), RR(1.4142135623730951))) + 2 sage: sage_input(2 - sqrt(AA(2)), verify=True) # Verified R.<x> = AA[] 2 - AA.polynomial_root(AA.common_polynomial(x^2 - 2), RIF(RR(1.4142135623730949), RR(1.4142135623730951))) sage: sage_input(2 / sqrt(AA(2)), verify=True) # Verified R.<x> = AA[] 2/AA.polynomial_root(AA.common_polynomial(x^2 - 2), RIF(RR(1.4142135623730949), RR(1.4142135623730951))) sage: sage_input(2 + (-1*sqrt(AA(2))), verify=True) # Verified R.<x> = AA[] 2 - AA.polynomial_root(AA.common_polynomial(x^2 - 2), RIF(RR(1.4142135623730949), RR(1.4142135623730951))) sage: sage_input(2*sqrt(AA(2)), verify=True) # Verified R.<x> = AA[] 2*AA.polynomial_root(AA.common_polynomial(x^2 - 2), RIF(RR(1.4142135623730949), RR(1.4142135623730951))) sage: rt2 = sqrt(AA(2)) sage: one = rt2/rt2 sage: n = one+3 sage: sage_input(n) R.<x> = AA[] v = AA.polynomial_root(AA.common_polynomial(x^2 - 2), RIF(RR(1.4142135623730949), RR(1.4142135623730951))) v/v + 3 sage: one == 1 True sage: sage_input(n) 1 + AA(3) sage: rt3 = QQbar(sqrt(3)) sage: one = rt3/rt3 sage: n = sqrt(AA(2))+one sage: one == 1 True sage: sage_input(n) R.<x> = AA[] QQbar.polynomial_root(AA.common_polynomial(x^2 - 2), RIF(RR(1.4142135623730949), RR(1.4142135623730951))) + 1 sage: from sage.rings.qqbar import * sage: from sage.misc.sage_input import SageInputBuilder sage: sib = SageInputBuilder() sage: binexp = ANBinaryExpr(AA(3), AA(5), operator.mul) sage: binexp.handle_sage_input(sib, False, False) ({binop:* {atomic:3} {call: {atomic:AA}({atomic:5})}}, True) sage: binexp.handle_sage_input(sib, False, True) ({call: {atomic:QQbar}({binop:* {atomic:3} {call: {atomic:AA}({atomic:5})}})}, True) """
# We want 2+QQbar.zeta(3) and QQbar.zeta(3)+2, not # QQbar(2)+QQbar.zeta(3). So we want to pass coerced=True to # an argument if it is rational (but if both arguments are # rational, we only want to set it for one of them).
(arg1_is_qqbar and not arg1_coerced) or \ (arg2_is_qqbar and not arg2_coerced)
else: raise RuntimeError("op is {}".format(op))
# The following version is not safe with respect to caching; # with the current sage_input.py, anything that gets entered # into the cache must be safe at all coercion levels. # if is_qqbar and not coerce: # v = sib.name('QQbar')(v) # if not is_qqbar and coerce != 2: # v = sib.name('AA')(v)
def is_complex(self): r""" Whether this element is complex. Does not trigger exact computation, so may return True even if the element is real.
EXAMPLES::
sage: x = (QQbar(sqrt(-2)) / QQbar(sqrt(-5)))._descr sage: x.is_complex() True """
def _interval_fast(self, prec): r""" Calculate an approximation to self in an interval field of precision prec.
EXAMPLES::
sage: x = (QQbar(sqrt(-2)) / QQbar(sqrt(-5)))._descr sage: y= x._interval_fast(64); y 0.632455532033675867? sage: y.parent() Complex Interval Field with 64 bits of precision """
def exactify(self): """ TESTS::
sage: rt2c = QQbar.zeta(3) + AA(sqrt(2)) - QQbar.zeta(3) sage: rt2c.exactify()
We check to make sure that this method still works even. We do this by increasing the recursion level at each step and decrease it before we return::
sage: import sys; sys.getrecursionlimit() 1000 sage: s = SymmetricFunctions(QQ).schur() sage: a=s([3,2]).expand(8)(flatten([[QQbar.zeta(3)^d for d in range(3)], [QQbar.zeta(5)^d for d in range(5)]])) sage: a.exactify(); a # long time 0 sage: sys.getrecursionlimit() 1000
"""
else: finally:
# These are the functions used to add, subtract, multiply, and divide # algebraic numbers. Basically, we try to compute exactly if both # arguments are already known to be in the same number field. Otherwise # we fall back to floating-point computation to be backed up by exact # symbolic computation only as required.
def an_binop_rational(a, b, op): r""" Used to add, subtract, multiply or divide algebraic numbers.
Used when both are actually rational.
EXAMPLES::
sage: from sage.rings.qqbar import an_binop_rational sage: f = an_binop_rational(QQbar(2), QQbar(3/7), operator.add) sage: f 17/7 sage: type(f) <class 'sage.rings.qqbar.ANRational'>
sage: f = an_binop_rational(QQbar(2), QQbar(3/7), operator.mul) sage: f 6/7 sage: type(f) <class 'sage.rings.qqbar.ANRational'> """
def an_binop_expr(a, b, op): r""" Add, subtract, multiply or divide algebraic numbers represented as binary expressions.
INPUT:
- ``a``, ``b`` -- two elements
- ``op`` -- an operator
EXAMPLES::
sage: a = QQbar(sqrt(2)) + QQbar(sqrt(3)) sage: b = QQbar(sqrt(3)) + QQbar(sqrt(5)) sage: type(a._descr); type(b._descr) <class 'sage.rings.qqbar.ANBinaryExpr'> <class 'sage.rings.qqbar.ANBinaryExpr'> sage: from sage.rings.qqbar import an_binop_expr sage: x = an_binop_expr(a, b, operator.add); x <sage.rings.qqbar.ANBinaryExpr object at ...> sage: x.exactify() -6/7*a^7 + 2/7*a^6 + 71/7*a^5 - 26/7*a^4 - 125/7*a^3 + 72/7*a^2 + 43/7*a - 47/7 where a^8 - 12*a^6 + 23*a^4 - 12*a^2 + 1 = 0 and a in 3.12580...?
sage: a = QQbar(sqrt(2)) + QQbar(sqrt(3)) sage: b = QQbar(sqrt(3)) + QQbar(sqrt(5)) sage: type(a._descr) <class 'sage.rings.qqbar.ANBinaryExpr'> sage: x = an_binop_expr(a, b, operator.mul); x <sage.rings.qqbar.ANBinaryExpr object at ...> sage: x.exactify() 2*a^7 - a^6 - 24*a^5 + 12*a^4 + 46*a^3 - 22*a^2 - 22*a + 9 where a^8 - 12*a^6 + 23*a^4 - 12*a^2 + 1 = 0 and a in 3.1258...? """
def an_binop_element(a, b, op): r""" Add, subtract, multiply or divide two elements represented as elements of number fields.
EXAMPLES::
sage: sqrt2 = QQbar(2).sqrt() sage: sqrt3 = QQbar(3).sqrt() sage: sqrt5 = QQbar(5).sqrt()
sage: a = sqrt2 + sqrt3; a.exactify() sage: b = sqrt3 + sqrt5; b.exactify() sage: type(a._descr) <class 'sage.rings.qqbar.ANExtensionElement'> sage: from sage.rings.qqbar import an_binop_element sage: an_binop_element(a, b, operator.add) <sage.rings.qqbar.ANBinaryExpr object at ...> sage: an_binop_element(a, b, operator.sub) <sage.rings.qqbar.ANBinaryExpr object at ...> sage: an_binop_element(a, b, operator.mul) <sage.rings.qqbar.ANBinaryExpr object at ...> sage: an_binop_element(a, b, operator.truediv) <sage.rings.qqbar.ANBinaryExpr object at ...>
The code tries to use existing unions of number fields::
sage: sqrt17 = QQbar(17).sqrt() sage: sqrt19 = QQbar(19).sqrt() sage: a = sqrt17 + sqrt19 sage: b = sqrt17 * sqrt19 - sqrt17 + sqrt19 * (sqrt17 + 2) sage: b, type(b._descr) (40.53909377268655?, <class 'sage.rings.qqbar.ANBinaryExpr'>) sage: a.exactify() sage: b = sqrt17 * sqrt19 - sqrt17 + sqrt19 * (sqrt17 + 2) sage: b, type(b._descr) (40.53909377268655?, <class 'sage.rings.qqbar.ANExtensionElement'>) """
# instanciation of the multimethod dispatch _binop_algo[ANRational, ANRational] = an_binop_rational _binop_algo[ANRational, ANExtensionElement] = \ _binop_algo[ANExtensionElement, ANRational] = \ _binop_algo[ANExtensionElement, ANExtensionElement ] = an_binop_element for t1 in (ANRational, ANRoot, ANExtensionElement, ANUnaryExpr, ANBinaryExpr): for t2 in (ANUnaryExpr, ANBinaryExpr, ANRoot): _binop_algo[t1, t2] = _binop_algo[t2, t1] = an_binop_expr
qq_generator = AlgebraicGenerator(QQ, ANRoot(AAPoly.gen() - 1, RIF(1)))
def _init_qqbar(): """ This code indirectly uses a huge amount of sage, despite the fact that qqbar is imported rather early on in the sage loading. This function is called at the end of sage.all.
EXAMPLES::
sage: sage.rings.qqbar.QQbar_I_generator # indirect doctest Number Field in I with defining polynomial x^2 + 1 with a in 1*I """ global ZZX_x, AA_0, QQbar_I, AA_hash_offset, QQbar_hash_offset, QQbar_I_generator, QQbar_I_nf global QQ_0, QQ_1, QQ_1_2, QQ_1_4, RR_1_10
RR_1_10 = RR(1)/10 QQ_0 = QQ.zero() QQ_1 = QQ.one() QQ_1_2 = QQ((1,2)) QQ_1_4 = QQ((1,4))
AA_0 = AA.zero()
QQbar_I_nf = QuadraticField(-1, 'I', embedding=CC.gen(), latex_name='i') QQbar_I_generator = AlgebraicGenerator(QQbar_I_nf, ANRoot(AAPoly.gen()**2 + 1, CIF(0, 1))) QQbar_I = AlgebraicNumber(ANExtensionElement(QQbar_I_generator, QQbar_I_nf.gen()))
AA_hash_offset = AA(~ZZ(123456789))
QQbar_hash_offset = AlgebraicNumber(ANExtensionElement(QQbar_I_generator, ~ZZ(123456789) + QQbar_I_nf.gen()/ZZ(987654321)))
ZZX_x = ZZ['x'].gen()
# This is used in the _algebraic_ method of the golden_ratio constant, # in sage/symbolic/constants.py AA_golden_ratio = None
def get_AA_golden_ratio(): r""" Return the golden ratio as an element of the algebraic real field. Used by :meth:`sage.symbolic.constants.golden_ratio._algebraic_`.
EXAMPLES::
sage: AA(golden_ratio) # indirect doctest 1.618033988749895? """ global AA_golden_ratio
class ANRootOfUnity(ANExtensionElement): r""" Deprecated class to support unpickling
TESTS::
sage: from sage.rings.qqbar import ANRootOfUnity sage: ANRootOfUnity(1/5, 3/2) doctest:...: DeprecationWarning: ANRootOfUnity is deprecated See http://trac.sagemath.org/19954 for details. 3/2*zeta5 where zeta5^4 + zeta5^3 + zeta5^2 + zeta5 + 1 = 0 and zeta5 in 0.3090169943749474? + 0.9510565162951536?*I """ def __new__(self, a, b): |