On Mon, 22 Mar 1999, Aaron Blosser wrote:
> The reason I thought of this was that if this is possible, would it not also
> be possible to use multiple computers on a network to work on the same
> number? With Windows OS', you could use DCOM or even just RPC to get many
> machines working on the same number.
We all wish that was the case. Unfortunately, the LL test is completely
sequential, so that the only parallelism you can hope to find in it would
be a parallel FFT. But the FFT requires all-to-all communication among
different parallel processors, and this would be far too slow over,
say, ethernet. To put it in perspective, GIMPS will soon need 512k size
FFTs, and 512k doubles means 4MB. You'll have to pump 4MB of data through
your LAN (twice per iteration) and have to do it in under a second for any
hope of a speedup. Beowulf can do this, but Beowulf isn't the norm.
Another vaguely appealing notion is to completely recode Prime95 to use
number-theoretic FFTs, have all your processors do several LL iterations
locally (much smaller FFTs too, since number theory lets you break up
the problem into bite-size chunks), and combine the results into a
single giant residue that gets mod'd and redistributed to all the
processors.
Problem is, it isn't obvious to me how (or even if) you can perform the
single subtraction the LL test requires while in "number theoretic Fourier
space". Sure, you could just subtract the FFT of 2 from the FFT of the
residue, but does that give the same answer as doing the LL test the
conventional way?
jasonp
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
