Maxim Dementiev's Blog

All posts are open. You are welcome to comment. Come on! :-)


Previous Entry Share Next Entry
Computing prime numbers during compilation, from-other-end version
mpd_eng

Русская версия

The canonical variant checks by the division, but I decided to create all multiplication variants and then to enumerate numbers for which there is no such variant.
As usual, I've learned a lot...
template<int N, int J=N, int I=N> struct K;

template<int N, int I> struct K<N, 1, I>
{
    void not_prim();
};

template<int N, int J> struct K<N, J, 1> : public K<N, J-1, N/(J-1) + 1>
{
    using K<N, J-1, N/(J-1) + 1>::not_prim;
    K() { char a[J] = {0}; not_prim(a); }
};

template<int N, int J, int I> struct K : public K<N, J, I-1>
{
    using K<N, J, I-1>::not_prim;
    typedef const char A[J*I];
    virtual void not_prim(const A &) const;
};

int main()
{
    K<55> k;
}

Generated by GNU Source-highlight 2.9


In fact, this is an implementation of the Sieve of Eratosthenes.

  • 1
Please, Don't be confused. Because many people start to compile it and expect it will be compiled.

But, as I mentioned at the beginning, this is a variant of a well-known observation.
Let me quote an old article:
"[3] If there is one person who is to be credited with the discovery of C++ template metaprogramming, then I believe it would have to be Erwin Unruh, who in 1994 wrote a metaprogram that calculated prime numbers at compile time and printed them out as compiler warnings."

Here you can read more http://www.drdobbs.com/184401547#3

And more, how informative or obscure the output from a compiler is, depends on how compiler developers addressed this problem. Some old compilers (Microsoft's one) do very big output from which you cannot see what is going on.

I have some output snapshots for other code in my russian version: http://mpd.livejournal.com/54014.html

Re: Output?

(Anonymous)
Here, I've used a form of "static asserts" to clean up the output (at least on g++). I did this on a simple version of factorial, but you could probably apply this to your algorithms as well.


template
[Error: Irreparable invalid markup ('<int n,>') in entry. Owner must fix manually. Raw contents below.]

Here, I've used a form of "static asserts" to clean up the output (at least on g++). I did this on a simple version of factorial, but you could probably apply this to your algorithms as well.


template <int N, int R=1>
struct fact : public fact<N-1,N*R> {
typedef typename fact<N-1,N*R>::result result;
};

template <int R>
struct fact<1,R> {
template <int r> struct result_is{
typedef int res[-r];
};
typedef result_is<R> result;
};


int main(int argc, char*argv[]) {
fact<7>::result res;
}

Re: Output?

(Anonymous)
In my sample code above, on g++ version 4.2.1, the entire output is:

err.cpp: In instantiation of ‘fact<1, 5040>::result_is<5040>’:
err.cpp:16: instantiated from here
err.cpp:9: error: creating array with negative size (‘-0x000000000000013b0’)


Re: Output?

(Anonymous)
Here's an idea (if you want to try it...)

You could define an P type and a _NIL class.

class _NIL {};

template
[Error: Irreparable invalid markup ('<int [...] n,>') in entry. Owner must fix manually. Raw contents below.]

Here's an idea (if you want to try it...)

You could define an P type and a _NIL class.

class _NIL {};

template <int N, typename Next=NIL>
class P {};

Then try to build your prime number list as a composed type, i.e.
P<1, P<3, P<5, P<7, P<11, NIL> > > >

You could use the static assert thing to cause an error with this type in the statement, and You'll probably get a nice output of the prime numbers....

What do you think?

First, I would like to thank every one who sent me the feed-back! :-)
And I hope it's interesting.

No doubt, this sample could be improved.
There is always something to improve.

But I don't think it really needs modifications: being simple and compiler/environment/platform-independent, it just works!


  • 1
?

Log in