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

From: Douglas Paul Gregor (gregod_at_[hidden])
Date: 2003-09-19 10:06:33

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