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

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?

Reply via email to