#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):
I have eliminated karatsuba_sumand karatsuba_diff so there are less
function calls and less if branches in the coding (we know an can predict
at each step the length of every list.
I have also eliminated most slicing of lists so less objects are creating.
The recursion does not operates over slices but over the orginial list
plus some pointers to the slice we are working on.
With this improvements the code is about 10% faster. I also think that
improves readability.
For number fields of degree 2 and 3 the code is about three times slower
than pari. For number fields of degree >=6 sage seems faster than pari.
For dense bivariate polynomials in QQ[x][y] the multiplication starts to
be faster than in QQ[x,y] for degree 16, for dense polynomials of degree
100 QQ[x][y] is 45x faster than QQ[x,y]. Of course, for non-dense
polynomials multivariate multiplication is much much faster.
Some doctests added to compare karatsuba with generic multiplication and
doctest for the non-commutative ring case.
Still has the QQbar fail.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/10255#comment:5>
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.
