[perl6/specs] 5277fe: Add expmod and is-prime as built-ins in Int
Branch: refs/heads/master Home: https://github.com/perl6/specs Commit: 5277fefed694bbdfc3e5da1022ceaf5aacb6d344 https://github.com/perl6/specs/commit/5277fefed694bbdfc3e5da1022ceaf5aacb6d344 Author: Larry Wall Date: 2012-09-19 (Wed, 19 Sep 2012) Changed paths: M S32-setting-library/Numeric.pod Log Message: --- Add expmod and is-prime as built-ins in Int
Re: [perl6/specs] 5277fe: Add expmod and is-prime as built-ins in Int
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. 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. -Martin
Re: [perl6/specs] 5277fe: Add expmod and is-prime as built-ins in Int
On Thu, Sep 20, 2012 at 11:36 AM, Martin D Kealey 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?
Re: [perl6/specs] 5277fe: Add expmod and is-prime as built-ins in Int
On Thu, 20 Sep 2012, Stephen Pollei wrote: > If it says it might be prime it's > about a 50% 50% split if it's correct. According to Wolfram, it's 75/25; so a positive result after 10 iterations leaves about a one-in-a-million chance of being composite (more precisely, one in 1048576). > 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. Logically if "tries" is zero, is-prime shouldn't do any testing at all, and should always return "true". (There's a chance it might be prime!) If "tries" is negative, which idiom should we follow: * a range iterator (empty, zero tries, return true) * arrays etc count-backwards-from-the-end (keep trying until certain) * a logical ambiguity (return Any(true,false)) * you-get-what-you-ask-for (return "PEBKAC":but(false) ) * a logical contradiction (return an unthrown exception) * a formal error (throw an exception) -Martin
Re: [perl6/specs] 5277fe: Add expmod and is-prime as built-ins in Int
On Thu, Sep 20, 2012 at 9:22 PM, Martin Kealey wrote:
> On Thu, 20 Sep 2012, Stephen Pollei wrote:
> According to Wolfram, it's 75/25; so a positive result after 10 iterations
> leaves about a one-in-a-million chance of being composite (more precisely,
> one in 1048576).
I'd believe wolfram over me, it's been a while since I've read Applied
Cryptography by Schneier .
>> 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.
>
> Logically if "tries" is zero, is-prime shouldn't do any testing at all, and
> should always return "true". (There's a chance it might be prime!)
A good built in test before you try Miller-Rabin is at least test
against some of the small prime numbers 2,3,5,7,11,13 otherwise even
if if tries is zero saying 42 is prime is too wrong . However if only
a miller-rabin style tests are used then a value of tries being zero
should always return true.
> If "tries" is negative, which idiom should we follow:
multi method is-prime ( Int $x: UInt $tries = 100) is export
I think I read somewhere that perl6 has both Int and UInt , just
change the prototype
multi method is-prime ( Int $x: UInt $tries = 100 where { $^n > 0 } ) is export
I think I even read you can constrain it so if zero tries is
completely useless you can outlaw it
so document at least or change prototype to account for negative and
zero values.
Re: [perl6/specs] 5277fe: Add expmod and is-prime as built-ins in Int
A quick search throws up http://primes.utm.edu/prove/prove2_3.html
Which says that for/n/< 341,550,071,728,321 it is enough to test 2, 3,
5, 7, 11, 13 and 17 to be definitive (and fewer specific tries for
smaller n)
That also verifies the 75/25 figures mentioned below.
So, depending on the implementation, the documentation should be able to
be explicit about how accurate it is.
R.
On 21/09/2012 06:32, Stephen Pollei wrote:
On Thu, Sep 20, 2012 at 9:22 PM, Martin Kealey wrote:
On Thu, 20 Sep 2012, Stephen Pollei wrote:
According to Wolfram, it's 75/25; so a positive result after 10 iterations
leaves about a one-in-a-million chance of being composite (more precisely,
one in 1048576).
I'd believe wolfram over me, it's been a while since I've read Applied
Cryptography by Schneier .
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.
Logically if "tries" is zero, is-prime shouldn't do any testing at all, and
should always return "true". (There's a chance it might be prime!)
A good built in test before you try Miller-Rabin is at least test
against some of the small prime numbers 2,3,5,7,11,13 otherwise even
if if tries is zero saying 42 is prime is too wrong . However if only
a miller-rabin style tests are used then a value of tries being zero
should always return true.
If "tries" is negative, which idiom should we follow:
multi method is-prime ( Int $x: UInt $tries = 100) is export
I think I read somewhere that perl6 has both Int and UInt , just
change the prototype
multi method is-prime ( Int $x: UInt $tries = 100 where { $^n > 0 } ) is export
I think I even read you can constrain it so if zero tries is
completely useless you can outlaw it
so document at least or change prototype to account for negative and
zero values.
Re: [perl6/specs] 5277fe: Add expmod and is-prime as built-ins in Int
On Mon, Sep 24, 2012 at 10:09 AM, Richard Nuttall wrote: > A quick search throws up http://primes.utm.edu/prove/prove2_3.html > > Which says that for/n/< 341,550,071,728,321 it is enough to test 2, 3, 5, 7, > 11, 13 and 17 to be definitive (and fewer specific tries for smaller n) > > That also verifies the 75/25 figures mentioned below. > > So, depending on the implementation, the documentation should be able to be > explicit about how accurate it is. Niecza's implementation of is-prime already takes advantage of this, and my understanding of Rakudo's implementation is that it always tests against the first 256 primes, so it also takes advantage of this in correctness, if possibly not in speed. -- Solomon Foster: colo...@gmail.com HarmonyWare, Inc: http://www.harmonyware.com
