Meta-Programming Challenge

Generate a table of primes at compile time

  • (2 Pages)
  • +
  • 1
  • 2

18 Replies - 7723 Views - Last Post: 14 June 2009 - 09:16 PM Rate Topic: -----

#1 NickDMax  Icon User is offline

  • Can grep dead trees!
  • member icon

Reputation: 2250
  • View blog
  • Posts: 9,245
  • Joined: 18-February 07

Meta-Programming Challenge

Post icon  Posted 05 June 2009 - 03:46 PM

Some resurrected an old "is prime" thread and it got me to thinking -- a fast way to determine if numbers are prime or not is to have a table of prime numbers to start from. Now one could just initialize an array by pasting the numbers from one of the many lists of primes out on the web, or writing a small program to generate the list and pasting the result from there -- But where is the fun in that.

The challenge: Write a meta-program that can initialize an array (or vector if you choose) with the first N primes. -- That is the array must be initialized at compile time without directly listing a bunch of primes. We should be able to offer an argument for the number of primes required.

Example usage when N=100:

int primes[100] = FindPrimes<100>::Array; // initializes an array with the first 100 prime numbers. primes[0] = 2

Of course the exact syntax is up to you (I am not even sure if the above is even possible). I am not even sure the challenge is possible (well I am pretty sure that I can do it... could be wrong though).

I have not worked this out myself already so I am going to work on it on my own. However, collaborative work IS allowed. You can use the Preprocessor or template meta programming or a combination (which is where I am leaning or am I just trying to throw you off track?).

A good place to start might be: Template Meta Programming and Number Theory.

Good Luck

Is This A Good Question/Topic? 0
  • +

Replies To: Meta-Programming Challenge

#2 NickDMax  Icon User is offline

  • Can grep dead trees!
  • member icon

Reputation: 2250
  • View blog
  • Posts: 9,245
  • Joined: 18-February 07

Re: Meta-Programming Challenge

Posted 06 June 2009 - 08:47 AM

I don't know if anyone else is participating in this -- but here is my update:

I managed to get a NextPrime<n, end>::value thing going so I can now enumerate primes but this is turning out to be less helpful than I thought. I don't think you can really make a template initialized array so I was looking into the preprocessor (thinking about something along the lines of this snippet) -- BUT while this lets me generate a list of primes, the list has duplicates.

basically after the preprocessor gets done I end up with:
int primes = { 
NextPrime<1, 1+20>::value, 
NextPrime<2, 2+20>::value,
NextPrime<3, 3+20>::value,
NextPrime<4, 4+20>::value,
NextPrime<5, 5+20>::value,
};


which list 2 and 5 twice...

Can one create template namespaces? that would be awesome as you can add names to namespace... but I doubt it is possible.

If I keep the maximum array size pretty low, then I can probably do something recursive like:

NextPrime<n, end>::value,
NextPrime<n, end>::NextPrime<n+1, end>::value

Anyway, one direction I did find but currently am not persuing is from this example from a wiki-book. -- This creates a template function to print out primes -- I would imagine that this could be changed to initialize an array rather than just produce output.

SO while I still don't know for sure if this is possible -- I think that the evidence is mounting that it is.

Has anyone else been working on this?
Was This Post Helpful? 0
  • +
  • -

#3 NickDMax  Icon User is offline

  • Can grep dead trees!
  • member icon

Reputation: 2250
  • View blog
  • Posts: 9,245
  • Joined: 18-February 07

Re: Meta-Programming Challenge

Posted 06 June 2009 - 10:14 AM

Well it turns out that you can call templates recursively like so:
FindNextPrime< FindNextPrime< FindNextPrime< FindNextPrime<1>::value + 1>::value + 1 >::value + 1 >::value 


(at least on Borland 55 and MinGW )

So I am getting really close: I have
	int aPrimes[] = { 
		PA_BUILDER_1, 
		PA_BUILDER_2, 
		PA_BUILDER_3, 
		PA_BUILDER_4, 
		PA_BUILDER_5,
		PA_BUILDER_6,
		PA_BUILDER_7,
		PA_BUILDER_8,
		PA_BUILDER_9,
		PA_BUILDER_10,	   
	};
which is not quite to a general solution yet, but close.
Was This Post Helpful? 0
  • +
  • -

#4 NickDMax  Icon User is offline

  • Can grep dead trees!
  • member icon

Reputation: 2250
  • View blog
  • Posts: 9,245
  • Joined: 18-February 07

Re: Meta-Programming Challenge

Posted 06 June 2009 - 11:48 AM

ok, here is my initial solution. It is very limited and can only create an array with up to 10 elements -- but I think it represents a good "proof of concept".

#include <iostream>
/** 
 * This is my first complete attempt at generating an array of prime numbers
 *   at compile time.
 *
 * The fist few template function are by Zeeshan Amjad and can be located at:
 *   http://www.codeproject.com/KB/recipes/meta_programming.aspx
 *   http://www.codeguru.com/cpp/misc/misc/math/article.php/c14087
 * 
 * The remaining program is by NickDMax @ DreamInCode
 *
/* ______________ FOLLOWING TEMPLATE FUNCTIONS ARE BY: Zeeshan Amjad____________*/
template <int u, int v>
struct Divisible
{
	enum { value = u % v == 0 ? 1 : 0 };
};

// check divide by zero condition
template <int u>
struct Divisible<u, 0>
{
	enum { value = -1 };
};

// loop for total no of divisors
template <int Start, int End>
struct NumDivisorsLoop
{
	enum { value = (Divisible<End, Start>::value + NumDivisorsLoop<Start + 1, End>::value) };
};
// partial specialization to terminate loop

template <int End>
struct NumDivisorsLoop<End, End>
{
	enum { value = 1 };
};
// number of divisor of any digit

template <int n>
struct NoOfDivisor
{
	enum { value = NumDivisorsLoop<1, n>::value };
};

/*_________ END OF CODE BY Zeeshan Amjad _______________________________________*/

template <int n, int end>
struct NextPrime {
	enum { value = (NoOfDivisor<n>::value == 2 ? n : NextPrime<n+1, end>::value) };
};

template <int end>
struct NextPrime<1, end> {
	enum { value = 2 };
};

template <int End>
struct NextPrime<End, End>
{
	enum { value = 0 };
};


#define NEXT_PRIME_DEPTH 20
template <int n>
struct FindNextPrime {
	enum { value = (NextPrime<n+1, n + NEXT_PRIME_DEPTH>::value) };
};
#undef NEXT_PRIME_DEPTH

template <int n>
struct GetPrime {
	enum { value = (FindNextPrime< GetPrime<n-1>::value >::value) };
};

template <>
struct GetPrime<1> {
	enum { value = (FindNextPrime< 1 >::value) };
};


#ifndef INIT_ARRAYS_MACRO
#   define INIT_ARRAYS_MACRO
#   define INIT_PRIME_ARRAY(size) { LIST_PRIMES( size , 1) }
#   define LIST_PRIMES(ones, value) LIST_PRIMES_ ## ones (value)
#   define LIST_PRIMES_10(v) LIST_PRIMES_9(v), GetPrime<v+9>::value 
#   define LIST_PRIMES_9(v) LIST_PRIMES_8(v), GetPrime<v+8>::value
#   define LIST_PRIMES_8(v) LIST_PRIMES_7(v), GetPrime<v+7>::value
#   define LIST_PRIMES_7(v) LIST_PRIMES_6(v), GetPrime<v+6>::value
#   define LIST_PRIMES_6(v) LIST_PRIMES_5(v), GetPrime<v+5>::value
#   define LIST_PRIMES_5(v) LIST_PRIMES_4(v), GetPrime<v+4>::value
#   define LIST_PRIMES_4(v) LIST_PRIMES_3(v), GetPrime<v+3>::value
#   define LIST_PRIMES_3(v) LIST_PRIMES_2(v), GetPrime<v+2>::value
#   define LIST_PRIMES_2(v) LIST_PRIMES_1(v), GetPrime<v+1>::value
#   define LIST_PRIMES_1(v) GetPrime<v>::value
#   define LIST_PRIMES_0(v) 
#endif

int main() {
	// INIT_PRIME_ARRAY will take values between 1 and 10
	int aPrimes[] = INIT_PRIME_ARRAY(10);
	int a = GetPrime<5>::value;
	
	std::cout << a << std::endl;
	
	for (int i = 0; i < sizeof(aPrimes)/sizeof(int); i++) { 
		std::cout << aPrimes[i] << ", "; 
	}
	std::cout << std::endl;
	return 0;
}

Was This Post Helpful? 0
  • +
  • -

#5 NickDMax  Icon User is offline

  • Can grep dead trees!
  • member icon

Reputation: 2250
  • View blog
  • Posts: 9,245
  • Joined: 18-February 07

Re: Meta-Programming Challenge

Posted 06 June 2009 - 12:54 PM

My solution is flawed on several levels but the worst (to me) is that the farthest I can get it to go (on Borland 5.5) is
GetPrime<29>::value

Anything past 29 generates an error. To get even to this point I had to set NEXT_PRIME_DEPTH to 10. Which means that the maximum gap between primes would be 10 -- for GetPrime<30> I would need NEXT_PRIME_DEPTH set to 14. (Though I could decrease NEXT_PRIME_DEPTH to 8 which might make it compile a little faster, but would not really help at all).

However as long as I am at 29 then the largest prime number I could check would have to be less than 109 * 109 = 11881

Have to work out a better method to check IsPrime...
Was This Post Helpful? 0
  • +
  • -

#6 BlakeJustBlake  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 26
  • View blog
  • Posts: 441
  • Joined: 15-February 09

Re: Meta-Programming Challenge

Posted 07 June 2009 - 01:09 AM

Have you ever looked into any of the sieves?
Was This Post Helpful? 0
  • +
  • -

#7 Topher84  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 113
  • View blog
  • Posts: 359
  • Joined: 04-June 07

Re: Meta-Programming Challenge

Posted 07 June 2009 - 03:25 AM

Edit: NM... didn't read the challenge before I posted.

This post has been edited by Topher84: 07 June 2009 - 03:27 AM

Was This Post Helpful? 0
  • +
  • -

#8 gabehabe  Icon User is offline

  • GabehabeSwamp
  • member icon




Reputation: 1382
  • View blog
  • Posts: 10,962
  • Joined: 06-February 08

Re: Meta-Programming Challenge

Posted 07 June 2009 - 06:55 AM

I'm not sure I've totally grasped what you're trying, but I was in the mood for a little mathematical challenge of my own. Using a bitset, this program will use a sieve of Eratosthenes to pack that bitset fast. Then, you can run get_nth_prime(1000, primes); to find the nth prime.

Execution time of this entire program is (approx) 0.1 seconds. (Of which, the speed of get_nth_prime is extremely minimal)

To save confusion, a quick explanation:
Setting the value of MAX will calculate all prime numbers up to MAX, not the first MAX numbers.

It seems to work up to #define MAX 1000000 but I haven't tested it for such large numbers yet, particularly massive prime numbers.

Takes just ~0.1 seconds to find the 7500th prime (confirmed to be correct) when MAX is set to 100000.

/*
 * A fast method of producing a table of primes
 * using a bitset
 * Author: Danny Battison
 */

 #include <iostream>
#include <bitset>
#include <cmath>

using namespace std;

#define MAX 100000

void output(bitset<MAX> primes) {
    for(int i = 0; i < MAX; i++) {
        if(primes[i] == 1) {
            cout << i << " ";
        }
    }
}

int get_nth_prime(int n, bitset<MAX> primes) {
    int count = 0;
    for(int i = 2; i < MAX; i++) {
        if(primes[i]) {
            count++;
        } if(count == n) {
            return i;
        }
    }
    return 0; // could not find
}

int main() {
    bitset <MAX> primes;
    for(int i = 1; i < MAX; i++) {
        primes[i] = 1;
    }
    // quick sieve of eratosthenes -- start it off
    int sieve[] = {2,3,5,7}; // give it a few primes to start with
    for(int mul = 0; mul < 4; mul++) {
        for(int i = 1; i < MAX; i++) {
            if(i % sieve[mul] == 0 && i != sieve[mul]) {
                primes[i] = 0;
            }
        }
    }

    // by now, we have a list of primes with some larger numbers still left
    // in order to remove those, we now need to run through primes and
    // make sure to remove multiples of primes up to sqrt(MAX)
    for(int i = 2; i < sqrt(MAX); i++) {
        if(primes[i]) {
            for(int j = i+1; j < MAX; j++) {
                if(j % i == 0) {
                    primes[j] = 0;
                }
            }
        }
    }

    cout << get_nth_prime(1000, primes);

    return 0;
}

This post has been edited by gabehabe: 07 June 2009 - 07:06 AM

Was This Post Helpful? 0
  • +
  • -

#9 NickDMax  Icon User is offline

  • Can grep dead trees!
  • member icon

Reputation: 2250
  • View blog
  • Posts: 9,245
  • Joined: 18-February 07

Re: Meta-Programming Challenge

Posted 07 June 2009 - 08:11 AM

Quote

Have you ever looked into any of the sieves?

I did but I didn't really see how they would be much help in meta-programming. The sieves generally requires a storage mechanism (like an array) and this is not really available during meta-programming.

But the sieve of Eratosthenes was my first choice. I could not think of a way to approach it -- I was thinking about a structure like:

Primes::value2 = 2
Primes::value3 = 3
Primes::value4 = 0
Primes::value5 = 5
Primes::value6 = 0

Where the enumeration was built by the preprocessor -- but I could not really figure it out.


Quote

I'm not sure I've totally grasped what you're trying
-- The idea is to fill an array of prime number at compile time via meta-programming. This is different from writing a program that runs and finds primes (as yours does) because your program builds the array at run-time. My program above initializes the array to prime numbers at compile time -- so when it comes to run time the array already has the prime numbers in it.
Was This Post Helpful? 0
  • +
  • -

#10 gabehabe  Icon User is offline

  • GabehabeSwamp
  • member icon




Reputation: 1382
  • View blog
  • Posts: 10,962
  • Joined: 06-February 08

Re: Meta-Programming Challenge

Posted 07 June 2009 - 09:02 AM

Ah, I get it. Interesting! I'll see what I can figure out next time I get a chance, that's a really interesting idea. :^:
Was This Post Helpful? 0
  • +
  • -

#11 NickDMax  Icon User is offline

  • Can grep dead trees!
  • member icon

Reputation: 2250
  • View blog
  • Posts: 9,245
  • Joined: 18-February 07

Re: Meta-Programming Challenge

Posted 07 June 2009 - 03:29 PM

I made a little progress today, I got rid of the functions from the tutorial which gave me ever so slightly farther reach (1 more number). I fixed the NextPrime<n, Range> template so that it checks all the way up to the Range rather than Range -1.

The preprocessor bit is still messed up but at least it covers the current range of (1 to 29) that the program can produce. However it does not work when you enter INIT_PRIME_ARRAY10(1,0) or INIT_PRIME_ARRAY10(2,0) as the 0 in the ones place is not functioning.

I *think* that on other compilers you should be able to get farther but the Preprocessor part of the program still needs work.

#include <iostream>
/**
 * This is my first complete attempt at generating an array of prime numbers
 *   at compile time.
 *
 * Program by NickDMax @ DreamInCode
 */


//This will loop up from n to Number and check if Number is relativly prime with
//  all numbers between n and Number.
template <int n, int Number>
struct CheckPrime {
	enum { value = (((Number % n) == 0) ? 0 : CheckPrime<n+1, Number>::value) };
};

//Teminating position, if we get here then Number should be prime (so long as n started at 2)
template <int Number>
struct CheckPrime<Number, Number> {
	enum { value = 1 };
};

//If the current number is not a prime, it finds the next prime number within the
// specified range [n, Range]
template <int n, int Range>
struct NextPrime {
	enum { value =  (CheckPrime<2, n>::value ? n : NextPrime<n+1, Range>::value) };
};


//Terminating condition 
template <int Range>
struct NextPrime<Range, Range>
{
	enum { value = (CheckPrime<2, Range>::value ? Range : 0) };
};

//macro to set the default Depth 
#define NEXT_PRIME_DEPTH 8

template <int n>
struct FindNextPrime {
	enum { value = (NextPrime<n+1, n + NEXT_PRIME_DEPTH>::value) };
};
#undef NEXT_PRIME_DEPTH

template <int n>
struct GetPrime {
	enum { value = (FindNextPrime< GetPrime<n-1>::value >::value) };
};

template <>
struct GetPrime<1> {
	enum { value = (FindNextPrime< 1 >::value) };
};


#ifndef INIT_ARRAYS_MACRO
#   define INIT_ARRAYS_MACRO
#   define INIT_PRIME_ARRAY10(tens, ones) { LIST_PRIMES( ones , 1), LIST_PRIMES10( tens , 10) }
#   define LIST_PRIMES10(tens, v) LIST_PRIMES10_ ## tens (v)
#   define LIST_PRIMES10_2(v) LIST_PRIMES10_1(v), LIST_PRIMES_10(v+10)
#   define LIST_PRIMES10_1(v) LIST_PRIMES_10(v)
#   define LIST_PRIMES10_0(v)

#   define INIT_PRIME_ARRAY(size) { LIST_PRIMES( size , 1) }
#   define LIST_PRIMES(ones, value) LIST_PRIMES_ ## ones (value)
#   define LIST_PRIMES_10(v) LIST_PRIMES_9(v), GetPrime<v+9>::value
#   define LIST_PRIMES_9(v) LIST_PRIMES_8(v), GetPrime<v+8>::value
#   define LIST_PRIMES_8(v) LIST_PRIMES_7(v), GetPrime<v+7>::value
#   define LIST_PRIMES_7(v) LIST_PRIMES_6(v), GetPrime<v+6>::value
#   define LIST_PRIMES_6(v) LIST_PRIMES_5(v), GetPrime<v+5>::value
#   define LIST_PRIMES_5(v) LIST_PRIMES_4(v), GetPrime<v+4>::value
#   define LIST_PRIMES_4(v) LIST_PRIMES_3(v), GetPrime<v+3>::value
#   define LIST_PRIMES_3(v) LIST_PRIMES_2(v), GetPrime<v+2>::value
#   define LIST_PRIMES_2(v) LIST_PRIMES_1(v), GetPrime<v+1>::value
#   define LIST_PRIMES_1(v) GetPrime<v>::value
#   define LIST_PRIMES_0(v)
#endif

int main() {
	// INIT_PRIME_ARRAY will take values between 1 and 10
	int aPrimes[] = INIT_PRIME_ARRAY10(2, 9);
	
	//Used for troubleshooting -- this should be what the macro produces
	int bPrimes[] = {
		GetPrime<1>::value,
		GetPrime<2>::value,
		GetPrime<3>::value,
		GetPrime<4>::value,
		GetPrime<5>::value,
		GetPrime<6>::value,
		GetPrime<7>::value,
		GetPrime<8>::value,
		GetPrime<9>::value,
		GetPrime<10>::value,
		GetPrime<11>::value,
		GetPrime<12>::value,
		GetPrime<13>::value,
		GetPrime<14>::value,
		GetPrime<15>::value,
		GetPrime<16>::value,
		GetPrime<17>::value,
		GetPrime<18>::value,
		GetPrime<19>::value,
		GetPrime<20>::value,
		GetPrime<21>::value,
		GetPrime<22>::value,
		GetPrime<23>::value,
		GetPrime<24>::value,
		GetPrime<25>::value,
		GetPrime<26>::value,
		GetPrime<27>::value,
		GetPrime<28>::value,
		GetPrime<29>::value,
		GetPrime<30>::value,
		//GetPrime<31>::value,
		//GetPrime<32>::value,
		//GetPrime<33>::value,
	};
	
   
	for (int i = 0; i < sizeof(aPrimes)/sizeof(int); i++) { 
		std::cout << aPrimes[i] << ((i%5)==4 ? "\n" : ",  \t"); 
	}
	std::cout << std::endl;
	for (int i = 0; i < sizeof(bPrimes)/sizeof(int); i++) { 
		std::cout << bPrimes[i] << ((i%5)==4 ? "\n" : ",  \t"); 
	}
	std::cout << std::endl;
	return 0;
}

Was This Post Helpful? 0
  • +
  • -

#12 NickDMax  Icon User is offline

  • Can grep dead trees!
  • member icon

Reputation: 2250
  • View blog
  • Posts: 9,245
  • Joined: 18-February 07

Re: Meta-Programming Challenge

Posted 07 June 2009 - 07:52 PM

So I was able to reduce the number of iterations by only checking for odd primes -- this has let me get all way way up to GetPrime<49>::value before I hit the maximum number of iterations. Again on other compilers it gets father I just have not really run any tests to see how far.

Note that I ditched the Preprocessor part for now as I am going to redo that perhaps with a little different technique. I could not figure out how to make it generally count up though the numbers 10, 20, 30 etc.

#include <iostream>
/**
 * This is my third complete attempt at generating an array of prime numbers
 *   at compile time.
 *
 * Program by NickDMax @ DreamInCode
 */


//This will loop up from n to Number and check if Number is relativly prime with
//  all numbers between n and Number.
template <int n, int Number>
struct CheckPrime {
	enum { value = (((Number % n) == 0) ? 0 : CheckPrime<n+2, Number>::value) };
};

//Teminating position, if we get here then Number should be prime (so long as n started at 2)
template <int Number>
struct CheckPrime<Number, Number> {
	enum { value = 1 };
};

//If the current number is not a prime, it finds the next prime number within the
// specified range [n, Range]
template <int n, int Range>
struct NextPrime {
	enum { value =  (CheckPrime<3, n>::value ? n : NextPrime<n+2, Range>::value) };
};

//Terminating condition 
template <int Range>
struct NextPrime<Range, Range>
{
	enum { value = (CheckPrime<3, Range>::value ? Range : 0) };
};

//macro to set the default Depth 
#define NEXT_PRIME_DEPTH 14
template <int n>
struct FindNextPrime {
	enum { value = (NextPrime<n+2, n + NEXT_PRIME_DEPTH>::value) };
};
#undef NEXT_PRIME_DEPTH

template <int n>
struct GetPrime {
	enum { value = (FindNextPrime< GetPrime<n-1>::value >::value) };
};

//Since this is the only even prime we will not check for any even primes.
template <>
struct GetPrime<1> {
	enum { value = 2 };
};

//Needed to get to the first odd prime so that we never have to check an
// even number
template <>
struct GetPrime<2> {
	enum { value = 3 };
};


int main() {
	
	//Used for troubleshooting -- this should be what the macro produces
	int bPrimes[] = {
		GetPrime<1>::value,
		GetPrime<2>::value,
		GetPrime<3>::value,
		GetPrime<4>::value,
		GetPrime<5>::value,
		GetPrime<6>::value,
		GetPrime<7>::value,
		GetPrime<8>::value,
		GetPrime<9>::value,
		GetPrime<10>::value,
		GetPrime<11>::value,
		GetPrime<12>::value,
		GetPrime<13>::value,
		GetPrime<14>::value,
		GetPrime<15>::value,
		GetPrime<16>::value,
		GetPrime<17>::value,
		GetPrime<18>::value,
		GetPrime<19>::value,
		GetPrime<20>::value,
		GetPrime<21>::value,
		GetPrime<22>::value,
		GetPrime<23>::value,
		GetPrime<24>::value,
		GetPrime<25>::value,
		GetPrime<26>::value,
		GetPrime<27>::value,
		GetPrime<28>::value,
		GetPrime<29>::value,
		GetPrime<30>::value,
		GetPrime<31>::value,
		GetPrime<32>::value,
		GetPrime<33>::value,
		GetPrime<34>::value,
		GetPrime<35>::value,
		GetPrime<36>::value,
		GetPrime<37>::value,
		GetPrime<38>::value,
		GetPrime<39>::value,
		GetPrime<40>::value,
		GetPrime<41>::value,
		GetPrime<42>::value,
		GetPrime<43>::value,
		GetPrime<44>::value,
		GetPrime<45>::value,
		GetPrime<46>::value,
		GetPrime<47>::value,
		GetPrime<48>::value,
		GetPrime<49>::value,
//		GetPrime<50>::value,
//		GetPrime<51>::value,
	};
	   
	for (int i = 0; i < sizeof(bPrimes)/sizeof(int); i++) { 
		std::cout << bPrimes[i] << ((i%5)==4 ? "\n" : ",  \t"); 
	}
	std::cout << std::endl;
	return 0;
}

Was This Post Helpful? 0
  • +
  • -

#13 NickDMax  Icon User is offline

  • Can grep dead trees!
  • member icon

Reputation: 2250
  • View blog
  • Posts: 9,245
  • Joined: 18-February 07

Re: Meta-Programming Challenge

Posted 07 June 2009 - 09:17 PM

As I was playing around in the preprocessor I came up with with odd little construction. The INIT_PRIME_SUM# macro can build up arrays by taking the sum of 2, 3, or 4 powers of 2.

For example INIT_PRIME_SUM2(2,4); would result in an array containing the first 6 primary numbers while INIT_PRIME_SUM3(1,2,16); would give the first 19, as would any permutation of 1, 2, 16 in the arguments.

#include <iostream>
/**
 * This is my first complete attempt at generating an array of prime numbers
 *   at compile time.
 *
 * Program by NickDMax @ DreamInCode
 */


//This will loop up from n to Number and check if Number is relativly prime with
//  all numbers between n and Number.
template <int n, int Number>
struct CheckPrime {
	enum { value = (((Number % n) == 0) ? 0 : CheckPrime<n+2, Number>::value) };
};

//Teminating position, if we get here then Number should be prime (so long as n started at 2)
template <int Number>
struct CheckPrime<Number, Number> {
	enum { value = 1 };
};

//If the current number is not a prime, it finds the next prime number within the
// specified range [n, Range]
template <int n, int Range>
struct NextPrime {
	enum { value =  (CheckPrime<3, n>::value ? n : NextPrime<n+2, Range>::value) };
};

//Terminating condition 
template <int Range>
struct NextPrime<Range, Range>
{
	enum { value = (CheckPrime<3, Range>::value ? Range : 0) };
};

//macro to set the default Depth 
#define NEXT_PRIME_DEPTH 14
template <int n>
struct FindNextPrime {
	enum { value = (NextPrime<n+2, n + NEXT_PRIME_DEPTH>::value) };
};
#undef NEXT_PRIME_DEPTH

template <int n>
struct GetPrime {
	enum { value = (FindNextPrime< GetPrime<n-1>::value >::value) };
};

//Since this is the only even prime we will not check for any even primes.
template <>
struct GetPrime<1> {
	enum { value = 2 };
};

//Needed to get to the first odd prime so that we never have to check an
// even number
template <>
struct GetPrime<2> {
	enum { value = 3 };
};



#define MAC(n) GetPrime<n>::value,
#define DO_0(m, n) 
#define DO_1(m, n) m(n)
#define DO_2(m, n) DO_1(m, n) DO_1(m, (n+1))
#define DO_4(m, n) DO_2(m, n) DO_2(m, (n+2))
#define DO_8(m, n) DO_4(m, n) DO_4(m, (n+4)) 
#define DO_16(m, n) DO_8(m, n) DO_8(m, (n+8)) 
#define DO_32(m, n) DO_16(m, n) DO_16(m, (n+16))
#define DO_64(m, n) DO_32(m, n) DO_32(m, (n+32))
#define DO_128(m, n) DO_64(m, n) DO_64(m, (n+64))

#define INIT_PRIME_SUM1(a) { DO_ ## a (MAC, 1) }
#define INIT_PRIME_SUM2(a, b) { DO_ ## a (MAC, 1)  DO_ ## b(MAC, (1+ ## a ))  }
#define INIT_PRIME_SUM3(a, b, c) { DO_ ## a (MAC, 1)  DO_ ## b(MAC, (1+ ## a )) DO_ ## c(MAC, (1+ ## a + ## b)) }
#define INIT_PRIME_SUM4(a, b, c, d) { DO_ ## a (MAC, 1)  DO_ ## b(MAC, (1+ ## a )) DO_ ## c(MAC, (1+ ## a + ## b)) DO_ ## d(MAC, (1+ ## a + ## b + ## c)) }


int main() {
	
	int aPrimes[] = INIT_PRIME_SUM4(4, 16, 8, 2); 
	//Used for troubleshooting -- this should be what the macro produces
	int bPrimes[] = {
		GetPrime<1>::value,
		GetPrime<2>::value,
		GetPrime<3>::value,
		GetPrime<4>::value,
		GetPrime<5>::value,
		GetPrime<6>::value,
		GetPrime<7>::value,
		GetPrime<8>::value,
		GetPrime<9>::value,
		GetPrime<10>::value,
		GetPrime<11>::value,
		GetPrime<12>::value,
		GetPrime<13>::value,
		GetPrime<14>::value,
		GetPrime<15>::value,
		GetPrime<16>::value,
		GetPrime<17>::value,
		GetPrime<18>::value,
		GetPrime<19>::value,
		GetPrime<20>::value,
		GetPrime<21>::value,
		GetPrime<22>::value,
		GetPrime<23>::value,
		GetPrime<24>::value,
		GetPrime<25>::value,
		GetPrime<26>::value,
		GetPrime<27>::value,
		GetPrime<28>::value,
		GetPrime<29>::value,
		GetPrime<30>::value,
		GetPrime<31>::value,
		GetPrime<32>::value,
		GetPrime<33>::value,
		GetPrime<34>::value,
		GetPrime<35>::value,
		GetPrime<36>::value,
		GetPrime<37>::value,
		GetPrime<38>::value,
		GetPrime<39>::value,
		GetPrime<40>::value,
		GetPrime<41>::value,
		GetPrime<42>::value,
		GetPrime<43>::value,
		GetPrime<44>::value,
		GetPrime<45>::value,
		GetPrime<46>::value,
		GetPrime<47>::value,
		GetPrime<48>::value,
		GetPrime<49>::value,
//		GetPrime<50>::value,
//		GetPrime<51>::value,
	};

	for (int i = 0; i < sizeof(aPrimes)/sizeof(int); i++) { 
		std::cout << aPrimes[i] << ((i%5)==4 ? "\n" : ",  \t"); 
	}
	std::cout << std::endl; 

	  
	for (int i = 0; i < sizeof(bPrimes)/sizeof(int); i++) { 
		std::cout << bPrimes[i] << ((i%5)==4 ? "\n" : ",  \t"); 
	}
	std::cout << std::endl;
	return 0;
}


Still not quite there but that is a neat trick all the same... I like it. I left it general enough so that if you wanted to customize it to initialize some other sort of array all you have to do is create a custom macro MAC -- so it kind of works like an X-Macro program...


*Fixed a bug for the DO_16 and above...
Was This Post Helpful? 0
  • +
  • -

#14 NickDMax  Icon User is offline

  • Can grep dead trees!
  • member icon

Reputation: 2250
  • View blog
  • Posts: 9,245
  • Joined: 18-February 07

Re: Meta-Programming Challenge

Posted 07 June 2009 - 10:05 PM

TO sort of flesh out the above attempt I am settling on the following preprocessor macros:
#define DO_0(m, n) 
#define DO_1(m, n) m(n)
#define DO_2(m, n) DO_1(m, n) DO_1(m, (n+1))
#define DO_4(m, n) DO_2(m, n) DO_2(m, (n+2))
#define DO_8(m, n) DO_4(m, n) DO_4(m, (n+4)) 
#define DO_16(m, n) DO_8(m, n) DO_8(m, (n+8)) 
#define DO_32(m, n) DO_16(m, n) DO_16(m, (n+16))
#define DO_64(m, n) DO_32(m, n) DO_32(m, (n+32))
#define DO_128(m, n) DO_64(m, n) DO_64(m, (n+64))


#define LIST_TO_SUM1(a)	   LIST_TO_SUM4(a, 0, 0, 0)
#define LIST_TO_SUM2(a, b)	LIST_TO_SUM4(a, b, 0, 0)
#define LIST_TO_SUM3(a, b, c) LIST_TO_SUM4(a, b, c, 0)
#define LIST_TO_SUM4(a, b, c, d)		  \
	DO_ ## a(X, 1)					  \
	DO_ ## b(X, (1 + a ))			   \
	DO_ ## c(X, (1 + a + b))				   \
	DO_ ## d(X, (1 + a + b + c))  
	
#define LIST_TO_SUM(num, ...) LIST_TO_SUM ## num ( __VA_ARGS__ )
#define INIT_ARRAY_WITH_MACRO(mac) { mac }


So to initialize an array with primes one can do the following:
	#define X(n) GetPrime<n>::value,
	int aPrimes[] = INIT_ARRAY_WITH_MACRO( LIST_TO_SUM(3, 32, 16, 1) ); 
	#undef X


But if one wanted to initialize the array with the numbers from 1 to 49, you can do this:
	#define X(n)  n,
	int aNums[] = INIT_ARRAY_WITH_MACRO( LIST_TO_SUM(3, 32, 16, 1) ); 
	#undef X
Or if one wanted to list the first 128 square values:
	#define X(n)  (n) * (n),
	int aSqrs[] = INIT_ARRAY_WITH_MACRO( LIST_TO_SUM(1, 128) ); 
	#undef X


So it is now generally useful rather than a specific case... I have to admit that it is a strange way of doing things, but I think it is kind of neat.
Was This Post Helpful? 0
  • +
  • -

#15 NickDMax  Icon User is offline

  • Can grep dead trees!
  • member icon

Reputation: 2250
  • View blog
  • Posts: 9,245
  • Joined: 18-February 07

Re: Meta-Programming Challenge

Posted 08 June 2009 - 11:05 AM

At lunch I did some tests on some other compilers.

MinGW HATES the preprocessor bit. It does it,but will only do it for small numbers. It will not even generate the 49.

However MinGW will find Primes above the 49 with GetPrime -- but the compile time goes WAY up -- but it does it.

I also did some test with VC++ (the cl 64bit version) and it will use the macro as well as generate primes above 49. With the configuration above I was able to generate 99 primes, but the compile time was about 2min 23sec which actually seems like forever. To get past 99 primes you need to set the NEXT_PRIME_DEPTH higher which will drastically increase the compile time.

OH, VC++ does not like the LIST_TO_SUM macro and I have to use the LIST_TO_SUM3 macro directly.
Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2