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, 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