A C++14-compatible physical units library with no dependencies and a single-file delivery option. Emphasis on safety, accessibility, performance, and developer experience.
We put this in a new file, probable_primes.hh. Algorithms in this
class can return one of three outcomes:
"composite" for numbers that are definitely composite
"probably prime" for all primes, and possibly some composite
numbers
"bad input" for numbers that aren't composite or prime (0 or 1), or
simply aren't appropriate inputs for that particular algorithm.
The wikipedia page[1] gives a good overview of the algorithm.
How do we know that the implementation is correct? By these main
strategies:
[x] Miller-Rabin should mark every prime number as "probably prime",
so test a large number of known primes, each with a variety of bases.
[x] Test all (odd) inputs up to a certain maximum, making sure that it
marks every prime as "probably prime", every pseudoprime to that
base as "probably prime", and every other number as "composite".
[x] Test a list of known pseudoprimes for a few given bases, and make
sure that these are all marked as "probably prime" for that base.
(Making sure that we make the "right mistakes" is a good way to build
confidence that we implemented the algorithm correctly.)
[x] Test an extremely large prime (close to the uint64_t limit), to
check that overflow hasn't crept into any of our calculations.
Given that the implementation passes all of these tests, it seems very
likely that our implementation is correct.
We put this in a new file,
probable_primes.hh. Algorithms in this class can return one of three outcomes:The wikipedia page[1] gives a good overview of the algorithm.
How do we know that the implementation is correct? By these main strategies:
[x] Miller-Rabin should mark every prime number as "probably prime", so test a large number of known primes, each with a variety of bases.
[x] Test all (odd) inputs up to a certain maximum, making sure that it marks every prime as "probably prime", every pseudoprime to that base as "probably prime", and every other number as "composite".
[x] Test a list of known pseudoprimes for a few given bases, and make sure that these are all marked as "probably prime" for that base. (Making sure that we make the "right mistakes" is a good way to build confidence that we implemented the algorithm correctly.)
[x] Test an extremely large prime (close to the
uint64_tlimit), to check that overflow hasn't crept into any of our calculations.Given that the implementation passes all of these tests, it seems very likely that our implementation is correct.
Helps #217.
[1] https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test