mersenneforum.org Pminus1 - Bug report and feature request
 Register FAQ Search Today's Posts Mark Forums Read

2020-06-12, 19:56   #34
ewmayer
2ω=0

Sep 2002
República de California

2·5·13·89 Posts

Quote:
 Originally Posted by axn Stage 1 of P-1 is implemented in two steps, a fast(er) Stage 0 and a slow(er) regular Stage 1.
That says nothing about the algorithmic differences between the 2 sub-stages - if I had to guess, I would surmise that:

[0] 'Stage 0' is the classic fixed-upper-bound p-1 stage 1 implemented using fast left-to-right [LR] binary modexp, which for a roughly equal mix of 0s and 1s in the small-primes-powers product runs in around 2/3 the time of the right-to-left [RL] variant of binary modexp which we turn to next.

[1] The disadvantages to [0] is that the small-primes product must be precomputed and should the ensuing GCD fail to find a factor, and subsequent stage 2 also fail to find a factor, we cannot "deepen" Stage 0 to a large primes bound using the LR modexp algorithm. Thus we introduce a 'Stage 1' based on an RL modexp, which can take a Stage 0 output residue and power it to any desired larger small-primes bound, at a cost of ~1.5x per powering bit compared to Stage 0's LR modexp.

If in fact George's 'Stage 0' and 'Stage 1' refer to something different, I would appeciate a description of that.

Last fiddled with by ewmayer on 2020-06-12 at 19:57

2020-06-12, 21:09   #35
Prime95
P90 years forever!

Aug 2002
Yeehaw, FL

23·3·7·43 Posts

Quote:
 Originally Posted by ewmayer If in fact George's 'Stage 0' and 'Stage 1' refer to something different, I would appeciate a description of that.

 2020-06-13, 01:32 #36 axn     Jun 2003 10010101101102 Posts Just an update. Since switching to the new build, I've completed 60 P-1 test without any factors found. About 5 factors are expected. Could be just luck of the draw, I guess. But, if I get to 100 without factors, I might have to QC them with previous version :-( Probably I will run some with known factors first.
2020-06-14, 09:48   #37
axn

Jun 2003

479010 Posts

Quote:
 Originally Posted by axn Probably I will run some with known factors first.
A run with the new version found 16 of 17 known factors, only missing 25766609245631959384399, which is a B-S factor (different bounds between first and second run). So, everything looks fine. Just the luck of the draw, then.

 Similar Threads Thread Thread Starter Forum Replies Last Post tha Software 4 2014-02-23 21:29 TheMawn PrimeNet 3 2013-06-17 02:32 JuanTutors Software 22 2013-03-11 19:23 Bent PrimeNet 2 2008-12-07 23:22 tha PrimeNet 10 2003-12-12 15:37

All times are UTC. The time now is 15:22.

Wed Dec 2 15:22:50 UTC 2020 up 83 days, 12:33, 2 users, load averages: 3.54, 3.24, 2.57