On Fri, Jul 13, 2018 at 2:58 PM, Tim Peters <tim.pet...@gmail.com> wrote: > [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. >
Thank you. Great explanation. Much appreciated! ChrisA _______________________________________________ Python-ideas mailing list Python-ideas@python.org https://mail.python.org/mailman/listinfo/python-ideas Code of Conduct: http://python.org/psf/codeofconduct/