A C++14-compatible physical units library with no dependencies and a single-file delivery option. Emphasis on safety, accessibility, performance, and developer experience.
Formerly, is_prime depended on find_first_factor. Now, we reverse
that dependency! This is good, because while factoring is generally
hard enough that we've built the foundations of global banking on that
difficulty, is_prime can be done in polynomial time --- and now is,
because we're using baillie_psw. We have a static_assert to make
sure it's restricted to 64 bits, but even this could probably be
removed, because there aren't any known counterexamples of any size.
For efficiency reasons, when factoring a number, it's common to do trial
division before moving on to the "fast" primality checkers. We hardcode
a list of the "first N primes", taking N=100 for now. (We could also
compute them at compile time, but this turned out to have a very large
impact on compilation times.) It should be easy to adjust the size of
this list if we decide later: there are tests to make sure that it
contains only primes, has them in order, and doesn't skip any.
The new is_prime is indeed very fast and accurate. It now correctly
handles all of the "problem numbers" mentioned in #217, as well as the
(much much larger) largest 64-bit prime.
One more tiny fix: we had switched to use std::abs in #322, but this
doesn't actually work: std::abs won't be constexpr compatible until
C++23! So as part of this change, we switch back to something that will
work.
Formerly,
is_primedepended onfind_first_factor. Now, we reverse that dependency! This is good, because while factoring is generally hard enough that we've built the foundations of global banking on that difficulty,is_primecan be done in polynomial time --- and now is, because we're usingbaillie_psw. We have astatic_assertto make sure it's restricted to 64 bits, but even this could probably be removed, because there aren't any known counterexamples of any size.For efficiency reasons, when factoring a number, it's common to do trial division before moving on to the "fast" primality checkers. We hardcode a list of the "first N primes", taking N=100 for now. (We could also compute them at compile time, but this turned out to have a very large impact on compilation times.) It should be easy to adjust the size of this list if we decide later: there are tests to make sure that it contains only primes, has them in order, and doesn't skip any.
The new
is_primeis indeed very fast and accurate. It now correctly handles all of the "problem numbers" mentioned in #217, as well as the (much much larger) largest 64-bit prime.One more tiny fix: we had switched to use
std::absin #322, but this doesn't actually work:std::abswon't beconstexprcompatible until C++23! So as part of this change, we switch back to something that will work.Fixes #217.