A long note on Mulders' short product

Guillaume Hanrot 1 Paul Zimmermann 1
1 SPACES - Solving problems through algebraic computation and efficient software
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : The short product of two power series is the meaningful part of the product of these objects, i.e., _i+j < n a_ib_j x^i+j. In , Mulders gives an algorithm to compute a short product faster than the full product in the case of Karatsuba's multiplication . This algorithm work by selecting a cutoff point k and performing a full kk product and two (n-k)(n-k) short products recursively. Mulders also gives an heuristically optimal cutoff point n. In this paper, we determine the optimal cutoff point in Mulders' algorithm. We also give a slightly more general description of Mulders' method.
Document type :
Reports
Complete list of metadatas

https://hal.inria.fr/inria-00071931
Contributor : Rapport de Recherche Inria <>
Submitted on : Tuesday, May 23, 2006 - 7:17:49 PM
Last modification on : Thursday, January 11, 2018 - 6:20:00 AM
Long-term archiving on : Sunday, April 4, 2010 - 10:45:09 PM

Identifiers

  • HAL Id : inria-00071931, version 1

Collections

Citation

Guillaume Hanrot, Paul Zimmermann. A long note on Mulders' short product. [Research Report] RR-4654, INRIA. 2002. ⟨inria-00071931⟩

Share

Metrics

Record views

360

Files downloads

160