PFGW vs LLR comparison discussion

[gd_barnes]

Originally Posted by mdettweiler

One thing that may even the tables a bit: if there's only one k left on a base, LLR's StopOnSuccess=1 option winds up behaving exactly the same way as PFGW's {number_primes,$a,1}. Even though LLR's option does the more general move of stopping the entire program versus just one k, that means the same thing when there is only one k.

I completely forgot about that. That definitely changes things slightly. If you're only running one k, then running LLR with the stoponsuccess option on is better due to the few hours that could be saved on a primality proof. This applies whether you are overloading your computer or not or running batch jobs to fill the computer's time or not.

[Mini-Geek]

Originally Posted by gd_barnes

Unanswered questions:
1. Would the percentage difference be as great for much smaller tests such as for 10,000 digits?
2. Would the percentage difference be greater for much larger tests such as for 300,000 digits?
3. Would the percentage difference be the same for larger k values such as k=~300?
4. Would the percentage difference be the same for base 2 vs. some other base such as base 5?
5. Would the percentage difference be the same in Linux?

I'll check 1, 3, and 4.

[Mini-Geek]

Environment: i5 on XP 32-bit with the other 3 cores working on other LLR 3.8.0 work
Program: LLR 3.8.0

Originally Posted by gd_barnes

1. Would the percentage difference be as great for much smaller tests such as for 10,000 digits?

A greater difference, in fact.

Raw results:

3*2^33219-1 is not prime.  LLR Res64: A376F1DAC8711F6A  Time : 627.730 ms.
7*2^33219-1 is not prime.  LLR Res64: 9E8805FFADF7975A  Time : 628.117 ms.
9*2^33219-1 is not prime.  LLR Res64: 79561A8C7B4ECD75  Time : 626.235 ms.
2*3^20959-1 is not prime.  RES64: D0BBDC84AD2E4430.  OLD64: F0BD1921158D3FE3  Time : 774.398 ms.
4*3^20959-1 is not prime.  RES64: CAE19F16E1DE1038.  OLD64: 60A4DD44A59A30A5  Time : 773.138 ms.
6*3^20959-1 is not prime.  RES64: 9855F56DADEBEFB5.  OLD64: C901E04909C3CF1C  Time : 771.612 ms.
3*2^33219-1 is not prime.  LLR Res64: A376F1DAC8711F6A  Time : 628.925 ms.
7*2^33219-1 is not prime.  LLR Res64: 9E8805FFADF7975A  Time : 625.828 ms.
9*2^33219-1 is not prime.  LLR Res64: 79561A8C7B4ECD75  Time : 627.717 ms.
2*3^20959-1 is not prime.  RES64: D0BBDC84AD2E4430.  OLD64: F0BD1921158D3FE3  Time : 774.332 ms.
4*3^20959-1 is not prime.  RES64: CAE19F16E1DE1038.  OLD64: 60A4DD44A59A30A5  Time : 771.940 ms.
6*3^20959-1 is not prime.  RES64: 9855F56DADEBEFB5.  OLD64: C901E04909C3CF1C  Time : 771.234 ms.

Results:
Average base 2 time: 627.425 ms
Average base 3 time: 772.776 ms
At 10,000 digits with very small k, base 2 is 18.81% faster than base 3.

Originally Posted by gd_barnes

3. Would the percentage difference be the same for larger k values such as k=~300?

Again, a greater difference.

Raw results:

301*2^332191-1 is not prime.  LLR Res64: 838E673AE827270E  Time : 90.516 sec.
303*2^332191-1 is not prime.  LLR Res64: 8490D6606D386526  Time : 90.488 sec.
307*2^332191-1 is not prime.  LLR Res64: 77653C95F8BAB70C  Time : 90.503 sec.
302*3^209591-1 is not prime.  RES64: 6F4E51BFDCF6E592.  OLD64: 4DEAF53F96E4B0B3  Time : 116.848 sec.
304*3^209591-1 is not prime.  RES64: 060AB7310C91F6EE.  OLD64: 7B286806ECDF83B8  Time : 117.237 sec.
310*3^209591-1 is not prime.  RES64: 7750769DF8641EEA.  OLD64: 1B27494C9B00E8EA  Time : 116.754 sec.

Results:
Average base 2 time: 90.502 sec
Average base 3 time: 116.946 sec
At 100,000 digits with k about 300, base 2 is 22.61% faster than base 3.

Originally Posted by gd_barnes

4. Would the percentage difference be the same for base 2 vs. some other base such as base 5?

About the same difference.

Raw results:

3*2^332191-1 is not prime.  LLR Res64: F7D86C663D06F365  Time : 90.509 sec.
7*2^332191-1 is not prime.  LLR Res64: F9F68E1E93C80AD4  Time : 90.423 sec.
9*2^332191-1 is not prime.  LLR Res64: 647E0ADBF224F9BB  Time : 90.590 sec.
3*5^143067-1 is not prime.  RES64: CAF5E343491784FF.  OLD64: 60E1A9C9DB468EFA  Time : 97.941 sec.
4*5^143067-1 is not prime.  RES64: 13F277C23E6E6CDE.  OLD64: 2CE26F06449181B1  Time : 97.896 sec.
6*5^143067-1 is not prime.  RES64: 57F729330E0D6FE8.  OLD64: 07E57B992A284FB5  Time : 97.920 sec.

Results:
Average base 2 time: 90.507 sec
Average base 5 time: 97.919 sec
At 100,000 digits with very small k, base 2 is 7.57% faster than base 5.

[Mini-Geek]

I have a feeling that the granularity coming from the FFT size choosing is, in a way, throwing the data off. That might explain the large difference between the tests where base 2 is about 7% faster and where it's about 20% faster than other bases.

[gd_barnes]

Originally Posted by Mini-Geek

I have a feeling that the granularity coming from the FFT size choosing is, in a way, throwing the data off. That might explain the large difference between the tests where base 2 is about 7% faster and where it's about 20% faster than other bases.

Can you explain what granularity means in this context?

I'm wondering if my I7 would have the same difference for those various small tests. I'll make time to check it later today.

[Mini-Geek]

Originally Posted by gd_barnes

Can you explain what granularity means in this context?

Since the FFT length increases in discrete jumps, the time it takes for tests does not increase linearly, (smoothly) but in big jumps, (granularly...whether I just invented that word or not ) and that the effects of those jumps might easily mean the difference between 0%, 7%, or 20% improvement (rather than only the factors we're trying to vary: digit size, base, and k).
To sum the whole statement up: take our results with a grain of salt (no pun intended), since they don't account for FFT changes.

[gd_barnes]

Originally Posted by Mini-Geek

Since the FFT length increases in discrete jumps, the time it takes for tests does not increase linearly, (smoothly) but in big jumps, (granularly...whether I just invented that word or not ) and that the effects of those jumps might easily mean the difference between 0%, 7%, or 20% improvement (rather than only the factors we're trying to vary: digit size, base, and k).
To sum the whole statement up: take our results with a grain of salt (no pun intended), since they don't account for FFT changes.

I was aware of the FFTlen jumps and that it's not a perfect squared curve on timings but I'm a little confused on how that applies here since we're testing nearly the same k-values and size in an effort to avoid such jumps or differences.

To sum it up: It seems like our results here would be useful since the FFTlen changes are non-existent due to same size tests and k-value.

Or maybe I'm not understanding something. I had assumed that FFTlen jumps would be solely related to k-value and size of the test. Could those be impacted by base also even though the other 2 variables are almost the same? If so, that would explain the differences and what we'd need to do is test across a variety of sizes and average all of the speed differences to get a better of idea of what the "real" speed difference is.

Assuming that the above is the case, then REALLY what determines the speed difference for a particular test is where it falls within the range of the FFTlen for both the base 2 and non-base 2 tests. So what we'd need to do is find somewhat similar sizes and k's and verify where that size falls within the particular FFTlen for the bases in question to get a real apples to apples comparison. As an example, if the base 2 test falls on the low end of the FFTlen (i.e. right after an increase in FFTlen), and the non-base 2 test falls on the high end of the FFTlen for that base, then there might only be a 1-2% difference or no difference at all. Whereas in the reverse scenario, we might get as much as a 25-30% difference.

This may be more complicated to test than I had imagined.

[henryzz]

Originally Posted by Mini-Geek

Since the FFT length increases in discrete jumps, the time it takes for tests does not increase linearly, (smoothly) but in big jumps, (granularly...whether I just invented that word or not ) and that the effects of those jumps might easily mean the difference between 0%, 7%, or 20% improvement (rather than only the factors we're trying to vary: digit size, base, and k).
To sum the whole statement up: take our results with a grain of salt (no pun intended), since they don't account for FFT changes.

What it would probably make sense looking at is what FFT lengths are used for the same size number for different bases.
Or at what size number the FFT length changes for different bases.
One problem with this is that AFAIK pfgw doesn't output FFT length(that has always bugged me if your reading rouge)

[Mini-Geek]

3*2^332191-1, Used fftlen = 20480
2*3^209591-1, Using FFT length 20K, a = 3
(Gary's scenario, same FFT length, 7% difference)

3*2^33219-1, Used fftlen = 1792
2*3^20959-1, Using FFT length 1792, a = 3
(scenario 1: digit length ~10,000, same FFT length, 18.81% difference)

301*2^332191-1, Used fftlen = 20480
302*3^209591-1, Using FFT length 24K, a = 3
(scenario 3: k~=300, different FFT lengths, 22.61% difference)

3*2^332191-1, Used fftlen = 20480
3*5^143067-1, Using FFT length 20K, a = 3
(scenario 4: b=5, same FFT length, 7.57% difference)

It is definitely possible to have different FFT lengths at similar k and sizes, but we'd need more data (be it experimental or by the math or viewing the code) to have any good idea of how often that happens.

I know that there's a tool called fft_len that tells you what FFT length will be used for the given k in the given n range for base 2, but I don't know about other bases.

[rogue]

Originally Posted by Mini-Geek

3*2^332191-1, Used fftlen = 20480
2*3^209591-1, Using FFT length 20K, a = 3
(Gary's scenario, same FFT length, 7% difference)

3*2^33219-1, Used fftlen = 1792
2*3^20959-1, Using FFT length 1792, a = 3
(scenario 1: digit length ~10,000, same FFT length, 18.81% difference)

301*2^332191-1, Used fftlen = 20480
302*3^209591-1, Using FFT length 24K, a = 3
(scenario 3: k~=300, different FFT lengths, 22.61% difference)

3*2^332191-1, Used fftlen = 20480
3*5^143067-1, Using FFT length 20K, a = 3
(scenario 4: b=5, same FFT length, 7.57% difference)

It is definitely possible to have different FFT lengths at similar k and sizes, but we'd need more data (be it experimental or by the math or viewing the code) to have any good idea of how often that happens.

I know that there's a tool called fft_len that tells you what FFT length will be used for the given k in the given n range for base 2, but I don't know about other bases.

PFGW has the ability to tell you the FFT length with -V. Maybe Jean has a hidden option or could add one.

[mdettweiler]

Originally Posted by rogue

PFGW has the ability to tell you the FFT length with -V. Maybe Jean has a hidden option or could add one.

I think LLR always tells you the FFT length; for its new N-1/N+1 tests you have to wait a bit for some initialization stuff to finish, but that shouldn't be more than 10-15 seconds even for very large tests.