sorting of number field elements

[JohnCremona]

See the discussion at https://groups.google.com/forum/#!topic/sage-devel/aP5LP09sADY

sage: K.<a> = NumberField(x^3+x+1)
sage: K(1) > K(2), K(2) > K(1)
(True, True)
sage: K(1) < K(2), K(2) < K(1)
(False, False)

Depends on #20064

CC: gjorgens@math.fsu.edu @sagetrac-jakobkroeker @kliem @videlec @fchapoton @antonio-rojas

Component: number fields

Keywords: sort number field elements

Branch/Commit: u/cremona/20028 @ 2016dd3

Issue created by migration from https://trac.sagemath.org/ticket/20028

[nbruin]

comment:1

I guess the first step for this is to ensure that order comparisons on number field elements by default raise an error. I think that means implementing _richcmp_ and nuking the _cmp_ on NumberFieldElement. Then we can see where that raises errors (all those places are bugs given what _cmp_ does for order comparisons) and, where necessary, we can put in "sort" commands with a suitable sort key (and make convenient key implementations available).

[nbruin]

Branch: u/nbruin/sorting_of_number_field_elements

[nbruin]

comment:3

Failures are pretty bad. We'll need a lot of fixing (and these things are basically all bugs!)

One of the doctest failures is actually just documenting that comparison is bogus: numberfield.py:394 so that one is not so bad.

---

New commits:

7aca119

trac 20028: disable nonsensical comparison for number field elements

[nbruin]

Commit: 7aca119

[JohnCremona]

comment:4

Thanks for geting started on this. I have built the branch and will see what "make testlong" reveals. It may be a good idea -- surely -- to not put this forward for merging until there is at least a default sorting function in place, which is quick such as by comparing strings?

[nbruin]

comment:5

Replying to @JohnCremona:

Thanks for geting started on this. I have built the branch and will see what "make testlong" reveals. It may be a good idea -- surely -- to not put this forward for merging until there is at least a default sorting function in place, which is quick such as by comparing strings?

Isn't the whole idea that there is no default sorting function? If you mean making convenient key functions readily available, then: yes. I expect we'll need them to fix doctests.

Comparing strings is not cheap at all because constructing the string representation is slow. It's better to stick with binary objects. Coefficient lists are much faster:

sage: L=[a^j for j in [1..100]]
sage: %timeit [str(l) for l in L]
100 loops, best of 3: 5.89 ms per loop
sage: %timeit [l.list() for l in L]
1000 loops, best of 3: 386 µs per loop
sage: %timeit [list(l) for l in L]
100 loops, best of 3: 9.92 ms per loop
sage: k=lambda l:l.list()
sage: %timeit [k(l) for l in L]
1000 loops, best of 3: 398 µs per loop

unfortunately, using "list(l)" is slow: it might construct an iterator out of l first, which would have much more overhead to get the whole list of coefficients than getting the list immediately. So either we optimize "list" so that sorted(L,key=list) works or we make k above available (possibly in a lower overhead version). Note that coefficient lists already come in the right order for power basis rep: integers look like [*,0,...,0].

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

d664262

trac 20028: first batch of fixes to pass doctests

[sagetrac-git]

Changed commit from 7aca119 to d664262

[nbruin]

comment:7

First list of changes. For me, number_field_element.pyx now passes. I suspect that a lot of changes will be along the lines of the ones done here.

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

77618de

second batch of doctest fixes

[sagetrac-git]

Changed commit from d664262 to 77618de