View Single Post
Old 2013-05-15, 22:10   #5
owftheevil's Avatar
"Carl Darby"
Oct 2012
Spring Mountains, Nevada

31510 Posts

Originally Posted by Mr. P-1 View Post
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.
In each pass, it is computing E^(k*d)^e - E^rp^e for all of the relative primes that its processing, then increasing k by 2 and repeating until k*d gets up to b2. It needs 2 * e transforms for each change of k, so larger d results in fewer "change of base" operations per pass. This gain is balanced against the possible increase in the number of passes and the associated initialization costs a larger d might require.

The next primorial gives a rather dramatic increase in the number of relative primes, so sometimes the initialization costs for the increased number of passes outweighs the other advantages of the larger primorial.

Clear as mud?

Last fiddled with by owftheevil on 2013-05-15 at 22:27 Reason: Left out the base
owftheevil is offline   Reply With Quote