Opened 4 years ago
Closed 4 years ago
#25635 closed enhancement (fixed)
enhanced make_monic in heegner.py
Reported by:  Frédéric Chapoton  Owned by:  

Priority:  major  Milestone:  sage8.3 
Component:  elliptic curves  Keywords:  
Cc:  John 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: 
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 4 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 4 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 4 years ago by
Description:  modified (diff) 

comment:5 Changed 4 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 4 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 4 years ago by
Branch:  u/chapoton/25635 → u/jdemeyer/25635 

comment:8 Changed 4 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 python3pdfdocbuild : the full log is here :
New commits:
61b0930  possibly better make_monic in heegner.py

9cbb66b  Improve make_monic

comment:9 Changed 4 years ago by
Status:  needs_work → needs_review 

I also enabled __future__.division
.
comment:11 Changed 4 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 followup: 13 Changed 4 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..
EDIT: I mean, not in the final creation of the polynomial, but in the main loop.
And maybe the main loop should use range(1,n+1) in fact ?
comment:13 Changed 4 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 4 years ago by
Reviewers:  → Frédéric Chapoton 

Status:  needs_review → positive_review 
ok, indeed. Sorry for the noise.
comment:15 Changed 4 years ago by
Description:  modified (diff) 

comment:16 Changed 4 years ago by
Branch:  u/jdemeyer/25635 → 9cbb66bf5822c77fb8356af27ccc2d03401d0b25 

Resolution:  → fixed 
Status:  positive_review → closed 
New commits:
possibly better make_monic in heegner.py