#13213: Comparisons in real number field
-------------------------------------------------+--------------------------
Reporter: vdelecroix | Owner: vdelecroix
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-5.3
Component: number fields | Resolution:
Keywords: real number field, comparison | Work issues:
Report Upstream: N/A | Reviewers: Burcin Erocal
Authors: Vincent Delecroix | Merged in:
Dependencies: | Stopgaps:
-------------------------------------------------+--------------------------
Description changed by vdelecroix:
Old description:
> The order of quadratic field is not induced from the order of RR and CC
> (when there is an embedding). More precisely we have
> {{{
> sage: K.<sqrt2> = NumberField(x^2 - 2, 'sqrt2', embedding=1.4142)
> sage: sqrt2 < 100
> False
> }}}
> which is not compatible with the order of RR and
> {{{
> sage: K.<i> = QuadraticField(-1)
> sage: i > 1
> True
> sage: 1 > i
> True
> }}}
> which is not compatible (!) with the order of CC.
>
> There is a patch for quadratic field. Another will come for general
> number fields. Note that this patch is partly a duplicate because of
> #7160. The modifications for the order on complex number field modify the
> behavior of many commands (output order).
>
> The lost of speed is about x5 for positive discriminant and almost
> nothing for negative ones
> {{{
> sage: K.<sqrt2> = QuadraticField(2,'sqrt2',embedding=1.4142)
> sage: a = (3*sqrt2 + 18)/7
> sage: b = (5*sqrt2 + 14)/5
> sage: %timeit a < b
> 625 loops, best of 3: 2.36 µs per loop
>
> sage: K.<s> = QuadraticField(-2)
> sage: a=3*s+2/4
> sage: b=5/7*s+1/3
> sage: %timeit a < b
> 625 loops, best of 3: 600 ns per loop
> }}}
> Timings without the patch
> {{{
> sage: sage: K.<sqrt2> = QuadraticField(2,'sqrt2',embedding=1.4142)
> sage: a = (3*sqrt2 + 18)/7
> sage: b = (5*sqrt2 + 14)/5
> sage: %timeit a < b
> 625 loops, best of 3: 491 ns per loop
>
> sage: K.<s> = QuadraticField(-2)
> sage: a=3*s+2/4
> sage: b=5/7*s+1/3
> sage: %timeit a < b
> 625 loops, best of 3: 488 ns per loop
> }}}
New description:
The order of number field with specified embedding is not induced from the
order of RR and CC. More precisely we have
{{{
sage: K.<sqrt2> = NumberField(x^2 - 2, 'sqrt2', embedding=1.4142)
sage: sqrt2 < 100
False
sage: K.<s> = NumberField(x^3 - 2, 's', embedding=1.26)
sage: s < 100
False
}}}
which is not compatible with the order of RR and
{{{
sage: K.<i> = QuadraticField(-1)
sage: i > 1
True
sage: 1 > i
True
}}}
which is not compatible (!) with the order of CC.
The ticket implements the order for quadratic field (for which comparisons
are made using only operations on integers) and a patch for generic number
fields with specified real embedding (for which comparisons are made using
successive approximations).
Note:
* this patch is partly a duplicate because of #7160
* the modifications for quadratic field field modify the behavior of many
commands (especially about output order).
----
The lost of speed is about x10 for quadratic field and about x100 for
generic real number field.
{{{
sage: K.<sqrt2> = QuadraticField(2, 'sqrt2', embedding=1.4142)
sage: a = (3*sqrt2 + 18)/7
sage: b = (5*sqrt2 + 14)/5
sage: %timeit a < b
625 loops, best of 3: 4.32 µs per loop
sage: K.<s> = QuadraticField(-2)
sage: a = 3*s + 2/4
sage: b = 5/7*s + 1/3
sage: %timeit a < b
625 loops, best of 3: 1.42 µs per loop
sage: K.<s> = NumberField(x^3-3, 's', embedding=1.26)
sage: a = 3/15*s**2 - 4/7*s + 2/3
sage: b = -1/2*s**2 + s - 13/5
sage: %timeit a < b
625 loops, best of 3: 49.6 µs per loop
}}}
Timings without the patch
{{{
sage: sage: K.<sqrt2> = QuadraticField(2,'sqrt2',embedding=1.4142)
sage: a = (3*sqrt2 + 18)/7
sage: b = (5*sqrt2 + 14)/5
sage: %timeit a < b
625 loops, best of 3: 491 ns per loop
sage: K.<s> = QuadraticField(-2)
sage: a = 3*s+2/4
sage: b = 5/7*s+1/3
sage: %timeit a < b
625 loops, best of 3: 488 ns per loop
sage: K.<s>=NumberField(x^3-3, 's',embedding=1.26)
sage: a = 3/15*s**2 - 4/7*s + 2/3
sage: b = -1/2*s**2 + s - 13/5
sage: %timeit a < b
625 loops, best of 3: 845 ns per loop
}}}
--
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/13213#comment:17>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
