Opened 5 years ago
Closed 5 years ago
#25635 closed enhancement (fixed)
enhanced make_monic in heegner.py
| Reported by: | chapoton | Owned by: | |
|---|---|---|---|
| Priority: | major | Milestone: | sage-8.3 |
| Component: | elliptic curves | Keywords: | |
| Cc: | cremona | Merged in: | |
| Authors: | Frédéric Chapoton, Jeroen Demeyer | Reviewers: | Frédéric Chapoton |
| Report Upstream: | N/A | Work issues: | |
| Branch: | 9cbb66b (Commits, GitHub, GitLab) | Commit: | 9cbb66bf5822c77fb8356af27ccc2d03401d0b25 |
| Dependencies: | Stopgaps: |
GitHub link to the corresponding issue
Description (last modified by )
By being more subtle, getting simpler results.
NOTE: needs to be merged with existing clear_denominators ?
Change History (16)
comment:1 Changed 5 years ago by
| Branch: | → u/chapoton/25635 |
|---|---|
| Commit: | → 9a8afc97ea2de430a90e9bb504a2dd6b4d042413 |
| Status: | new → needs_review |
| Summary: | enhanced make_onic in heegner.py → enhanced make_monic in heegner.py |
comment:3 Changed 5 years ago by
note that clear_denominators assumes that its input is monic
and also the output are in reversed order.
timing comparison with th branch here:
sage: %timeit make_monic(x^2 + x/2 + 1/4) 10000 loops, best of 3: 96.6 µs per loop sage: %timeit clear_denominators(x^2 + x/2 + 1/4) 10000 loops, best of 3: 109 µs per loop sage: make_monic(3*x^3 + 14*x^2 - 7*x + 5) sage: %timeit make_monic((3*x^3 + 14*x^2 - 7*x + 5)/3) 10000 loops, best of 3: 112 µs per loop sage: %timeit clear_denominators((3*x^3 + 14*x^2 - 7*x + 5)/3) 10000 loops, best of 3: 155 µs per loop
comment:4 Changed 5 years ago by
| Description: | modified (diff) |
|---|
comment:5 Changed 5 years ago by
Replying to chapoton:
By being more subtle, getting simpler results.
but maybe slower because it is using radical instead of gcd ?
It is certainly slower when the denominators are large: computing the radical of N means factoring N.
comment:6 Changed 5 years ago by
| Authors: | Frédéric Chapoton → Frédéric Chapoton, Jeroen Demeyer |
|---|---|
| Status: | needs_review → needs_work |
I'll make an improvement using trivial division only.
comment:7 Changed 5 years ago by
| Branch: | u/chapoton/25635 → u/jdemeyer/25635 |
|---|
comment:8 Changed 5 years ago by
| Commit: | 9a8afc97ea2de430a90e9bb504a2dd6b4d042413 → 9cbb66bf5822c77fb8356af27ccc2d03401d0b25 |
|---|
Thanks for having a look. This has rather low priority, in my opinion.
Something unrelated : I wonder if you could have a look at a specific failure involving __div__ in element.pyx in the python3-pdf-docbuild : the full log is here :
New commits:
| 61b0930 | possibly better make_monic in heegner.py
|
| 9cbb66b | Improve make_monic
|
comment:9 Changed 5 years ago by
| Status: | needs_work → needs_review |
|---|
I also enabled __future__.division.
comment:11 Changed 5 years ago by
Replying to chapoton:
maybe
for i in range(n)can start from 1 ?
What do you mean? Surely we need to look at the constant coefficient too (image the polynomial is x + 1/2).
comment:12 follow-up: 13 Changed 5 years ago by
But i=0 is for the leading coefficient, no ?
If I run in my mind the code when i=0, I got den=1, and nothing happens..
comment:13 Changed 5 years ago by
Replying to chapoton:
But i=0 is for the leading coefficient, no ?
No, the constant coefficient, the coefficient of degree 0.
comment:14 Changed 5 years ago by
| Reviewers: | → Frédéric Chapoton |
|---|---|
| Status: | needs_review → positive_review |
ok, indeed. Sorry for the noise.
comment:15 Changed 5 years ago by
| Description: | modified (diff) |
|---|
comment:16 Changed 5 years ago by
| Branch: | u/jdemeyer/25635 → 9cbb66bf5822c77fb8356af27ccc2d03401d0b25 |
|---|---|
| Resolution: | → fixed |
| Status: | positive_review → closed |
New commits:
possibly better make_monic in heegner.py