A long note on Mulders' short product
The short product of two power series is the meaningful part of the product of these objects, i.e., Sigma(i+j <n) a(i)b(j)x(i+j). Mulders (AAECC 11 (2000) 69) gives an algorithm to compute a short product faster than the full product in the case of Karatsuba's multiplication (Karatsuba and Ofman, Dokl. Akad. Nauk SSSR 145 (1962) 293). This algorithm works by selecting a cutoff point k and performing a full k x k product and two (n - k) x (n - k) short products recursively. Mulders also gives a heuristically optimal cutoff point fin. In this paper, we determine the optimal cutoff point in Mulders' algorithm. We also give a slightly more general description of Mulders' method. (C) 2003 Elsevier Ltd. All rights reserved.
mulders' algorithm karatsuba model