Re: Any interest (Wolfram or general) in fast multiply?
- 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