Fast on-line integer multiplication
Michael J. Fischer, Larry J. Stockmeyer · 1973
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 Schonhage 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.