#10255: improve karatsuba multiplication of univariate polynomials
--------------------------------+-------------------------------------------
Reporter: lftabera | Owner: AlexGhitza
Type: enhancement | Status: new
Priority: major | Milestone: sage-4.6.2
Component: basic arithmetic | Keywords: karatsuba, multiplication,
polynomial
Author: | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
--------------------------------+-------------------------------------------
Comment(by lftabera):
just for the record, I attach two images showing some numbers.
comparison_product_50_400.png Shows the number of products made to
multiply a fixed polynomial of degree 49 and another polynomial of degree
from 0 to 399.
comparison_addition_50_400.png shows the number of additions performed by
the same polynomials.
- In yellow using algorithm _mul_generic
- In red using current _mul_karatsuba as of 4.6.1
- in blue with this patch
We can appreciate that for a big difference in the degrees of the
polynomials, current _mul_karatsuba needs more additions and more products
than _mul_generic.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/10255#comment:17>
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.
