complexity of Pepin's test

[xilman]

Originally Posted by philmoore

The benchmarks page: http://www.mersenne.org/bench.htm says that it would take a 3800 MHz Pentium-4 about 4050 years to do a LL test on a number of that size, and a Pepin test on F33 should be comparable. But a 4GB FFT size would create some problems. Interestingly enough, F31, which was considered out of reach before Alex Kruppa found a factor, would take on the order of 250 years according to the benchmarks page, which a multi-processor system could conceivably bring down to a few decades.

Aw, you spoilt it. You should have used spoiler tags.

As I said earlier, it's educational to perform the calculation for yourself.


Paul

[philmoore]

Originally Posted by xilman

Aw, you spoilt it. You should have used spoiler tags.
As I said earlier, it's educational to perform the calculation for yourself.
Paul

True, but my guess is that if the original poster didn't do the simple calculation you outlined within two days, he was probably too lazy to ever do it. I was hoping to provoke some comments from Jason or Ernst about how much more rapidly such a calculation could be done via multiprocessing.

[drew]

Originally Posted by R.D. Silverman

I think your response is a bit unfair. We can not expect others to know
how to do simple arithmetic.

Give the guy a break...this isn't merely simple arithmetic. It *does* require some knowledge of the order of complexity of a squaring operation to perform that first step. Not everybody knows this stuff off the top of their head, especially for FFT implementations.

[ewmayer]

Originally Posted by philmoore

The benchmarks page: http://www.mersenne.org/bench.htm says that it would take a 3800 MHz Pentium-4 about 4050 years to do a LL test on a number of that size, and a Pepin test on F33 should be comparable.

That strikes me as a gross underestimate. The benchmarks page says a 3800 MHz P4 needs 0.0556 seconds per iteration at an FFT length of 2048K = 2^21 doubles. Testing an F33-sized number will need an FFT length of 2^29 doubles. That means that even if we assume that the cache performance at that much-larger FFT length will be just as good as at the smaller, each iteration will need 512*(29/21) ~= 750 times as long, which works out to around 40 seconds (similar to the 1 minute per iteration I mentioned previously). Since we need to do ~2^33 iterations, that works out to over 11000 CPU-years. Since in practice cache performance is invariably going to decline with increasing dataset size (heck, just the "compact" FFT trig tables are going to be big enough to completely fill most PC's L2 caches for an F33-sized FFT), you should probably double that. (Although this is all academic at this point in time anyway.)

So I don't know what formula the benchpage is using to generate its estimates, but even if it's neglecting the log2(FFT length) part of the work estimate and assuming that per-iteration time scales linearly with FFT length, and that cache performance is independent of dataset size, it's *still* underestimating the runtime.