PRP v2.3, incorrect results for k > 2^32

Angular · 2002-09-25, 16:34

Hello,

When using PRP v2.3, which uses Prime95 FFTs I believe, for prp testing of number of the form k.2^n-1, 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

Prime95 · 2002-09-25, 19:27

Yes, PRP cannot handle k > 2^32. I suggest trying WinPFGW.

The problem is the assembly code that does the mod k*2^n-1 can only handle k values that fit in one register.

Angular · 2002-09-25, 21:01

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.3-2.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.

Prime95 · 2002-09-26, 00:10

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.

Angular · 2002-09-26, 00:26

I agree, Rewritting fscanf would not be worth the time.

Quote:

Originally Posted by Prime95

I really wish all PRP functionality were incorporated in PFGW so that I could cease supporting PRP.

What functionality does PRP have that PFGW does not?

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?

Prime95 · 2002-09-26, 02:11

I'm not positive, but I think PFGW does not use the assembly code I wrote to do the mod k*2^n-1. 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.

Angular · 2002-09-26, 02:28

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.

2002-09-25, 16:34	#1
Angular Aug 2002 54₁₀ 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^n-1, 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

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Nvidia 364.xx drivers returning incorrect results	UBR47K	GPU Computing	2	2016-06-11 22:38
Incorrect result	bayanne	Information & Answers	2	2013-12-01 09:18
CPU Speed Incorrect	AZMango	Software	8	2010-03-20 21:55
Incorrect totals in stats	Flatlander	No Prime Left Behind	1	2008-12-01 23:16
Incorrect CPU profile in 22.9 and 22.8	sdbardwick	Software	5	2002-09-22 19:49

2002-09-25, 19:27	#2
Prime95 P90 years forever! Aug 2002 Yeehaw, FL 1FDF₁₆ Posts	Yes, PRP cannot handle k > 2^32. I suggest trying WinPFGW. The problem is the assembly code that does the mod k*2^n-1 can only handle k values that fit in one register.

2002-09-25, 21:01	#3
Angular Aug 2002 110110₂ 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.3-2.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.

2002-09-26, 00:10	#4
Prime95 P90 years forever! Aug 2002 Yeehaw, FL 8159₁₀ 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.

2002-09-26, 02:11	#6
Prime95 P90 years forever! Aug 2002 Yeehaw, FL 1FDF₁₆ Posts	I'm not positive, but I think PFGW does not use the assembly code I wrote to do the mod k*2^n-1. 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.

2002-09-26, 02:28	#7
Angular Aug 2002 66₈ 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.