*To*: mathgroup@smc.vnet.net*Subject*: [mg11173] Re: Any interest (Wolfram or general) in fast multiply?*From*: Robert Knapp <rknapp@wolfram.com>*Date*: Wed, 25 Feb 1998 03:31:45 -0500*Organization*: Wolfram Research, Inc.*References*: <6ctjok$lua@smc.vnet.net>

Wendy Hartman wrote: > > Does anyone know if Wolfram (or anyone else for that matter) has any > interest in replacing the _Integer multiplication N^1.58 code with N > logN code (i.e. Karatsuba algorithm with some form of discrete > transform such as Fourier)? I am interested in large primes, and when > you get to 10 or 20 thousand digits, a factor of Sqrt[N] would be > greatly appreciated... For a look at the discrete transform stuff see > the WEB pages dealing with GIMPS (Great Internet Mersenne Prime Search) > or Proth.exe (finds Proth's theorem primes of size tens of thousands of > digits...) ... thanks for any replies (a beginner who remembers using > Macsyma in 1973 .. vive la difference!!!) Well, I'm glad you asked. At Wolfram Research there is indeed interest, and in fact fast Fourier transform algorithms have been implemented in the version currently under development (Version 3.5). At the bottom of my reply I have included a table which shows the relative speeds of integer multiplication in Versions 3.0 and Versions 3.5. I hope you wont be disappointed by the fact that the spped gain in the 10000 digit range is not as big as you might of hoped. The reason is that while ASYMPTOTICALLY the FFT algorithm is "Sqrt[N]" faster, the asymptotic coefficients for the two methods is different (the one for the FFT method is larger). For smaller N, the Karatsuba multiplication is faster because of this. At small N, the speed advantage of the Karatsuba multiplication can also be viewed in terms of overhead. To do a multiplication with a real FFT, you have to convert the integer into a list of floating point numbers, do a convolution, and the convert the floating point numbers back to an integer, making VERY sure you introduce no error along the way. This all takes time of order N. Here are the results I computed on my Pentium Pro 200 running Linux. In the TableForm output, I just appended an extra column which was the times obtained from the Mathematica 3.5 developement version. I used the function time so that timings could be compared even when the multiplication time is so small as to be affected by the granularity of Timing. In[1]:= SetAttributes[time, HoldAll]; time[expr_] := Block[{Second = 1,t, tries = 1}, t = Timing[expr;][[1]]; While[t < 1.,tries *= 2;t = Timing[Do[expr,{tries}];][[1]]]; t/tries]; In[2]:= Table[ digits = Ceiling[2^k]; i1 = Random[Integer,{10^(digits-1), 10^digits}]; i2 = Random[Integer,{10^(digits-1), 10^digits}]; {digits, t}, {k,10,20}] // TableForm digits Version 3.0 Version 3.5 (development version) Out[2]//TableForm= 1024 0.00128906 0.00112305 2048 0.00390625 0.00339844 4096 0.0117969 0.0103906 8192 0.035625 0.0228125 16384 0.108125 0.04625 32768 0.3275 0.14625 65536 0.985 0.305 131072 2.96 1.12 262144 8.84 2.36 524288 26.56 5.39 1048576 79.81 10.63