HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

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 :
Complete list of metadata

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Tuesday, May 23, 2006 - 7:17:49 PM
Last modification on : Friday, February 4, 2022 - 3:22:03 AM
Long-term archiving on: : Sunday, April 4, 2010 - 10:45:09 PM


  • HAL Id : inria-00071931, version 1



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



Record views


Files downloads