Fast On-Line Integer Multiplication.
Abstract
A Turing machine multiplies binary integers on-line if it receives its inputs low-order digits first and produces the jth digit of the project before reading in the (j+1)st digits of the two inputs. The authors present a general method for converting any off-line multiplication algorithm which forms the product of two n-digit binary numbers in time F(n) into an on-line method which uses time only O(F(n) log n), assuming that F is monotone and satisfies n < or = F(n) < or = F(2n)/2 < or = kF(n) for some constant k. Applying this technique to the fast multiplication algorithm of Schonhage and Strassen gives an upper bound of O(n (log n)sup 2 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. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- May 01, 1974
- Accession Number
- AD0779889
Entities
People
- Larry J. Stockmeyer
- Michael J. Fischer
Organizations
- Massachusetts Institute of Technology