Faster comparison code in (real embedded) number fields

[vdelecroix]

Using #19822 we provide a faster comparison code for number field elements when a real embedding is defined (see #17830). We obtain x10 speed up for small elements and x2 speed up for larger ones. The new code is also x50 faster than comparisons in QQbar (with a fixed number field element!!).

For the benchmarks, we used the following comparison function

def test(a,n):
    cf = continued_fraction(a)
    cv1 = a.parent()(cf.convergent(2*n+1))
    cv2 = a.parent()(cf.convergent(2*n+2))
    for _ in range(200):
        assert cv1 > a > cv2

Before

sage: x = polygen(ZZ)
sage: K.<a> = NumberField(x^3 - 2, embedding=1.26)
sage: %timeit test(a,10)
10 loops, best of 3: 51.1 ms per loop
sage: %timeit test(a,20)
10 loops, best of 3: 67 ms per loop
sage: %timeit test(a,100)
10 loops, best of 3: 108 ms per loop
sage: %timeit test(a,200)
1 loops, best of 3: 154 ms per loop

after

sage: x = polygen(ZZ)
sage: K.<a> = NumberField(x^3 - 2, embedding=1.26)
sage: %timeit test(a,10)
100 loops, best of 3: 5.84 ms per loop
sage: %timeit test(a,20)
100 loops, best of 3: 10.2 ms per loop
sage: %timeit test(a,100)
10 loops, best of 3: 33.5 ms per loop
sage: %timeit test(a,200)
10 loops, best of 3: 64.8 ms per loop

To be compared with

sage: a = AA(2)**(1/3)
sage: a.exactify()
sage: %timeit test(a,10)
10 loops, best of 3: 97.7 ms per loop
sage: %timeit test(a,20)
10 loops, best of 3: 133 ms per loop
sage: %timeit test(a,100)
1 loops, best of 3: 224 ms per loop
sage: %timeit test(a,200)
1 loops, best of 3: 305 ms per loop

[vdelecroix]

New commits:

​e2287a6	Trac 19822: polynomial evaluation
​ea54d91	Trac 19822: call from python
​131cd59	Trac 19822: review 1
​ad07216	Trac 19822: change method names + warning in doc
​cf0f8f5	Trac 19824: faster number field comparisons

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​6693fa9	Trac 19822: only use MPFR_RNDN
​2453496	Trac 19822: review 2
​82f121b	Trac 19822: add doctest for corner cases
​5562a78	Trac 19822: remove two Cython directives that belong to #19841
​c9c7133	Trac 19824: faster number field comparisons