#13213: Comparisons in quadratic number field
-------------------------------------------------+--------------------------
Reporter: vdelecroix | Owner: vdelecroix
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-5.10
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 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
> }}}
New description:
The order of quadratic 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).
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 patch introduces a new attribute to NumberFieldElement_quadratic
called standard_embedding (of type bint)
----
There is no significant lost of speed as shown on the following timings.
{{{
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
1000000 loops, best of 3: 408 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
1000000 loops, best of 3: 352 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
1000000 loops, best of 3: 393 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
1000000 loops, best of 3: 344 ns per loop
}}}
Apply:
* trac_13213-quadratic_field_comparison.patch
--
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/13213#comment:20>
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 unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.
