I have rewritten the karatsuba algorithm for
Polynomial_generic_dense_field. The code needs some cleaning, but it
is already usable at #10255
My primary personal motivation is that, for number fields as base
rings, karatsuba performs worse than the generic multiplication. For
this concrete problem is probably much better to create a custom class
(ticket #10591), but the patch at #10255 already introduces an
enhancement for several base rings that currently use
Polynomial_generic_dense_field code such as:
ZZ[I][x]: x200 faster
ZZ[I,sqrt(2)][x]: x30 faster
QuaternionAlgebra(1,1)[x]: x2 faster
SR[x]: x2 faster
PolynomialRing(MatrixSpace(QQ,2),'x'): x1.45 faster
Comparing the new code with the previous one:
- It has less function calls, less slicing of lists and less `if`
branches (this has a low impact).
- It does not perform plenty of unnecessary additions of python 0 +
ModuleElement (this has a very high impact over some base rings, like
QQ[I] and ZZ[I] due to slow coercion of python 0).
- User has ring-wise control over the karatsuba threshold to fall back
to the school method, this can speed up things in some cases. By
default the threshold 0, no school method at all, the same as the
previous implementation. But this is customizable using
PolynomialRing.set_karatsuba_thresold. This is quite ring and input
dependent and may introduce a performance penalty, so use this at your
own risk!
- The case of different sized inputs is treated differently. for
polynomials f and g of degree m-1 and n-1. The previous implementation
used as split point min(n,m)/2. I feel that it is inefficient in many
cases:
{{{
sage: K=ZZ[x]
sage: f=K.random_element(4000)
sage: g=K.random_element(2000)
sage: h=K.random_element(1500)
sage: %time _= f._mul_generic(g)
CPU times: user 0.90 s, sys: 0.00 s, total: 0.90 s
Wall time: 0.90 s
sage: %time _= f._mul_karatsuba(g)
CPU times: user 2.65 s, sys: 0.00 s, total: 2.66 s
Wall time: 2.66 s
sage: %time _= f._mul_karatsuba(h)
CPU times: user 3.41 s, sys: 0.00 s, total: 3.41 s
Wall time: 3.42 s
}}}
The new code, for f is of degree m-1 and g of degree n-1 with m<n,
consider g as:
g0 + x^m*g1 + x^(2*m)g2 + ... + x^(q*m)*gq
Compute the products f*gi recursively with karatsuba and reconstruct
f*g.
I took the idea from some documentation of an old implementation of
gmp. This is still not optimal in all cases, for instance, the pair of
degrees (6700,6000) is slightly slower than the pair of degrees
(6700,6700).
Does anyone knows any alternative that is easy to implement to
Karatsuba for different degree polynomials?
With the new code
{{{
sage: sage: K=ZZ[x]
sage: sage: f=K.random_element(4000)
sage: sage: g=K.random_element(2000)
sage: sage: h=K.random_element(1500)
sage: sage: %time _= f._mul_generic(g)
CPU times: user 0.90 s, sys: 0.00 s, total: 0.90 s
Wall time: 0.91 s
sage: sage: %time _= f._mul_karatsuba(g)
CPU times: user 0.24 s, sys: 0.00 s, total: 0.25 s
Wall time: 0.25 s
sage: sage: %time _= f._mul_karatsuba(h)
CPU times: user 0.26 s, sys: 0.00 s, total: 0.26 s
Wall time: 0.26 s
}}}
Do you think that it is a good idea to include this code in the sage
library?
Any comment and/or suggestion for improvement is welcomed.
Bests
Luis
--
To post to this group, send an email to sage-devel@googlegroups.com
To unsubscribe from this group, send an email to
sage-devel+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URL: http://www.sagemath.org
