Accession Number:

AD0779889

Title:

Fast On-Line Integer Multiplication.

Descriptive Note:

Interim scientific rept.,

Corporate Author:

MASSACHUSETTS INST OF TECH CAMBRIDGE PROJECT MAC

Report Date:

1974-05-01

Pagination or Media Count:

25.0

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 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

Subject Categories:

  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE