Calculating increase in testing time

[mdettweiler]

I recall that, on numerous occasions, Gary mentioned that primality testing time increases proportionately to the square of the n-range, and I think he mentioned it holds true for other bases as well. However, I'm having a hard time utilizing this rule to calculate the expected testing time at n=2M on my R2 odd-n reservation based on what I'm seeing at n=1.6M.

What I tried doing was setting it up as a standard proportion and solving for x (the number of hours to do a test at 2M). Since tests are taking almost exactly 1 hour apiece at 1.6M, that would be:

When I solve for x, I get x = 1.5625. But that can't be right--only ~1.5 hours for a 2M test? As I recall, when we did Sierp. base 4 tests at that level a few years ago they took about 4 hours.

I'm sure there's something exceedingly simple that I missed about this. If someone could enlighten me as to where I went wrong, it would be greatly appreciated!

[axn]

Originally Posted by mdettweiler

When I solve for x, I get x = 1.5625. But that can't be right--only ~1.5 hours for a 2M test?

Sounds about right. Naturally, this is only true if the tests are for same base and same/similar sized k's.

[Mini-Geek]

Just calculated this data:
approx. time for 349*2^1000000-1: 980s (FFT 64K, ~.98 ms/iter * 1M iter)
approx. time for 349*2^1600000-1: 3040s (FFT 112K, ~1.9 ms/iter * 1.6M iter)
approx. time for 349*2^2000000-1: 4200s (FFT 128K, ~2.1 ms/iter * 2M iter)
ratio 2M/1.6M: 1.3816

Looks about right to me. In fact, because of where they fall in the FFT divisions, (see table) the ratio is lower than your theoretical one of 1.5625.

k = 349
n(min) = 1000000
n(max) = 2000000

The following FFT lengths would be used:

    fftlen       nmax
-----------------------
     65536    1048197
     81920    1301999
     98304    1550800
    114688    1802602
    131072    2060403

Maybe the base 4 tests you're referring to were themselves closer to n=2M, (being equivalent to 2^4M) or were on a slower CPU? At 1 hour for 2^1.6M, you should expect to take 4 hours per test at 2^3.2M or 4^1.6M.

[mdettweiler]

Originally Posted by Mini-Geek

Just calculated this data:
approx. time for 349*2^1000000-1: 980s (FFT 64K, ~.98 ms/iter * 1M iter)
approx. time for 349*2^1600000-1: 3040s (FFT 112K, ~1.9 ms/iter * 1.6M iter)
approx. time for 349*2^2000000-1: 4200s (FFT 128K, ~2.1 ms/iter * 2M iter)
ratio 2M/1.6M: 1.3816

Looks about right to me. In fact, because of where they fall in the FFT divisions, (see table) the ratio is lower than your theoretical one of 1.5625.

k = 349
n(min) = 1000000
n(max) = 2000000
 
The following FFT lengths would be used:
 
    fftlen       nmax
-----------------------
     65536    1048197
     81920    1301999
     98304    1550800
    114688    1802602
    131072    2060403

Maybe the base 4 tests you're referring to were themselves closer to n=2M, (being equivalent to 2^4M) or were on a slower CPU? At 1 hour for 2^1.6M, you should expect to take 4 hours per test at 2^3.2M or 4^1.6M.

Hey, would you know! Thanks axn and Mini-Geek--glad to hear I was on the right track.

Regarding the base 4 tests, see here, from our earlier mini-drive on S4 k=64494. In that post is a figure of 7000 seconds/test--about 1 hour 56 minutes--at 885K base 4 (n=1.7M base 2). Perhaps it's all in the k--k=39687 on my R2-odd reservation vs. k=64494 on the S4 mini-drive?

[gd_barnes]

Max, it's easier to do simple division and square it:

( 2M / 1.6M ) ^ 2 = 1.5625 or 56.25% longer for n=2M vs. n=1.6M tests.

That's it.

The main factor here is where the fftlen changes lie. If the ratio of the division, i.e. 2M/1.6M, is large, the fftlen change points will have little effect on this ratio but if it is small, they will have a greater effect. In this case, the ratio is fairly small at 1.25 so your n=2M tests would likely be anywhere from ~35% to 75% longer.

[mdettweiler]

Originally Posted by gd_barnes

Max, it's easier to do simple division and square it:

( 2M / 1.6M ) ^ 2 = 1.5625 or 56.25% longer for n=2M vs. n=1.6M tests.

That's it.

The main factor here is where the fftlen changes lie. If the ratio of the division, i.e. 2M/1.6M, is large, the fftlen change points will have little effect on this ratio but if it is small, they will have a greater effect. In this case, the ratio is fairly small at 1.25 so your n=2M tests would likely be anywhere from ~35% to 75% longer.

Ah, right, I hadn't throught of that...I'll remember that for the future, it should indeed be somewhat quicker than having to worry about all those huge squared numbers on paper.