Opened 4 months ago
Closed 3 months ago
#33218 closed enhancement (fixed)
speed up poly.valuation(other_poly)
Reported by: | mmezzarobba | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-9.6 |
Component: | basic arithmetic | Keywords: | |
Cc: | Merged in: | ||
Authors: | Marc Mezzarobba | Reviewers: | Lorenz Panny, Frédéric Chapoton |
Report Upstream: | N/A | Work issues: | |
Branch: | fba7039 (Commits, GitHub, GitLab) | Commit: | fba70398c05016d05b0738888b196426d57ce0e7 |
Dependencies: | Stopgaps: |
Description (last modified by )
sage: pol = (27122036833024*z^43 + 8208413201024064*z^42 + 1028987679702510976*z^41 + 75518451137118783792*z^40 + 3743195619381989907184*z^39 + 135369638077546936261428*z^38 + 3745615314367420203992832*z^37 + 81811619367860049045984675*z^36 + 1440466637248203913774334250*z^35 + 20724331113040275023719172850*z^34 + 245446627541652046097792768214*z^33 + 2395828801191215780780578117794*z^32 + 19147407470673111231862249418166*z^31 + 122863963621496746370188659696702*z^30 + 602621255648485924378700672331054*z^29 + 1935192664301617476137337671088360*z^28 + 694152712036783264243644290673234*z^27 - 39030042885818935455901289133872622*z^26 - 297645962803933196564873733670191774*z^25 - 1329742929728007215704002549281591538*z^24 - 3903989614825648819224432657208727646*z^23 - 6038015534019664017777438417359311914*z^22 + 7565280951156009750992823479550694170*z^21 + 83328126336960183101771239549883786325*z^20 + 297859836972471180382017327162905955900*z^19 + 681226694393685252017130073908325840500*z^18 + 1055504316932586226613390044310017920000*z^17 + 974982625144110654834660688990434600000*z^16 + 80921481727424794623135930623472000000*z^15 - 1245692778975371208980497936649580000000*z^14 - 1877612972166046542841525891548000000000*z^13 - 1186201691981014544058180007080000000000*z^12 - 4424139263701398029187830400000000000*z^11 + 526588498855023559134177312000000000000*z^10 + 410999234738834010247469568000000000000*z^9 + 174333012213810958051184640000000000000*z^8 + 29950530354743793153638400000000000000*z^7 + 2276991208061142220800000000000000000*z^6) # before: sage: sage: %timeit pol.valuation(z-3) 140 µs ± 272 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each) # after: sage: %timeit pol.valuation(z-3) 90.7 µs ± 119 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
Change History (7)
comment:1 Changed 4 months ago by
- Branch set to u/mmezzarobba/33218-valuation
- Commit set to fe1407df2be76d74653f57568718f9633fd364c3
- Description modified (diff)
- Status changed from new to needs_review
- Summary changed from speed up valuation of a polynomial at another to speed up poly.valuation(other_poly)
comment:2 Changed 4 months ago by
- Reviewers set to Lorenz Panny
Looks good! Just two small suggestions.
- This appears to make it a tiny bit faster:
- rem = self.parent().zero() + cdef Polynomial rem = self.parent().zero()
- While we're at it, we could also fix this (to catch
p=0
):- if p.degree() == 0: - raise ArithmeticError("The polynomial, p, must have positive degree.") + if p.is_constant(): + raise ArithmeticError("The polynomial, p, must be non-constant.")
comment:3 Changed 4 months ago by
- Commit changed from fe1407df2be76d74653f57568718f9633fd364c3 to fba70398c05016d05b0738888b196426d57ce0e7
Branch pushed to git repo; I updated commit sha1. New commits:
fba7039 | #33218 reviewer comments, further micro-optimizations
|
comment:4 Changed 4 months ago by
thanks for your comments! the new version seems to be 1-2% faster on the example in the description
comment:5 Changed 4 months ago by
- Reviewers changed from Lorenz Panny to Lorenz Panny, Frédéric Chapoton
- Status changed from needs_review to positive_review
ok
comment:6 Changed 4 months ago by
thank you!
comment:7 Changed 3 months ago by
- Branch changed from u/mmezzarobba/33218-valuation to fba70398c05016d05b0738888b196426d57ce0e7
- Resolution set to fixed
- Status changed from positive_review to closed
Note: See
TracTickets for help on using
tickets.
New commits:
#33218 speed up Polynomial.valuation()