MathGroup Archive 1998

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: Any interest (Wolfram or general) in fast multiply?

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

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]]];
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
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

  • Prev by Date: Re: Computing my own function efficiently
  • Prev by thread: Any interest (Wolfram or general) in fast multiply?
  • Next by thread: Iterative Type Programming