1
\$\begingroup\$

I previously posted a thread asking for a general review of one of my first projects related to programming (C++ Prime Number Library) and received very good help and new perspectives. After this, I decided to incorporate my newly acquired knowledge of templates into the same project. I want to know if this implementation follows good standards or if I am making big mistakes regarding the template implementation or the source code in general.

inpalprime.hpp:

#ifndef inpalprime_hpp
#define inpalprime_hpp

#include <vector>
#include <string>


namespace inpal
{
    template <class T> class prime
    {
    public:
     static T max_prime(T n);
     static T count_primes(T n);
     static double prime_density(double h);
     static bool prime_test(T p);
     static bool twin_test(T p);
     static bool cousin_test(T p);
     static bool sexy_test(T p);
     static T max_palprime(T n);
     static T max_factor(T f);
     static T count_factors(T f);
    private:
     static std::vector<bool> prime_sieve(T m);
     static std::vector<T> factorizer(T f);
     static bool pal_test(T n);
    };
}


#endif /* inpalprime_hpp */

inpalprime.cpp:

#include "inpalprime.hpp"
#include <cmath>
#include <vector>
#include <string>
#include <algorithm>


template <class T> T  inpal::prime<T>::max_prime(T n)
{
    auto primes = prime_sieve(n);
    auto it = std::find(primes.rbegin(), primes.rend(), true);

    return primes.size()-std::distance(primes.rbegin(), it)-1;
}


template <class T> T inpal::prime<T>::count_primes(T n)
{
    auto primes = prime_sieve(n);

    return std::count(primes.begin(), primes.end(), true);
}


template <class T> double inpal::prime<T>::prime_density(double h)
{
    return count_primes(h)/h;
}


template <class T> bool inpal::prime<T>::prime_test(T p)
{
    return p == max_prime(p);
}


template <class T> bool inpal::prime<T>::twin_test(T p)
{
    auto primes = prime_sieve(p+2);

    return p!=2 && primes[primes.size()-3] && (primes[primes.size()-1] || primes[primes.size()-5]);
}


template <class T> bool inpal::prime<T>::cousin_test(T p)
{
    auto primes = prime_sieve(p+4);

    return  p!=2 && primes[primes.size()-5] && (primes[primes.size()-1] || primes[primes.size()-9]);
}


template <class T> bool inpal::prime<T>::sexy_test(T p)
{
    auto primes = prime_sieve(p+6);

    return (p!=2 && p!=3) && primes[primes.size()-7] && (primes[primes.size()-1] || primes[primes.size()-13]);
}


template <class T> T inpal::prime<T>::max_palprime(T n)
{
    auto primes = prime_sieve(n);

    for(std::size_t i=n; i>=2; --i) if(primes[i] && pal_test(i)) return i;

    return 2;
}


template <class T> T inpal::prime<T>::max_factor(T f)
{
    return factorizer(f).back();
}


template <class T> T inpal::prime<T>::count_factors(T f)
{
    return factorizer(f).size();
}


template <class T> std::vector<bool> inpal::prime<T>::prime_sieve(T m)
{
    std::vector<bool> p_test(m+1, false);

    //defines square root of m
    T root = ceil(sqrt(m));

    //sieve axioms
    for(T x=1; x<=root; x++)
    {
        for(T y=1; y<=root; y++)
        {
            T i= (4*x*x)+(y*y);
            if (i<=m && (i%12==1 || i%12==5))
            {
                p_test[i].flip();
            }

            i=(3*x*x)+(y*y);
            if(i<=m && i%12==7)
            {
                p_test[i].flip();
            }

            i=(3*x*x)-(y*y);
            if(x>y && i<=m && i%12==11)
            {
                p_test[i].flip();
            }
        }
    }

    //marks 2,3,5 and 7 as prime numbers
    p_test[2]=p_test[3]=p_test[5]=p_test[7]=true;

    //marks all multiples of primes as non primes
    for(T r=5; r<=root; r++)
    {
        if(p_test[r])
        {
            for(T j=r*r; j<=m; j+=r*r)
            {
                p_test[j]=false;
            }
        }
    }

    return p_test;
}


template <class T> std::vector<T> inpal::prime<T>::factorizer(T f)
{
    std::vector<T> p_fac;
    T p = 2;

    //trial division
    while(p<=f)
    {
        while(f%p==0)
        {
            p_fac.push_back(p);
            f=f/p;
        }
        p += p==2 ? 1 : 2;
    }

    return p_fac;
}


template <class T> bool inpal::prime<T>::pal_test(T n)
{
    //converts n to a string
    std::string rev = std::to_string(n);

    //checks if the reverse of rev is equal to rev
    if(std::equal(rev.begin(), rev.begin()+rev.size()/2, rev.rbegin()))
    {
        return true;
    }

    return false;
}


template class inpal::prime<unsigned long>;
template class inpal::prime<unsigned long long>;
template class inpal::prime<long>;
template class inpal::prime<long long>;
\$\endgroup\$

1 Answer 1

5
\$\begingroup\$

Not really an answer but I just joined this site and I don't have enough rep to post a comment.

The first thing that bothers me is that you are using a class that only has static functions. You might as well put everything as a free floating function in your namespace.

Another thing is the usage of unconstrained templates. Your functions accept any type of parameter when they really should only accept natural numbers. This can lead to surprising results (i.e: What's stopping the user from doing something like inpal::prime<SomeRandomType>::count_primes(some_object)). Also, you are not letting template argument deduction do its thing (deducing the type of the passed argument). Currently, every time you want to do an operation you must specify a type. Instead of doing inpal::prime<int>::max_prime(120) I should just be able to do inpa::max_prime(120).

This was meant to be a comment. If you want more critique feel free to ask and I shall try to provide some.

Edit: (more stuff):

You can use the magic of type_traits to construct the traits you need:

template <typename T> struct is_natural_helper : std::is_integral<T> {};
// Might as well disable bool
template <> struct is_natural_helper<bool> : std::false_type {};

template <typename T>
struct is_natural : is_natural_helper<std::remove_cv_t<T>> {};

Then inside your functions you can say:

static_assert(is_natural<T>::value, "T must be a natural number");

That way if the user passes an object of an invalid type that user will get a meaningful error message instead of a thousand lines (exaggerating) error message at compile time. Using template metaprogramming, you can avoid repetition in your source code and still get type safety.

\$\endgroup\$
1
  • \$\begingroup\$ Currently I make the templates just use either long, long long, unsigned long and unsigned long long. If the user puts a type different than the previous ones mentioned some compiler errors will occur. I am interested in knowing how to make it so the compiler can identify the type being used by the user, been researching a little about 'template argument deduction' but I don't know how to make it work. \$\endgroup\$ Commented Jul 7, 2016 at 14:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.