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 jdemeyer)

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 chapoton

Branch: u/chapoton/25635
Commit: 9a8afc97ea2de430a90e9bb504a2dd6b4d042413
Status: newneeds_review
Summary: enhanced make_onic in heegner.pyenhanced make_monic in heegner.py

New commits:

9a8afc9possibly better make_monic in heegner.py

comment:2 Changed 5 years ago by chapoton

see also clear_denominators(poly) in qqbar.py

comment:3 Changed 5 years ago by chapoton

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 chapoton

Description: modified (diff)

comment:5 in reply to:  description Changed 5 years ago by jdemeyer

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 jdemeyer

Authors: Frédéric ChapotonFrédéric Chapoton, Jeroen Demeyer
Status: needs_reviewneeds_work

I'll make an improvement using trivial division only.

comment:7 Changed 5 years ago by jdemeyer

Branch: u/chapoton/25635u/jdemeyer/25635

comment:8 Changed 5 years ago by chapoton

Commit: 9a8afc97ea2de430a90e9bb504a2dd6b4d0424139cbb66bf5822c77fb8356af27ccc2d03401d0b25

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 :

https://patchbot.sagemath.org/log/0/Ubuntu/18.04/x86_64/4.15.0-20-generic/petitbonum/2018-07-08%2021:25:52?plugin=docbuild_pdf


New commits:

61b0930possibly better make_monic in heegner.py
9cbb66bImprove make_monic

comment:9 Changed 5 years ago by jdemeyer

Status: needs_workneeds_review

I also enabled __future__.division.

comment:10 Changed 5 years ago by chapoton

maybe for i in range(n) can start from 1 ?

comment:11 in reply to:  10 Changed 5 years ago by jdemeyer

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 Changed 5 years ago by chapoton

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

Version 0, edited 5 years ago by chapoton (next)

comment:13 in reply to:  12 Changed 5 years ago by jdemeyer

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 chapoton

Reviewers: Frédéric Chapoton
Status: needs_reviewpositive_review

ok, indeed. Sorry for the noise.

comment:15 Changed 5 years ago by jdemeyer

Description: modified (diff)

comment:16 Changed 5 years ago by vbraun

Branch: u/jdemeyer/256359cbb66bf5822c77fb8356af27ccc2d03401d0b25
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.