Fast On-Line Integer Multiplication

A Turing machine multiplies on-line if it receives its inputs low order digits first and it produces the k-th output digit before reading in the (k+1)-st inputs. We present a general method for converting any off-line multiplication algorithm which forms the product of two n-bit binary numbers in time F(n) into an on-line method, and the new algorithm requires time only 0(F(n) log n). Applying this technique to the fast multiplication algorithm of Schönhage and Strassen gives an upper bound of 0(n (log n) 2 log log n) for on-line multiplication of integers. Other applications are to the on-line problems of products of polynomials over a finite ring, recognition of palindromes, and multiplication by a constant.

Authors

• Michael J. Fischer
• Larry J. Stockmeyer

Keywords

No keywords are indexed for this paper.