Fast Online Multipication of Real Numbers

摘要

We develop an online-algorithm for multiplication of real numbers which runs in time O (#MU#(n) log(n)), #MU# denotes the Schoenhage-Strassen-bound for integer multiplication which is defined by #MU#(m)=mloglog(m), and n refers to the output precision (1/2)~n. Our computational model is based on Type-2-machines: The real numbers are given by infinite sequences of symbols which approximate the reals with increasing precision. While reading more and more digits of the input reals, an algorithm for a real function produces more and more precise approximations of the desired result. An algorithm #MU# is called online, if for every n implied by IN the input-precision, which #MU# requires for producing the result with precision (1/2)~n, is approximately the same as the topologically necessary precision.