#10255: improve karatsuba multiplication of univariate polynomials
--------------------------------+-------------------------------------------
Reporter: lftabera | Owner: AlexGhitza
Type: enhancement | Status: new
Priority: major | Milestone: sage-4.6.1
Component: basic arithmetic | Keywords: karatsuba, multiplication,
polynomial
Author: | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
--------------------------------+-------------------------------------------
Comment(by lftabera):
Further improvements for polynomials of of different sizes:[[BR]]
if f is of degree m-1 and g is of degree n-1 with m<n, consider g
as:[[BR]]
{{{
g0 + x^m*g1 + x^(2*m)g2 + ... + x^(q*m)*gq
}}}
Compute the products f*gi with karatsuba and reconstruct f*g[[BR]]
With this strategy, for polynomials of degree 849 and 449 I get:[[BR]]
214507 additions[[br]]
39942 products[[br]]
Far better from previous method. Anyway this is not optimal and it is hard
to messure the recursion overhead. I have taken this strategy from old
versions of gmp documentation.
Some timmings (Debian 64bits). All polyomials have been generated with
random_element without further parameters. Pure karatsuba without
threshold for better comparison with old code. With an appropriate
threshold the timming whould slightly better.[[br]]
Note that for rigns like QQ[x] and GF(2)[x] sage uses faster special
libraries (FLINT, NTL and the like).
Degree f:1000,g:1000
{{{
QQ[x]
old code: 828 ms
new code: 498 ms
GF(2)[x]
old code: 284 ms
new code: 99.1 ms
QQ[sqrt(2)][x]
old code: 2.61 s
new code: 480 ms # 5 times faster
ZZ[x]['y']['z']['t']
old code: 86.95 s
new code: 71.10 s
}}}
degree f:849, g:449
{{{
QQ[x]
old code: 988 ms
new code: 343 ms
GF(2)[x]
old code: 148 ms
new code: 67.6 ms
QQ[sqrt(2)][x]
old code: 1.93 s
new code: 313 ms #6 times faster
ZZ[x]['y']['z']['t']
old code: 342.16 s
new code: 48.11 s # 7 times faster
}}}
degree 3, 5
{{{
QQ[x]
old code: 135 µs
new code: 83.6 µs
GF(2)[x]
old code: 137 µs
new code: 100 µs
QQ[sqrt(2)][x]
old code: 323 µs
new code: 86.4 µs
ZZ[x]['y']['z']['t']
old code: 19.5 ms
new code: 13.2 ms
}}}
TODO:[[br]]
- Sensible default threshold.[[br]]
- Documentation cleanup. (almost done)[[br]]
- More testing for correctness rather than speed. This is a very basic
feature, so we cannot allow correctness bugs here.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/10255#comment:3>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
