Template meta programming prime decision

Recommended for you: Get network issues from WhatsUp Gold. Not end users.

Template meta programming (English: Template metaprogramming; abbreviation: TMP) is a kind of meta programming techniques, is no exaggeration to say, this technology has opened a new way of programming in C++. The compiler uses the template to generate a temporary source, then and the rest of the source mixed and compiled. The output of these templates include compile time constants, data structure and a complete function. So the template can be thought of as a compile time operation. This paper describes the use of template metaprogramming technique at compile time to determine whether an integer is prime algorithms. Input is an integer greater than 0, the output of 1 indicates that the integer is prime, 0 is expressed as the number of. The main purpose of this paper is to introduce the general design and the programming method of template meta programming arithmetic and logical operations with examples. The concept of template meta programming and the basic introduction to see Wikipedia:

We use the most basic number judgment algorithm, pseudo code as follows:

function IsPrime(n)
if n == 1 then return false
if n == 2 then return true
for each m from 2
    if m * m > n then return true
    if n mod m = 0 then return false
    m := m + 1

This is obviously a complexity of O (sqrt (n)) algorithm, the main logic loop. Template meta programming is the logical form of recursive algorithm to achieve the cycle, so we must to know two things: there are several variables involved, and the termination condition is what cycle. This algorithm apparently there are 2 variables involved in operation: one is n, another is m. We have the m from the beginning of 2 degrees, until it reaches the terminating condition of the loop. In the template meta programming, the template argument deduction priority is arranged to specialization degree, therefore the termination condition and special value processing using partial specialization (also called the partial specialization) implementation. A template argument deduction and partial specialization concepts and syntax here not to repeat them, see C++ books or search webpage data. Then based on the above analysis, we can first write the following a framework:

template<uint n, uint m>struct TEST{
	const static uint r = TEST<n, nextM>::r; //NextM is a M, not the implementation of. Instead of the cycle with recursive structure here.
};
template<uint n>struct ISPRIME{
	const static uint r = TEST<n, 2>::r; //From the beginning of 2, in order to judge each possible value of M code, not realizing judgment. 
};
template<>struct ISPRIME<1>{ //The algorithm can not calculate the special value of 1, judge for the 0
	const static uint r = 0;
};
template<>struct ISPRIME<2>{ //The algorithm can not calculate the special value of 2, judge for the 1
	const static uint r = 1;
};

The termination condition cycle is: m square more than n or can be divisible by n. When the termination condition is satisfied, send a special value to the template parameters, and the values in the partial specialization, then the recursion will terminate. But to judge whether the termination condition, need to carry on logic and arithmetic operations. Based on the above analysis, the framework code rewritten as follows:

template<uint n, uint m>struct TEST{
       // if (n % m == 0) n = 0;
       // if (m * m > n) m = 0; else ++m;
	const static uint r = TEST<n, m>::r; //The above is not two lines of code written in here, only that logic. The actual syntax below another introduction
};
template<uint m>struct TEST<0, m>{ //A n of 0
	const static uint r = 0; //In the non specialized template code, n can be divided by m, so n is set to 0, it is a composite number
};
template<uint n>struct TEST<n, 0>{ //A m of 0
	const static uint r = 1; //In the non specialized template code, m * m > N, so n cannot be any smaller number divisible, so is a prime number
};
template<uint n>struct ISPRIME{
	const static uint r = TEST<n, 2>::r; //From the beginning of 2, in order to judge each possible value of M code, not realizing judgment. 
};
template<>struct ISPRIME<1>{ //The algorithm can not calculate the special value of 1, judge for the 0
	const static uint r = 0;
};
template<>struct ISPRIME<2>{ //The algorithm can not calculate the special value of 2, judge for the 1
	const static uint r = 1;
};

 Finally, as long as the parameters are deduced template implementation of two logical judgment can be modulo arithmetic and the above framework, the integrity of the code are as follows:

#include <iostream>
typedef unsigned int uint;

template<uint n, uint m>struct NEXTN{
	const static uint r = ((n % m != 0) * n);
};

template<uint n, uint m>struct NEXTM{
	const static uint r = (m * m <= n ? (m + 1) : 0);
};

template<uint n, uint m>struct TEST{
	const static uint r = TEST<NEXTN<n, m>::r, NEXTM<n, m>::r>::r;
};

template<uint m>struct TEST<0, m>{
	const static uint r = 0;
};

template<uint n>struct TEST<n, 0>{
	const static uint r = 1;
};

template<uint n>struct ISPRIME{
	const static uint r = TEST<n, 2>::r;
};

template<>struct ISPRIME<1>{
	const static uint r = 0;
};

template<>struct ISPRIME<2>{
	const static uint r = 1;
};

int main()
{
	int primes[] = {
		ISPRIME<1>::r, ISPRIME<2>::r, ISPRIME<3>::r, ISPRIME<4>::r,
		ISPRIME<5>::r, ISPRIME<6>::r, ISPRIME<7>::r, ISPRIME<8>::r,
		ISPRIME<9>::r, ISPRIME<10>::r, ISPRIME<11>::r, ISPRIME<12>::r,
		ISPRIME<13>::r, ISPRIME<14>::r, ISPRIME<15>::r, ISPRIME<16>::r,
	};
	for (int i = 0; i <sizeof(primes) / sizeof(primes[0]); ++i)
		std::cout <<i + 1 <<(primes[i] ? " YES" : " NO") <<std::endl;
	return 0;
}

 If you have more concise wording, please advise. Thank you!

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download

Posted by Clifford at November 19, 2013 - 5:34 PM