Boost logo

Boost :

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
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

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


----- 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:

Boost list run by bdawes at, gregod at, cpdaniel at, john at