PFGW vs LLR comparison discussion

[MyDogBuster]

Everyone and his dog will be doing non base 2 work.

Buster likes work, base 2 or none base 2.

[henryzz]

Originally Posted by kar_bon

here is an example (on an i7 with 8 threads):

for 3051*2^491000-1 LLR needs about 540s (about 148000 digits).

in the same time PFGW do 2*1019^52400-1 (about 158000 digits).

so for this example PFGW is slightly faster for the same amount of digits.

The time for llr changes due to the FFT length being higher for larger ks.
Does this sort of thing affect PFGW for prp tests at all?
If not then i would guess that LLR is faster for really low ks(below NPLB territory maybe?) but slower for larger ks.
Does a change in k size make any difference to bases other than 2 in PFGW?
Again once my gnfs is finished i will do tests if people dont already know the answers.

[gd_barnes]

Originally Posted by henryzz

The time for llr changes due to the FFT length being higher for larger ks.
Does this sort of thing affect PFGW for prp tests at all?
If not then i would guess that LLR is faster for really low ks(below NPLB territory maybe?) but slower for larger ks.
Does a change in k size make any difference to bases other than 2 in PFGW?
Again once my gnfs is finished i will do tests if people dont already know the answers.

Yes, PFGW is affected by k-size in a manner similar to LLR. I know this from my Sierp base 31 testing that has a very large conjecture of k>6.3M. You might ask Mark but I think PFGW uses some or all of the same programs/routines as LLR. I don't understand the details but from what I've read of some of his posts about the changes to PFGW that make it about as fast as LLR, I have concluded as much. (...not sure if I'm wording that quite correctly.)

In other words, to do an apples to apples comparison of PFGW and LLR, you need approximately the same size k-value and # of digits in the 2 tests. Also, the k-value cannot be divisible by the base on one of the two tests and not the other because I think both programs internally reduce it to its lowest possible for the base being tested, hence allowing for a faster test.


Gary

[rogue]

Originally Posted by henryzz

The time for llr changes due to the FFT length being higher for larger ks.
Does this sort of thing affect PFGW for prp tests at all?
If not then i would guess that LLR is faster for really low ks(below NPLB territory maybe?) but slower for larger ks.
Does a change in k size make any difference to bases other than 2 in PFGW?
Again once my gnfs is finished i will do tests if people dont already know the answers.

Yes to your first question.

The main difference between PFGW and LLR for bases that are not powers of two is that PFGW uses fast modular reduction and LLR uses generic modular reduction. These routines are internal to the gwnum FFT library.

This is what you can do to compare LLR to PFGW. Test two numbers of similar decimal length and similar k values, one base 2 and one not base 2 in both. LLR will be faster for base 2. PFGW will be faster with the other base (but at least 30%). PFGW will take about the same amount of time for both tests. What this demonstrates is that LLR uses different gwnum routines for base 2 than for other bases while PFGW uses the same gwnum routines for both. It will also show that the routines used by PFGW are different than those used by LLR.

[MyDogBuster]

Rumor has it that Jean has version 3.8.0 of LLR ready to go after doing some documenting. opyrt over on the PSP board is claiming a 25% increase in speed. I'm wondering if it will do non-base 2 stuff? Should be interesting.

[rogue]

Originally Posted by MyDogBuster

Rumor has it that Jean has version 3.8.0 of LLR ready to go after doing some documenting. opyrt over on the PSP board is claiming a 25% increase in speed. I'm wondering if it will do non-base 2 stuff? Should be interesting.

I expect no differences between PFGW and LLR WRT non-base 2, presuming he is using gwnum 25.13 and fast modular reduction. The main difference between the two is that PFGW can do primality tests for those bases and LLR cannot (unless he added that feature).

I know that Jean was deciding at one point if LLR should do a primality test instead of a PRP test for non-base 2 numbers. My recommendation to him was to not do that because it would make PFGW and LLR completely incompatible for non-base 2 tests. The other issue is that primality tests for other bases can take much longer than PRP tests for those same bases.

[gd_barnes]

I ran two different tests on two different computers running two different O.S.'s comparing LLR 3.8 vs. PFGW 3.3.0 with nothing else running on either machine.

The machines were a Q6600 running Linux Ubuntu 9.04 and an I7 running Windows 7.

Both tests were for Sierp base 9 at n=~300K.

There was virtually zero difference! The I7 took ~1700 secs. on both tests and the Q6600 took ~1950 secs.

Conclusion: For fairly large non-powers-of-2 base tests, use PFGW since you can use the stop on prime option.

I think the jury is still out on smaller tests. So...

If folks could run compares on LLR 3.8 vs. PFGW 3.3.0 for all kinds of things like base 2, non-base 2, small tests, large tests, different O.S.'s, different CPUs, I'd like to get the low down on if there is any area where either LLR or PFGW is significantly faster. Do your best to avoid anything running in the background.

To Mark and Jean and/or his son (or whomever modified LLR for 3.8): Nice work on syncing up the GWNUM libraries between the 2 heavily used and quite different prime search programs!


Gary

[mdettweiler]

This jives quite well with the testing I've done. However, there is one area where LLR really shines: N-1/N+1 tests on very large numbers. For small numbers, PFGW doesn't take much longer than it takes for the original PRP test; however, the extra time to do a deterministic test really adds up for big primes. LLR, however, uses a slightly different method for those tests and does them in the same time as it takes to do a PRP.

As I mentioned over in the LLR 3.8 thread, LLR's particular method of doing N-1/N+1 is somewhat more prone to requiring that the test be run again using a different base than does PFGW's. LLR has had to re-run the test in every single example I've tried, whereas PFGW only has to do it about 20% of the time (gut estimate). For smaller tests, in fact, this usually works out so that the total time spent on a prime number with LLR equals that of PFGW--LLR's two deterministic tests vs. PFGW's PRP+proof. However, for the larger numbers, you start to see a real difference: as soon as PFGW's proof starts taking more than twice as long as the PRP test, LLR will be faster since "both" of its tests take the same time as the PRP test.

Long story short: use PFGW on small numbers, for the flexibility that Gary mentioned above and because there's hardly a difference between the two at that size. For large numbers, it's a grab bag--the speed difference only shows up when testing a large number that turns out to be prime, so it's up to the individual user as to whether they're willing to sacrifice a few more hours of CPU time (which is what it would be at the size needed to really highlight the difference) to prove what's probably a once-in-a-blue-moon prime for the added flexibility of PFGW.

[gd_barnes]

Originally Posted by mdettweiler

This jives quite well with the testing I've done. However, there is one area where LLR really shines: N-1/N+1 tests on very large numbers. For small numbers, PFGW doesn't take much longer than it takes for the original PRP test; however, the extra time to do a deterministic test really adds up for big primes. LLR, however, uses a slightly different method for those tests and does them in the same time as it takes to do a PRP.

As I mentioned over in the LLR 3.8 thread, LLR's particular method of doing N-1/N+1 is somewhat more prone to requiring that the test be run again using a different base than does PFGW's. LLR has had to re-run the test in every single example I've tried, whereas PFGW only has to do it about 20% of the time (gut estimate). For smaller tests, in fact, this usually works out so that the total time spent on a prime number with LLR equals that of PFGW--LLR's two deterministic tests vs. PFGW's PRP+proof. However, for the larger numbers, you start to see a real difference: as soon as PFGW's proof starts taking more than twice as long as the PRP test, LLR will be faster since "both" of its tests take the same time as the PRP test.

Long story short: use PFGW on small numbers, for the flexibility that Gary mentioned above and because there's hardly a difference between the two at that size. For large numbers, it's a grab bag--the speed difference only shows up when testing a large number that turns out to be prime, so it's up to the individual user as to whether they're willing to sacrifice a few more hours of CPU time (which is what it would be at the size needed to really highlight the difference) to prove what's probably a once-in-a-blue-moon prime for the added flexibility of PFGW.

For huge tests, the chance of prime is so small as to be inconsequential. I assume you're talking tests over 1,000,000 bits (300K+ digits); correct?

Here are some factors to consider regardless of the size that you searching:

1. If you "overload" your computer with 5 or 6 instances running one k at a time on a quad; almost always use PFGW with the stop on prime option. That's because even though LLR will prove the prime sometimes even hours faster, it will continue searching at the expense of other programs for likely even longer than the PFGW proof required before you notice it.
2. If you don't overload your computer in the above scenario, use LLR. You'll get a proof faster and who knows, the k that you go on searching while you're away could yield a 2nd prime.
3. If all of your cores are searching 2-3 or more k's, almost always use PFGW for almost the same reason as #1. Stopping the k from searching will almost always save more time than the extra time it takes for PFGW to prove a prime.

OK, Max, here is something you might not have thought of that tips just about everything in favor of PFGW here:

You just run PRP tests with PFGW anyway, which makes it as fast as LLR even on a prime. The time lost is that you have to do the proof eventually. But that can be done on another machine and at your leasure. In other words, it need not slow your current efforts.

Based on this, I can't personally think of a reason to use LLR for conjectures searches like at CRUS. Of course you should almost always use it for n-range testing searching such as is done at NPLB/RPS, regardless of the base, since the primality proof is faster.

BTW, I found out from someone who was doing some small n-range comparison and had found that LLR was significantly faster. That turned out not to be the case. He reported back that something else was running in the background when he was doing the PFGW testing. He implied that they were about the same speed, even on small tests.

Conclusion:
With the exception of primality proofs, mainly of large primes, PFGW 3.3.0 and LLR 3.8 are the same speed for all non-power-of-2 bases.

Recommendations for non-power-of-2 bases:
Use PFGW without intially doing primality proofs for conjecture searches.
Use LLR for full n-range testing.

I haven't tested if they are the same for base 2 yet. I also want to compare base 2 and base 3 here shortly for 100K-digit numbers with the same k-value. I'm curious as to whether there is any advantage to running base 2 anymore. I'll report those back in a little while.


Gary

[mdettweiler]

Originally Posted by gd_barnes

For huge tests, the chance of prime is so small as to be inconsequential. I assume you're talking tests over 1,000,000 bits (300K+ digits); correct?

I'm not speaking as much of a set # of bits/digits but more of a ballpark figure; the speed difference shows up to an increasingly large degree as the size of the numbers increases, such that small numbers (like the ones I'm testing right now on base 39 around n=15K) would have extremely little difference, whereas 1-2 hour PRP tests would take at least 3 times that amount for a PFGW deterministic test.

Here are some factors to consider regardless of the size that you searching:

1. If you "overload" your computer with 5 or 6 instances running one k at a time on a quad; almost always use PFGW with the stop on prime option. That's because even though LLR will prove the prime sometimes even hours faster, it will continue searching at the expense of other programs for likely even longer than the PFGW proof required before you notice it.
2. If you don't overload your computer in the above scenario, use LLR. You'll get a proof faster and who knows, the k that you go on searching while you're away could yield a 2nd prime.
3. If all of your cores are searching 2-3 or more k's, almost always use PFGW for almost the same reason as #1. Stopping the k from searching will almost always save more time than the extra time it takes for PFGW to prove a prime.

Actually, I do something a bit more precise than #1: I usually like to queue things up using the bash command line so that as soon as one application finishes, another immediately takes its place. That way, I can (for example) set it so that if it finishes the last prime on a base (or just plain finishes the range), it rolls straight into something like PRPnet or Prime95 which can keep the core busy until I can manually attend to it. That way there's no wasted time whatsoever.

For those of you who aren't familiar with this, you can string up multiple commands in bash (the terminal prompt used in Linux, and in Cygwin on Windows) by separating the commands with a semicolon. They will each run in sequence. As an example:

./pfgw.exe -l sierp39-10K-25K.txt; cd ../prpnet/1; ./prpclient.exe

Alternatively, you can put one command on each line in a shell script or batch file; it accomplishes the same thing. Semicolons are just a way provided in bash for cases where you can't give a newline (such as directly on the command line).

OK, Max, here is something you might not have thought of that tips just about everything in favor of PFGW here:

You just run PRP tests with PFGW anyway, which makes it as fast as LLR even on a prime. The time lost is that you have to do the proof eventually. But that can be done on another machine and at your leasure. In other words, it need not slow your current efforts.

Based on this, I can't personally think of a reason to use LLR for conjectures searches like at CRUS. Of course you should almost always use it for n-range testing searching such as is done at NPLB/RPS, regardless of the base, since the primality proof is faster.

Yeah, it's not a huge difference for the reasons you outlined. See below for my comments on your recommendations based on this...

BTW, I found out from someone who was doing some small n-range comparison and had found that LLR was significantly faster. That turned out not to be the case. He reported back that something else was running in the background when he was doing the PFGW testing. He implied that they were about the same speed, even on small tests.

Conclusion:
With the exception of primality proofs, mainly of large primes, PFGW 3.3.0 and LLR 3.8 are the same speed for all non-power-of-2 bases.

Recommendations for non-power-of-2 bases:
Use PFGW without intially doing primality proofs for conjecture searches.
Use LLR for full n-range testing.

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.

Personally, what I'd do is run PRP tests with PFGW, then prove separately for most conjecture searches. However, when there's only one k left, I would consider using LLR since the additional flexibility of PFGW's stop-on-prime setting is moot. For full n-range testing, definitely LLR, no question.

I haven't tested if they are the same for base 2 yet. I also want to compare base 2 and base 3 here shortly for 100K-digit numbers with the same k-value. I'm curious as to whether there is any advantage to running base 2 anymore. I'll report those back in a little while.

I would imagine that PFGW and LLR would take just as long for base 2 tests, though at any rate since their residuals are not compatible, I'd recommend using LLR whenever possible even for a conjecture search. It can be somewhat of a pain to have to sort out which tests are PRP residuals and which are LLR in future doublechecking--possibly an even greater pain than the extra effort of having to work around LLR's coarser stop-on-prime setting. Given that all of the bases 2 are at high enough levels that primes are far and few, methinks that stop-on-prime is not a hugely big deal as you won't likely be able to get too far past a prime before you notice it manually anyway.

As for whether there's an advantage to running base 2 on the same k-value and digit size, just on a hunch I'd guess that they're the same. I guess we'll just have to wait and see though...

[gd_barnes]

No more guessing on this one. I've heard that there is no difference between base 2 and non-base 2 tests with the new version of LLR. I was skeptical so I figured I'd prove it to myself because I'm not sure that people used the exact same or a very similar k-value when testing:

Tests: 100,000 digits

Base 2: k=3, 5, & 7, n=~332191

Base 3: k=2, 4, & 8, n=~209591
(k=6 is effectively the same as k=2)

Machine: New I7 running Windows 7 with only 2 other cores running so as to not have any cores slowed by the hyper-threading of > 4 cores.

Program used: LLR 3.8

Assumption: LLR is as fast or faster than PFGW for base 2.

Results:
Average time for 3 tests in base 2: 94 secs.
Average time for 3 tests in base 3: 101 secs.

Conclusion:
Base 2 is ~7% faster for 100,000 digit tests on base 2 vs. base 3 for the same k size.

Therefore:
Base 2 is still the best bang for the buck in prime searching but not by very much!

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?


Tim, Max, Ian, or anyone else who likes to do compares of such things, feel free to give your comparisons here. If doing base 2 vs. base 3, use the above approximate n-values so that both bases are testing 100,000 digits.


Gary