View Single Post
Old 2013-05-15, 21:42   #4
Mr. P-1
 
Mr. P-1's Avatar
 
Jun 2003

7×167 Posts
Default

Quote:
Originally Posted by Mini-Geek View Post
That page was taken (with my permission) verbatum or nearly so from a post I made here some months ago. Frankly I'm surprised it hasn't been substantially revised by someone who knows more than I do. I am very far from being the most qualified person to have written it.

Quote:
it seems to me that the number of relative primes is due to the Brent-Suyama extension e used, but I don't know exactly what memory equates to what e value.
Yes and no.

No because, as the wiki page says, the number of relative primes is computed from a different parameter, denoted by d, not from the e value.

Yes because the program tries to optimise the choice of parameters, including d and e, subject to the maximum memory available. For fixed d, a higher value of e requires slightly more memory, so it can happen that there is enough memory available for a higher e, or a larger d, but not both.

Quote:
Originally Posted by kladner View Post
I have been puzzled by this, too. Until recently, I had been allowing P95 to use 27000MB. Rather than doing 480 RP in a single pass, it would mostly do multi-pass on 960 RP.
As is perhaps obvious, the explanation I gave for how the number of relative primes is calculated is a simplification, partly because my purpose was to explain the Brent-Suyama extension, not to go into P95 internals, and partly because, although I know what the program does, I don't understand why.

Specifically what the program does is choose d to be a small primorial (30, 210 or 2310) or a multiple of one of these values smaller than the next primorial. The number of relative primes is then 8, 48, or 480, or the corresponding multiple of one of these.

But I don't understand why it would ever choose a multiple (other than the next primorial up). Apparently if it can manage to do so, then there is a slight improvement in speed, but I cannot for the life of me think of a reason why this should be so.

Quote:
A change in memory usage led me to reduce the P95 allocation to 25500MB. Now it only does 960 RP occasionally, but it is still doing multi-pass at 480 RP. It seems that somewhere in there it would find it possible to do Stage 2 in a single pass.
For exponents in the current range for P-1 assignments, I'm using 12107MB to do P-1 stage 2 in one pass with 432 relative primes, E=12.
Mr. P-1 is offline   Reply With Quote