Opened 11 years ago

Closed 7 years ago

#9883 closed defect (duplicate)

slow coercion of list to polynomial over integer mod ring

Reported by: dmharvey Owned by: tbd
Priority: major Milestone: sage-duplicate/invalid/wontfix
Component: performance Keywords:
Cc: Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description

Sage 4.5.3, 2.6GHz Opteron, Linux:

sage: R = Integers(3^20)
sage: S.<x> = PolynomialRing(R)
sage: L = [R.random_element() for i in range(100)]
sage: timeit("f = S(L)")
125 loops, best of 3: 4.79 ms per loop

That's about 124000 cycles per coefficient conversion. Compare to the cost of multiplying polynomials of the same degree:

sage: f = S([R.random_element() for i in range(100)])
sage: g = S([R.random_element() for i in range(100)])
sage: timeit("h = f * g")
625 loops, best of 3: 31.8 µs per loop

Change History (4)

comment:1 Changed 11 years ago by roed

This is sped up by about a factor of 200 by the patch at #9887. If that's positively reviewed, I would suggest closing this ticket.

comment:2 Changed 7 years ago by mmezzarobba

  • Milestone set to sage-duplicate/invalid/wontfix
  • Status changed from new to needs_review

With sage-6.1:

sage: sage: R = Integers(3^20)
sage: sage: S.<x> = PolynomialRing(R)
sage: sage: L = [R.random_element() for i in range(100)]
sage: sage: timeit("f = S(L)")
625 loops, best of 3: 49.6 µs per loop
sage: sage: L = [R.random_element() for i in range(1000)]
sage: sage: timeit("f = S(L)")
625 loops, best of 3: 388 µs per loop

sage: sage: f = S([R.random_element() for i in range(100)])
sage: sage: g = S([R.random_element() for i in range(100)])
sage: sage: timeit("h = f * g")
625 loops, best of 3: 10.9 µs per loop

comment:3 Changed 7 years ago by aapitzsch

  • Status changed from needs_review to positive_review

comment:4 Changed 7 years ago by vbraun

  • Resolution set to duplicate
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.