Fast on-line integer multiplication

✍ Scribed by Michael J. Fischer; Larry J. Stockmeyer

• Book ID: 104148150
• Publisher: Elsevier Science
• Year: 1974
• Tongue: English
• Weight: 688 KB
• Volume: 9
• Category: Article
• ISSN: 0022-0000
• DOI: 10.1016/s0022-0000(74)80047-4

✦ Synopsis

A Turing machine multiplies binary integers on-line if it receives its inputs, low-order digit first, and produces the jth digit of the product before reading in the (j+l)st digits of the two inputs. We present a general method for converting any off-line mukiplication algorithm which forms the product of two n-digit binary numbers in timeF(n) into an on-tine method which uses time only O(F(n) Iog n), assuming thatF is monotone and satisfies n < F(n) < F(2n)[2 < hF(n) for some constant k. Applying this technique to the fast multiplication algorithm of SchSnhage and Strassen gives an upper bound of O(n (log n) ~ loglog n) for on-line multiplication of integers. A refinement of the technique yields an optimal method for on-line multiplication by certain sparse integers. Other applications are to the on-line computation of products of polynomials, recognition of palindromes, and multiplication by a constant.