DID YOU KNOW? DTIC has over 3.5 million final reports on DoD funded research, development, test, and evaluation activities available to our registered users. Click

HERE to register or log in.

# 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

# Distribution Statement:

## APPROVED FOR PUBLIC RELEASE

#