# Accession Number:

## AD0779889

# Title:

## Fast On-Line Integer Multiplication.

# Descriptive Note:

## Interim scientific rept.,

# Corporate Author:

## MASSACHUSETTS INST OF TECH CAMBRIDGE PROJECT MAC

# Personal Author(s):

# 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