20020925, 16:34  #1 
Aug 2002
2·3^{3} Posts 
PRP v2.3, incorrect results for k > 2^32
Hello,
When using PRP v2.3, which uses Prime95 FFTs I believe, for prp testing of number of the form k.2^n1, I noticed that when k ~> 2^32 the k value is wrapped around and incorrect. For example k=4300006275 => 5038979 Is this just a simple fix? Is testing k ~> 2^32 slower, and if so by what factor? Thanks, Michael 
20020925, 19:27  #2 
P90 years forever!
Aug 2002
Yeehaw, FL
5^{2}·311 Posts 
Yes, PRP cannot handle k > 2^32. I suggest trying WinPFGW.
The problem is the assembly code that does the mod k*2^n1 can only handle k values that fit in one register. 
20020925, 21:01  #3 
Aug 2002
2·3^{3} Posts 
Is it possible to handle larger k's in such a way as that prp tests take less than 2.3x with x the amount of time required for k < 2^32? I hope there is a better algorithm than in use by PFGW now.
PFGW presentally does handles these large k's but I find it supprising that it takes so much longer with larger k's. PFGW for my testing around 3000 digits takes 2.32.4x for a test of k > 2^32. Perhaps prp should test the k value before testing the number for probable primality? Since presentally it gives incorrect results if k is too large. 
20020926, 00:10  #4 
P90 years forever!
Aug 2002
Yeehaw, FL
5^{2}·311 Posts 
Sorry, I just checked the code. I use fscanf to get the k value from the input file. The C runtime library routine does not raise any errors and I'd rather not reimplement fscanf just to catch this case.
I really wish all PRP functionality were incorporated in PFGW so that I could cease supporting PRP. 
20020926, 00:26  #5  
Aug 2002
2·3^{3} Posts 
I agree, Rewritting fscanf would not be worth the time.
Quote:
Did you have any comment on PFGW's algorithm for k >2^32 taking 2.3x+ the amount of time for as the tests for k < 2^32? Is there a more efficient method of doing this? or what methods are you familure with to do this? 

20020926, 02:11  #6 
P90 years forever!
Aug 2002
Yeehaw, FL
5^{2}·311 Posts 
I'm not positive, but I think PFGW does not use the assembly code I wrote to do the mod k*2^n1. The C code to do this would be much slower, which is why people still use PRP. On the other hand, the PFGW C code can handle larger k values.

20020926, 02:28  #7 
Aug 2002
66_{8} Posts 
I am rather sure that PFGW uses your asm code, sinceI have tested many numbers with PRP + PFGW and the speeds are usually very close. difference < 0.1 % unless you enter a region were different FFT crossovers are used in the different programs. Perhaps just different versions of your library.
At least that is my experience with prping numbers from 1k digits to 40k digits. So its good news you may be able to retire PRP, unless you know of a counter example for timing. Oh, I found an old email from Chris Nash about the k > 2^32 slow down at: http://groups.yahoo.com/group/openpfgw/message/949 He apparentally had a version that did k > 2^32 but it had caused a FPU stall. Thanks. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Nvidia 364.xx drivers returning incorrect results  UBR47K  GPU Computing  2  20160611 22:38 
Incorrect result  bayanne  Information & Answers  2  20131201 09:18 
CPU Speed Incorrect  AZMango  Software  8  20100320 21:55 
Incorrect totals in stats  Flatlander  No Prime Left Behind  1  20081201 23:16 
Incorrect CPU profile in 22.9 and 22.8  sdbardwick  Software  5  20020922 19:49 