zbMATH — the first resource for mathematics

A long note on Mulders’ short product. (English) Zbl 1161.65301
J. Symb. Comput. 37, No. 3, 391-401 (2004); erratum ibid. 66, 111-112 (2015).
Summary: The short product of two power series is the meaningful part of the product of these objects, i.e., \(\sum _{i+j<n}a_{i}b_{j}x^{i+j}\). T. Mulders [Appl. Algebra Eng. Commun. Comput. 11, No. 1, 69–88 (2000; Zbl 0968.68200)] gives an algorithm to compute a short product faster than the full product in the case of Karatsuba’s multiplication [A. A. Karatsuba and Yu. P. Ofman, Dokl. Akad. Nauk SSSR 145, No. 2, 293–294 (1962); per bibl.]. This algorithm works by selecting a cutoff point \(k\) and performing a full \(k\times k\) product and two \((n - k)\times (n - k)\) short products recursively. Mulders also gives a heuristically optimal cutoff point \(\beta n\). We determine the optimal cutoff point in Mulders’ algorithm. We also give a slightly more general description of Mulders’ method.

65B10 Numerical summation of series
12Y05 Computational aspects of field theory and polynomials (MSC2010)
Full Text: DOI
[1] Karatsuba, A.A.; Ofman, Y.P., Multiplication of multiplace numbers by automata, Dokl. akad. nauk SSSR, 145, 2, 293-294, (1962)
[2] Mulders, T., On short multiplications and divisions, Aaecc, 11, 1, 69-88, (2000) · Zbl 0968.68200
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.