Fast on-line integer multiplication

摘要

A Turing machine multiplies binary integers on-line if it receives its inputs, low-order digit first, and produces the jth digit of the product before reading in the (j+1)st digits of the two inputs. We present a general method for converting any off-line multiplication algorithm which forms the product of two n-digit binary numbers in time F(n) into an on-line method which uses time only O(F(n) log n), assuming that F is monotone and satisfies n≤F(n)≤F(2n)/2≤kF(n) for some constant k. Applying this technique to the fast multiplication algorithm of Schönhage and Strassen gives an upper bound of O(n (log n)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.