Opened 5 years ago

Closed 5 years ago

#19824 closed enhancement (fixed)

Faster comparison code in (real embedded) number fields

Reported by: vdelecroix Owned by:
Priority: major Milestone: sage-7.0
Component: number fields Keywords:
Cc: Merged in:
Authors: Vincent Delecroix Reviewers: Marc Mezzarobba
Report Upstream: N/A Work issues:
Branch: c9c7133 (Commits) Commit: c9c7133322fe7d762d7fb5c95f5d105c60788f90
Dependencies: #19822 Stopgaps:

Description (last modified by 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

Change History (6)

comment:1 Changed 5 years ago by vdelecroix

  • Branch set to u/vdelecroix/19824
  • Commit set to cf0f8f525c00e2114260c3e6d34d594e0dfed3b0
  • Status changed from new to needs_review

New commits:

e2287a6Trac 19822: polynomial evaluation
ea54d91Trac 19822: call from python
131cd59Trac 19822: review 1
ad07216Trac 19822: change method names + warning in doc
cf0f8f5Trac 19824: faster number field comparisons

comment:2 Changed 5 years ago by vdelecroix

  • Description modified (diff)

comment:3 Changed 5 years ago by git

  • Commit changed from cf0f8f525c00e2114260c3e6d34d594e0dfed3b0 to c9c7133322fe7d762d7fb5c95f5d105c60788f90

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

6693fa9Trac 19822: only use MPFR_RNDN
2453496Trac 19822: review 2
82f121bTrac 19822: add doctest for corner cases
5562a78Trac 19822: remove two Cython directives that belong to #19841
c9c7133Trac 19824: faster number field comparisons

comment:4 Changed 5 years ago by vdelecroix

  • Description modified (diff)
  • Type changed from PLEASE CHANGE to enhancement

comment:5 Changed 5 years ago by mmezzarobba

  • Reviewers set to Marc Mezzarobba
  • Status changed from needs_review to positive_review

comment:6 Changed 5 years ago by vbraun

  • Branch changed from u/vdelecroix/19824 to c9c7133322fe7d762d7fb5c95f5d105c60788f90
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.