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:  sage7.0 
Component:  number fields  Keywords:  
Cc:  Merged in:  
Authors:  Vincent Delecroix  Reviewers:  Marc Mezzarobba 
Report Upstream:  N/A  Work issues:  
Branch:  c9c7133 (Commits, GitHub, GitLab)  Commit:  c9c7133322fe7d762d7fb5c95f5d105c60788f90 
Dependencies:  #19822  Stopgaps: 
Description (last modified by )
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
 Branch set to u/vdelecroix/19824
 Commit set to cf0f8f525c00e2114260c3e6d34d594e0dfed3b0
 Status changed from new to needs_review
comment:2 Changed 5 years ago by
 Description modified (diff)
comment:3 Changed 5 years ago by
 Commit changed from cf0f8f525c00e2114260c3e6d34d594e0dfed3b0 to c9c7133322fe7d762d7fb5c95f5d105c60788f90
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

comment:4 Changed 5 years ago by
 Description modified (diff)
 Type changed from PLEASE CHANGE to enhancement
comment:5 Changed 5 years ago by
 Reviewers set to Marc Mezzarobba
 Status changed from needs_review to positive_review
comment:6 Changed 5 years ago by
 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.
New commits:
Trac 19822: polynomial evaluation
Trac 19822: call from python
Trac 19822: review 1
Trac 19822: change method names + warning in doc
Trac 19824: faster number field comparisons