Join 307,214 C++ Programmers for FREE! Get instant access to thousands of C++ experts, tutorials, code snippets, and more! There are 1,560 people online right now. Registration is fast and FREE... Join Now!
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?).
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:
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.
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".
CODE
#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
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...
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.
cpp
/* * A fast method of producing a table of primes * using a bitset * Author: Danny Battison */
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: 7 Jun, 2009 - 06:06 AM
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:
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.
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.
CODE
#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) }; };
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.
CODE
#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) }; };
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.
CODE
#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) }; };
#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...
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.
Ok fixed the bug that was stopping MinGW from compiling it correctly. It now works just find in MinGW although it does take quite a while to compile.
The problem was that I was using the ## operator when I didn't need to -- VC++ and Borland were apparently ok with it, though I think this was the error in the variadic macro in VC++.
While I am aware that this turned out to be more like a Blog than a challenge I have been having a lot of fun with it...
I decided to see if I could expand my preprocessor trick to take care of some of the work for the templates -- this should remove the template recursion limit that Borland (my goto compiler) has... so here it is:
CODE
#include <iostream> using namespace std;
#ifndef CHECK_PRIME_WITH_MACRO //The DO_# Macros will do a particular macro m a given number of times. // the argument n keeps track of now many times.. // note n starts at 1 (as apposed to 0 which might seem natural). # define DO_0(m, n, o) # define DO_1(m, n, o) m((n), o) # define DO_2(m, n, o) DO_1(m, n, o) DO_1(m, (n+1), o) # define DO_4(m, n, o) DO_2(m, n, o) DO_2(m, (n+2), o) # define DO_8(m, n, o) DO_4(m, n, o) DO_4(m, (n+4), o) # define DO_16(m, n, o) DO_8(m, n, o) DO_8(m, (n+8), o) # define DO_32(m, n, o) DO_16(m, n, o) DO_16(m, (n+16), o) # define DO_64(m, n, o) DO_32(m, n, o) DO_32(m, (n+32), o) # define DO_128(m, n, o) DO_64(m, n, o) DO_64(m, (n+64), o) # define DO_256(m, n, o) DO_128(m, n, o) DO_128(m, (n+128), o)
#define X(n, o) (o % (n+1) == 0) ? (n+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 = (IS_PRIME(n) ? n : NextPrime<n+2, Range>::value) }; };
//Terminating condition template <int Range> struct NextPrime<Range, Range> { enum { value = (IS_PRIME(Range) ? Range : 0) }; }; #undef X //macro to set the default Depth #define NEXT_PRIME_DEPTH 18 template <int n> struct FindNextPrime { enum { value = (NextPrime<n+2, n + NEXT_PRIME_DEPTH>::value) }; }; #undef NEXT_PRIME_DEPTH
//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 }; };
//Utility macro to display the array and its size #define DISPLAY_ARRAY(name, cols) \ std::cout << "Array: " #name "[" << (sizeof(name)/sizeof(int)) << "] =\n"; \ for (int i = 0; i < sizeof(name)/sizeof(int); i++) { \ std::cout << name[i] << ((i%cols)==(cols-1) ? "\n" : ", \t"); \ } \ std::cout << std::endl;
int main() { #define X(n, o) GetPrime<n>::value, int aPrimes[] = { LIST_TO_SUM3(0,64,32,1) }; #undef X DISPLAY_ARRAY(aPrimes, 10);
return 0; }
This can roughly get up to 97 primes... I might be able to squeeze on or two more out but I was happy with this result since I was limited to about 30 or so before.
MinGW was able to reach 154 primes with a MUCH lower compile time. I am sure that MinGW and VC++ (untested so far) can use this to generate at least a couple of hundred primes with a reasonable compile time.
What I think is awesome about this is the NextPrime templates! This is what is generated when IS_PRIME is set to check up to 64
To generate the 154 primes I had IS_PRIME set to 1024!!! Borland has an out of memory error just past 512! Programming is so much fun sometimes!
For those people who were thinking that ?: is just a replacement for if-else -- this would not work with if-else because the compiler can evaluate a constant expression but can not evaluate if-else statements at compile time. I could not replace this with an if-else block.
It almost feels as though I could get rid of the templates and just use the preprocessor. Right now I need the templates for recursion (the FindNextPrime<> is not really needed) -- but since the templates are not really allowing me to get much past a few hundred primes I think that the preprocessor could accomplish the same thing... just need to work out the loops.
Well I made progress on the road to making it purely a preprocessor program -- and I now know that I CAN make it a preprocessor only program -- BUT I discovered a problem.
Borland's compilers are just out of the running all together. They can't compile the preprocessor version even with modest expectations.
MinGW can only get up to 101 Primes in the current version (before it runs out of memory) and I fear that if I were to take the last steps to make it a pure preprocessor program then it would not get very far at all (if it could even compile).
Anyway here is the latest version that only uses the GetPrime template:
CODE
#include <iostream> using namespace std;
#ifndef CHECK_PRIME_WITH_MACRO //The DO_# Macros will do a particular macro m a given number of times. // the argument n keeps track of now many times.. // note n starts at 1 (as apposed to 0 which might seem natural). # define DO_0(m, n, o) # define DO_1(m, n, o) m((n), o) # define DO_2(m, n, o) DO_1(m, n, o) DO_1(m, (n+1), o) # define DO_4(m, n, o) DO_2(m, n, o) DO_2(m, (n+2), o) # define DO_8(m, n, o) DO_4(m, n, o) DO_4(m, (n+4), o) # define DO_16(m, n, o) DO_8(m, n, o) DO_8(m, (n+8), o) # define DO_32(m, n, o) DO_16(m, n, o) DO_16(m, (n+16), o) # define DO_64(m, n, o) DO_32(m, n, o) DO_32(m, (n+32), o) # define DO_128(m, n, o) DO_64(m, n, o) DO_64(m, (n+64), o) # define DO_256(m, n, o) DO_128(m, n, o) DO_128(m, (n+128), o)
#ifndef CHECK_PRIME_WITH_MACRO2 //The DO2_# Macros will do a particular macro m a given number of times. // the argument n keeps track of now many times.. // note n starts at 1 (as apposed to 0 which might seem natural). # define DO2_0(m, n, o) # define DO2_1(m, n, o) m((n), o) # define DO2_2(m, n, o) DO2_1(m, n, o) DO2_1(m, (n+1), o) # define DO2_4(m, n, o) DO2_2(m, n, o) DO2_2(m, (n+2), o) # define DO2_8(m, n, o) DO2_4(m, n, o) DO2_4(m, (n+4), o) # define DO2_16(m, n, o) DO2_8(m, n, o) DO2_8(m, (n+8), o) # define DO2_32(m, n, o) DO2_16(m, n, o) DO2_16(m, (n+16), o) # define DO2_64(m, n, o) DO2_32(m, n, o) DO2_32(m, (n+32), o) # define DO2_128(m, n, o) DO2_64(m, n, o) DO2_64(m, (n+64), o) # define DO2_256(m, n, o) DO2_128(m, n, o) DO2_128(m, (n+128), o)
#define X(n, o) (o%(n+1)==0)?(n+1): #define Y(n, o) IS_PRIME((o+n))?(o+n): #define NEXT_PRIME(v) (LIST_TO_SUM_2(Y,v,16,4) 0) //macro to set the default Depth template <int n> struct GetPrime { enum { value = (NEXT_PRIME(GetPrime<n-1>::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 }; }; #undef Y #undef X
//Utility macro to display the array and its size #define DISPLAY_ARRAY(name, cols) \ std::cout << #name "[" << (sizeof(name)/sizeof(int)) << "] = {\n"; \ for (int i = 0; i < sizeof(name)/sizeof(int); i++) { \ std::cout << name[i] << ((i%cols)==(cols-1) ? ",\n" : ", \t"); \ } \ std::cout << "};" <<std::endl;
int main() { #define X(n, o) GetPrime<n>::value, int aPrimes[] = { LIST_TO_SUM4(X,0,64,32,4,1) }; #undef X DISPLAY_ARRAY(aPrimes, 10); return 0; }
Takes 2min 28seconds to compile...
It is easy to see how this can be completed in Preporcessor -- but I kind of doubt it would be able to generate more than 10 primes if any at all.
Forum Index:
Programming Help |
C and C++ |
VB6 |
Java |
VB.NET |
C# |
ASP.NET |
PHP |
ColdFusion |
Perl and Python |
Ruby |
Databases |
Other Languages |
Game Programming |
Mobile Development |
Software Development |
Computer Science |
Industry News |
Programming Tutorials |
C++ Tutorials |
Visual Basic Tutorials |
Java Tutorials |
VB.NET Tutorials |
C# Tutorials |
Linux Tutorials |
PHP Tutorials |
ColdFusion Tutorials |
Windows Tutorials |
HTML/JavaScript Tutorials |
CSS Tutorials |
Flash Tutorials |
Web Promotion Tutorials |
Graphic Design & Photoshop Tutorials |
Software Development Tutorials |
Database Tutorials |
Other Language Tutorials |
ASP.NET Tutorials |
Game Programming Tutorials |
WPF & Silverlight Tutorials |
5 Jun, 2009 - 02:46 PM
| 
