[boost] Re: Compile time prime numbers, powers and roots

From: Lucas Galfaso (lgalfaso_at_[hidden])
Date: 2003-09-17 07:58:01

how you test if a number is prime. As you might know, verifying that
s^(p-1)=s mod p for a specific s, is not enough.

Lucas/

"Stephen Nutt" <snutt_at_[hidden]> wrote in message
news:000e01c37cba$aed9daa0$0d00a8c0_at_dualamd...
> Is there any interest in a set of template that generate/validate large
> prime number at compile time?  I'm using MSVC 6.0 and can validate numbers
> in the low-mid hundreds of millions, and generate them up to around 100
> million.  Eventually I get compiler limit reached errors!
>
> I've run across templates in the past that have required prime numbers to
be
> specified as a template argument, for example a fixed hash table size.
>
> Now the primality of the number can be checked at compile time
>
> template <typename T, unsigned tableSize> class hash_table
> {
>     BOOST_STATIC_ASSERT (is_prime<tableSize>::value);
>
>     T table[tableSize];
> ...
> };
>
> or if the table size is a hint
>
> template <unsigned tableSizeHint> class hash_table
> {
>     BOOST_STATIC_CONSTANT (unsigned, tableSize =
> greatest_prime_less_or_equal<tableSizeHint>::value);
>     BOOST_STATIC_ASSERT (is_prime<tableSize>::value);
>
>     T table[tableSize];
> ...
> };
>
> To accomplish this I also had to write the two following templates
>
> template <unsigned x, unsigned y> struct power;
> template <unsigned x, unsigned y> struct root;
>
> where power calculates x^y and root generates the y'th root of x.  Both
are
> integer based and I believe will handle all legal positive integer values.
>
> _______________________________________________
> Unsubscribe & other changes:
http://lists.boost.org/mailman/listinfo.cgi/boost
>