#10255: Correct karatsuba multiplication of univariate polynomials for different
degree polynomials
-------------------------------------+-------------------------------------
Reporter: lftabera | Owner: AlexGhitza
Type: defect | Status: needs_review
Priority: major | Milestone: sage-6.1
Component: basic arithmetic | Resolution:
Keywords: karatsuba, | Merged in:
multiplication, polynomial | Reviewers: Marc Mezzarobba
Authors: Luis Felipe | Work issues:
Tabera Alonso | Commit:
Report Upstream: N/A | f6cd17edfaaa9ef285174579417855ebae41ae73
Branch: | Stopgaps:
u/mmezzarobba/10255-karatsuba |
Dependencies: |
-------------------------------------+-------------------------------------
Changes (by mmezzarobba):
* commit: 4d08ddff868a930de116c31163af910ea33b3d7d =>
f6cd17edfaaa9ef285174579417855ebae41ae73
* branch: u/lftabera/ticket/10255 => u/mmezzarobba/10255-karatsuba
* reviewer: => Marc Mezzarobba
Comment:
I for one believe that having a reasonable generic multiplication is
important, no matter how much faster specialized implementations can be.
The implementation in this ticket is a significant improvement over the
existing one. The code looks fine to me and works well on all examples I
tried.
(There are still, e.g., a few list copies that would be nice to avoid, but
this does not look easy to do without changes to the not-so-uniform
interface of polynomials. In any case, this is not a reason to further
delay this ticket IMO. Same goes for the other improvements I can think
of.)
A few minor points though, all related to documentation and tests:
* Shouldn't the test in the docstring of `do_karatsuba_different_size`
read
{{{
sage: K = ZZ[x]
sage: f = K.random_element(21) # instead of 28
sage: g = K.random_element(34)
sage: f*g - f._mul_karatsuba(g,0)
0
}}}
in accordance with the comment about Fibonacci numbers?
* The tests that call `random_element()` should probably use
`sage.misc.random_testing`.
* I pushed a commit with minor changes to some docstrings and comments (no
code change). Could you please have a look and tell me if you agree with
my changes?
----
New commits:
||[[http://git.sagemath.org/sage.git/commit/?id=f6cd17e|f6cd17e]]||{{{Improved
Karatsuba: cosmetic changes to docstrings and comments}}}||
--
Ticket URL: <http://trac.sagemath.org/ticket/10255#comment:26>
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 unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/groups/opt_out.
