Special-case pol*term, term*pol for generic polynomials

[mezzarobba]

sage: Pol0.<t> = ZZ[]
....: Pol1.<x> = Pol0[]
....: p = ((t^2 - 3*t)*x^10 + (-3*t^2 - 1)*x^9 + (-t^2 - t + 1)*x^8 + (-t^2 - 1)*x^7 + (-4*t^2 + 14*t - 4)*x^6 + (2*t^2 + 2)*x^5 + (-t^2 + 2*t + 2)*x^4 + (3*t^2 - t + 3)*x^3 + (t^2 - t + 156)*x^2 + (7*t - 3)*x - t^2 + 2*t)
....: q = 2*x

8.3.beta0:

sage: %timeit p*q
The slowest run took 2129.02 times longer than the fastest. This could mean that an intermediate result is being cached.
100000 loops, best of 3: 8.02 µs per loop

This ticket:

The slowest run took 8.63 times longer than the fastest. This could mean that an intermediate result is being cached.
100000 loops, best of 3: 2.21 µs per loop

Component: basic arithmetic

Author: Marc Mezzarobba, Travis Scrimshaw

Branch/Commit: d37db8d

Reviewer: Travis Scrimshaw, Marc Mezzarobba

Issue created by migration from https://trac.sagemath.org/ticket/25317

[tscrim]

comment:3

Perhaps it would be better to have a specialized cdef scale_and_shift method that can be overwritten by the specific data structures in order to avoid creating an intermediate object? In fact, the generic _lmul_ and _rmul_ just lift the coefficient to the polynomial ring and multiply. I would also rewrite _mul_ and _rmul_ to use this scale_and_shift with a shift of 0 to avoid code duplication.

[mezzarobba]

comment:4

Replying to @tscrim:

Perhaps it would be better to have a specialized cdef scale_and_shift method that can be overwritten by the specific data structures in order to avoid creating an intermediate object? In fact, the generic _lmul_ and _rmul_ just lift the coefficient to the polynomial ring and multiply. I would also rewrite _mul_ and _rmul_ to use this scale_and_shift with a shift of 0 to avoid code duplication.

Yes, why not... I'm not sure it is worth the pain now—I'm not really trying to make this operation as fast as possible, just to avoid the worst of the overhead (especially in the Karatsuba range). So I'm not going to implement your suggestion now, but perhaps later, and in any case I can review the implementation if you want to do it yourself.

Thanks for you comments in any case!

[tscrim]

comment:5

Replying to @mezzarobba:

Replying to @tscrim:

Perhaps it would be better to have a specialized cdef scale_and_shift method that can be overwritten by the specific data structures in order to avoid creating an intermediate object? In fact, the generic _lmul_ and _rmul_ just lift the coefficient to the polynomial ring and multiply. I would also rewrite _mul_ and _rmul_ to use this scale_and_shift with a shift of 0 to avoid code duplication.

Yes, why not... I'm not sure it is worth the pain now—I'm not really trying to make this operation as fast as possible, just to avoid the worst of the overhead (especially in the Karatsuba range). So I'm not going to implement your suggestion now, but perhaps later, and in any case I can review the implementation if you want to do it yourself.

I will do it today then.

[tscrim]

Reviewer: Travis Scrimshaw

[tscrim]

comment:6

Running the same test as in the description.

8.3.beta0:

sage: %timeit p*q
The slowest run took 2129.02 times longer than the fastest. This could mean that an intermediate result is being cached.
100000 loops, best of 3: 8.02 µs per loop

Your branch:

sage: %timeit p*q
The slowest run took 9.36 times longer than the fastest. This could mean that an intermediate result is being cached.
100000 loops, best of 3: 2.78 µs per loop

My branch:

The slowest run took 8.63 times longer than the fastest. This could mean that an intermediate result is being cached.
100000 loops, best of 3: 2.21 µs per loop

So my changes get us an extra ~20%.

---

New commits:

4a9c966	Merge branch 'u/mmezzarobba/generic_pol_times_term' of git://trac.sagemath.org/sage into u/tscrim/generic_pol_times_term
d37db8d	Improving the speed of single term multiplication.

[tscrim]

Changed branch from u/mmezzarobba/generic_pol_times_term to u/tscrim/generic_pol_times_term-25317

[tscrim]

Changed commit from 4203441 to d37db8d

[mezzarobba]

Changed reviewer from Travis Scrimshaw to Travis Scrimshaw, Marc Mezzarobba

[mezzarobba]

Changed author from Marc Mezzarobba to Marc Mezzarobba, Travis Scrimshaw

[mezzarobba]

comment:7

Great, thanks!

[vbraun]

Changed branch from u/tscrim/generic_pol_times_term-25317 to d37db8d