Re: [boost] [xint] Boost.XInt formal review

Subject: Re: [boost] [xint] Boost.XInt formal review
From: Marsh Ray (marsh_at_[hidden])
Date: 2011-03-07 15:27:35

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