On Thu, Sep 20, 2012 at 11:36 AM, Martin D Kealey <mar...@kurahaupo.gen.nz> wrote: > On Wed, 19 Sep 2012, GitHub wrote: >> Log Message: >> ----------- >> Add expmod and is-prime as built-ins in Int > >> +Returns True if C<$x> is known to be a prime, or is likely to be a >> +prime based on a probabilistic Miller-Rabin test. (The optional >> +argument tells how many times to iterate the probabilistic test, >> +if such is necessary.) >> + >> +Returns False if C<$x> is known not to be a prime, or is unlikely to >> +be a prime after probabilistic testing. > > Isn't Miller-Rabin definitive when it disproves primality? In which case the > probabilistic qualifier in the last paragraph isn't needed.
Yes iirc correctly if the Miller-Rabin test determines it is not prime then it is certainly not prime. If it says it might be prime it's about a 50% 50% split if it's correct. Each test cycle is suppose to be fairly independent. so if it survives 1 round it's 50% prime 50% not-prime 2 75% 25% 3 87.5% 12.5% 4 93.75% 6.25% so the certainty that it is prime approaches 1 as the number of tests approaches log2 of the number then there should be less chance of a false positive than there are numbers in that range. perhaps it should return a float in the range of 0 to 1 ;-) multi method is-prime ( Int $x: Int $tries = 100) is export should also at least document that tries is never a negative number, or if it is that it has same behaviour as zero. > > Or is this just to allow that some better (presumably faster or more probable) > non-deterministic primality test might be used in the future? (Though > Miller-Rabin is already pretty fast, so there seems little reason not to > incorporate it as part of any future test.) > > But in that case, we should be saying up front that the test might change. maybe multimethod signature should allow you to pass in a test, but provide one by default?
