Fast On-Line Integer Multiplication.
Interim scientific rept.,
MASSACHUSETTS INST OF TECH CAMBRIDGE PROJECT MAC
Pagination or Media Count:
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 j1st 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 Fn into an on-line method which uses time only OFn log n, assuming that F is monotone and satisfies n or Fn or F2n2 or kFn for some constant k. Applying this technique to the fast multiplication algorithm of Schonhage and Strassen gives an upper bound of On log nsup 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
- Theoretical Mathematics