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: sage-8.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:

Status badges

Description (last modified by Jeroen Demeyer)

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 Frédéric 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 4 years ago by Frédéric Chapoton

see also clear_denominators(poly) in qqbar.py

comment:3 Changed 4 years ago by Frédéric 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 4 years ago by Frédéric Chapoton

Description: modified (diff)

comment:5 in reply to:  description Changed 4 years ago by Jeroen Demeyer

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 Jeroen Demeyer

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 4 years ago by Jeroen Demeyer

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

comment:8 Changed 4 years ago by Frédéric 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 4 years ago by Jeroen Demeyer

Status: needs_workneeds_review

I also enabled __future__.division.

comment:10 Changed 4 years ago by Frédéric Chapoton

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

comment:11 in reply to:  10 Changed 4 years ago by Jeroen Demeyer

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 4 years ago by Frédéric 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..

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 ?

Last edited 4 years ago by Frédéric Chapoton (previous) (diff)

comment:13 in reply to:  12 Changed 4 years ago by Jeroen Demeyer

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 Frédéric Chapoton

Reviewers: Frédéric Chapoton
Status: needs_reviewpositive_review

ok, indeed. Sorry for the noise.

comment:15 Changed 4 years ago by Jeroen Demeyer

Description: modified (diff)

comment:16 Changed 4 years ago by Volker Braun

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