Project

General

Profile

Slug #882

Impl faster multiplication for DUP (dense univariate polys)

Added by John Abbott almost 8 years ago. Updated almost 8 years ago.

Status:
New
Priority:
Normal
Assignee:
-
Category:
Improving
Target version:
Start date:
09 May 2016
Due date:
% Done:

0%

Estimated time:
Spent time:

Description

Christof wanted faster multiplication for DUPs.
He suggested implementing karatsuba's method.

History

#1 Updated by John Abbott almost 8 years ago

I made a very ad hoc impl of karatsuba when I was in Osnabrueck as I wanted to get an idea of when cross-over might occur (for polys in ZZ[x]). My experiments found that karatsuba became potentially faster for two polys of degree about 30 (with fairly small integer coeffs).

#2 Updated by John Abbott almost 8 years ago

I also tried implementing a method which uses fast integer multiplication in GMP.

Evaluate both polys at 1000000 (say); multiply the integers, then extract the coeffs of product by converting the result to base 1000000. My prototype was about 5 times faster than the karatsuba prototype, so this method is probably worth implementing.

Note that this method would work best if all coeffs are about the same size. It may be rather inefficient if a few coeffs are much bigger than all the others. There should not be any problem in checking the "uniformity" of the sizes of the coeffs at run time.

Also available in: Atom PDF