On 03/05/2011 01:37 PM, Chad Nelson wrote:
But explicitly naming the algorithm would preclude replacing its internals with a faster and better algorithm that might come along later. A more generic name means that any code using the function will automatically get the benefit of any improvements to it.
is_probably_prime, and a forthcoming is_definitely_prime (once I've had a chance to study the new-to-me algorithm that John Bytheway pointed out), should do pretty much everything anyone needs.
More than likely the newer, faster, algorithm will return false positives in some circumstances where the old one would not. How about: template <typename Integral_T> bool is_maybe_prime(Integral_T const &) { return true; // Cf. http://xkcd.com/221/ // return false; // alternatively } I expect most of us would object to this implementation, but the interesting question is how do you justify the objection? If the result of an algorithm is only probabalistically correct, then the really interesting discussions relate to the question of "in what ways does it diverge from the ideal?" and "what are the restrictions on the process which selected the inputs such that the probabalistic estimate remains valid?" Probably most folks who need a function to test very large numbers for primality had better be very familiar the failure modes of the algorithm in use. So the value must be computed with a documented algorithm giving a result about which testable predictions can be made. Otherwise, at the very least, it's difficult to regression test. The algorithm is an essential part of the interface, I think it should be part of the function name (or maybe supplied with template policy tag types?) - Marsh