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:

Status badges

Description (last modified by mmezzarobba) 

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 mmezzarobba

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

New commits:

​fe1407d#33218 speed up Polynomial.valuation()

comment:2 Changed 4 months ago by lorenz

  • 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 git

  • 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 mmezzarobba

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 chapoton

  • 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 mmezzarobba

thank you!

comment:7 Changed 3 months ago by vbraun

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