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

From: Stephen Nutt (snutt_at_[hidden])
Date: 2003-09-19 22:15:53

Since there are around 200 hundred millions prime numbers in the 32 bit
unsigned integer domain space, and 4e17 primes in the 64 bit integer space,
I'm trying to find a way to avoid specialisations.  My solution now works
for all 32 bit unsigned numbers, and may even manage number in the teens of
billions, thought I cannot test this with my compiler.

I'd like a way for the author of a library to statically assert that an
integral template argument specified is prime if they desired.  Requiring
the user of this library to specialise the is_prime template for said
integer, allows them to bypass the constriction of using a prime number,
either intentionally, or by mistyping the prime number they acquired from
somewhere else.

Also, if I needed a hash table with at least 20,000 items in, and it had to
be a prime number, I wouldn't know off the top of my head what that would
be.  I'd have to search for some list on the internet.  If I needed one over
1 million I'd have to write a sieve, or find a sieve on the net and start
guessing numbers until I found one.  The templates I'm providing are to
avoid this unnecessary search step.  If you need one that is at least 1
million, use
smallest_prime_greater_or_equal<1000000>::prime
and then go on with your code.

If you want a huge prime number (40+ bits), find another solution as I do
not believe this will work.  If you need many primes (many depends upon your
compiler, the size etc), again this may not be the solution for you.

However, that said, I will do all I can to support as large a prime as I
can, and make the creation, or primality test as light and as fast as
possible.

Sorry to all those who have sent comments and remarks that I have not yet
had time to respond to.  Trying to catch up...

Stephen

----- Original Message ----- 
From: "Douglas Paul Gregor" <gregod_at_[hidden]>
To: "Boost mailing list" <boost_at_[hidden]>
Sent: Friday, September 19, 2003 11:06 AM
Subject: RE: [boost] Re: Re: Compile time prime numbers, powers and roots

> On Fri, 19 Sep 2003, Ehsan Akhgari wrote:
> > I have some rough idea in my mind which may not be
> > appropriate/implementable.  I thought of having a bunch of sorted MPL
> > sequences of prime numbers.  This way, the is_prime template does not
> > have to perform the actual calculation; it just needs to try to find the
> > number in the MPL sequences.  Because the sequences are sorted, it can
> > find the appropriate sequence by checking if the value falls between its
> > begin< > and end< >, and then look inside the correct sequence to try to
> > find the value.  The sequences' source code can be generated by a
> > runtime implementation of the algorithm, and can be applicable for large
> > numbers as well.  Of course the source code size may well be over
> > several megabytes (a guess), so maybe you can split different ranges of
> > sequences in different source files.
> >
> > You need a benchmark to see how fast this technique will be, but I guess
> > it pretty well eliminates a large number of compile-time calculations.
>
> One thing to consider: algorithmic complexity for C++ metaprograms is
> generally measured in instantiations, not based on the number of, e.g.,
> integer operations or branches. If you need a sequence of (precomputed)
> primes, an MPL sequence might be the best way. However, if you just want
> to test if a particular # is prime and you can precompute answers, you may
> very well be better off with specialization:
>
> template<> struct is_prime<2> {BOOST_STATIC_CONSTANT(bool, value = true)};
> template<> struct is_prime<3> {BOOST_STATIC_CONSTANT(bool, value = true)};
> template<> struct is_prime<5> {BOOST_STATIC_CONSTANT(bool, value = true)};
> etc, etc.
>
> Somewhere, there are some nice graphs that show how horribly compilers
> slow down when there are lots of instantiations. Executive summary:
> quadratic compile times in the number of instantiations is not uncommon.
>
> Doug
> _______________________________________________
> Unsubscribe & other changes:
http://lists.boost.org/mailman/listinfo.cgi/boost