On 21 Oct 99, at 17:16, Grieken, Paul van wrote:
> But I thought it only took longer to complete not that the iteration
> take longer. So I can say if the number doubles it takes 4x more
> time to complete.
Very roughly, yes. There are (p-2) iterations to do for a test of
exponent p. The computer work per iteration is proportional to
N log N, where N is the FFT run length. The complication here is that
as the run length increases, the effectiveness of the computer's
cache reduces, so there are also more "wasted" cycles when the CPU
cannot work as it's waiting for operands to be fetched from memory.
Another small complication is that you can't _quite_ cover double the
range with double the FFT size. The larger FFT needs an extra bit
precision, so the range of exponents which can be covered with FFT
run length 2N is not quite twice as large as the range of exponents
which can be covered with FFT run length N.
These effects (p-2 not p, the log N factor and the FFT run length
complication) are really quite small, but the CPU cache effectiveness
fall-off _does_ have quite a noticeable effect. George's V19 code has
managed to reduce the cache fall-off somehow, this is probably the
main reason for the increase in speed over V18.
Regards
Brian Beesley
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
