Member Avatar for vijayan121

Question posed by josolanes:

I looked at your thread here: http://www.daniweb.com/forums/thread88255.html from a couple years back

And I'm starting to get a grasp of your first post. I understood how to do the factorial struct really quickly, but the _if and _for statements still make me feel uneasy, though I think I understand them. I think a bit more experience with it will help a lot with my confidence

One that I'd like help withis the following example of isPrime:

bool isPrime(int p, int i=2) 
{
    if (i==p)
        return 1; 
    if (p%i == 0)
        return 0;
    return isPrime (p, i+1);
}

I'd like to achieve this in a similar manner as the fibonacci one, with a single set of funcitons and templates (for each "case") if possible.

I've been thinking about it a bit, but my lack of experience with TMP seems to have me somewhat dumbfounded. I assume it's possible to do this in a single struct set, but can't quite figure it out since it has 2 variables, one as an input and the other changing.

I looked online for an isPrime TMP example and found one that uses a combination of about 3 struct sets to perform the above operation http://zwabel.wordpress.com/2008/12/18/c-template-support-in-kdevelop4-another-milestone/

I tried to modify it to work within a single struct set using conditional shorthand but can't quite figure it out

Is there a way to do the above in a single struct set? If so, how would you?

THe is_prime itself can be done with a single struct and a specialization for it:

template< int NUMBER, int DIVISOR = NUMBER - 1 > struct is_prime
{
    // compile-time assertion that NUMBER >= 2
    struct check { char check_it[ NUMBER - 1 ] ; } ;

    enum
    {
        // NUMBER is a prime number if
        result = (NUMBER % DIVISOR) && // it is not divisible by (NUMBER-1)
                // and not divisible by any number smaller than it
                 is_prime< NUMBER, DIVISOR-1 >::result
    } ;
};

template< int NUMBER > struct is_prime< NUMBER, 1 > // except 1
{
    enum { result = true } ;
};

Just to give you another example of a compile-time if and a compile-time for loop, I've added these:

// compile-time if- general case (ISPRIME is not true): print nothing
template< int NUMBER, bool ISPRIME > struct print_if_prime
{
    static inline void print() {}
};

// specialization: print the number if ISPRIME is true (it is a prime number)
template< int NUMBER > struct print_if_prime< NUMBER, true >
{
    static inline void print() { std::cout << NUMBER << '\n' ; }
};

// compile-time loop
// print all prime numbers in the range N to MAX inclusive
template< int N, int MAX > struct print_primes
{
    static inline void print()
    {
        // if N is a prime number, print it
        print_if_prime< N, is_prime<N>::result >::print() ;

        // print all prime numbers in the range N+1 to MAX inclusive
        print_primes< N+1, MAX >::print() ;
    }
};

// exit the loop with this specialization (we have already reached MAX)
template< int N > struct print_primes<N,N>
{
    static inline void print()
    {
        // if N is a prime number, print it
        print_if_prime< N, is_prime<N>::result >::print() ;
    }
};

And finally a main, to print all prime numbers upto 100

int main()
{
    print_primes<2,100>::print() ;
}

The code that you saw on the web is based on the metaprogram by Erwin Unruh, which issues error messages that would contain successive prime numbers. The original program by Unruh is given in the afternotes to this article: http://www.informit.com/articles/article.aspx?p=30667
You may find it worth your while to read the complete article from beginning to end.

  • 2 Contributors
  • 1 Reply
  • 181 Views
  • 9 Hours Discussion Span
  • Latest Post Latest Post by josolanes

Dani AI

Generated

’s template-recursion solution is a classic TMP demonstration: it cleanly encodes a compile-time is_prime and even uses a compile-time check for NUMBER >= 2. That implementation, however, tests every divisor down to 1; trial division only needs to try divisors up to sqrt(n), so truncating the check there drastically reduces recursion and compile effort. Also keep in mind TMP recursion/instantiation can hit compiler limits (and long compile times); compilers expose options to adjust template depth. (en.wikipedia.org)

With modern C++ it’s usually clearer and cheaper to write a constexpr function rather than deep template recursion: C++14 relaxed constexpr rules so loops and local variables are allowed, making an iterative compile-time is_prime simple to express. Use static_assert to force a compile-time check, or consteval (C++20) when every call must be evaluated at compile time. Example (C++14+):

constexpr bool is_prime_ct(unsigned n) {
    if (n < 2) return false;
    for (unsigned d = 2; d * d <= n; ++d)
        if (n % d == 0) return false;
    return true;
}

static_assert(is_prime_ct(37), "37 should be prime");

See constexpr, static_assert and consteval for details. (cppreference.com)

Notes and pitfalls: avoid d*d overflow for very large n (use d <= n/d or a wider type), and beware that heavy compile-time computation increases build time. TMP is still appropriate when results must be available as types, but for numeric compile-time work prefer constexpr (or a carefully bounded constexpr sieve) for readability and much better compiler behaviour. As observed, experimenting with both styles is the best way to internalize the differences.

Member Avatar for josolanes

Thanks vijayan121! I'm going to have to play with this a bit more today to really understand how to use it myself

I understand your example, now. But I had trouble trying to come up with it on my own

Thanks again! You've really helped me in understanding this a lot!

EDIT: reading the article now :)

Edited by josolanes because: n/a
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.