[Chris Angelico, on "probable prime" testers]
> You can say that about algorithms easily enough. My point is that this
> ought to be a constraint on the function - implementations may choose
> other algorithms, but they MUST follow one pattern or the other,
> meaning that a Python script can depend on it without knowing the
> implementation. Like guaranteeing that list.sort() is stable without
> stipulating the actual sort algo used.
>
I agree! Don't worry about it - if this module gets added, I'll make sure
of it. My own "probable prime" function starts like so:
def pp(n, k=10):
"""
Return True iff n is a probable prime, using k Miller-Rabin tests.
When False, n is definitely composite.
"""
In the context of algorithmic number theory, "no false negatives" is
implied by that context, but it should be spelled out anyway. A "probable
prime", by definition, is an integer that satisfies some property that
_all_ primes satisfy, but that some composites may satisfy too. The
variation among probable prime algorithms is in which specific
property(ies) they test for.
For example:
def pp1(n):
return True
meets the promise, but is useless ;-)
def pp2(n):
return n % 3 != 0 or n == 3
is slightly less useless.
But
def pp3(n):
return n % 3 != 0
would be incorrect, because pp3(3) returns False - `n % 3 != 0` is not a
property that all primes satisfy.
_______________________________________________
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/
