Primality test program

Question

I am fairly new to programming and even newer to C++ but I am currently in a class for scientific computing, and our task from two weeks ago was to improve the speed of a primality test program. I regrettably do not have the original code because I wrote over it, but the long and short was that program selects 100,000 integers from 100,000 to 999,999 and checks all numbers from 2 to less than the number.

Needless to say, it took over 17 seconds to run. My code was able to get it down to ~74 milliseconds. I handed in my code last week but it's been bugging me that I don't know if I got it as fast as it could go.

(The area I made is at the bottom, at int CountPrimes)

#include "stdafx.h"

using namespace std;
using namespace chrono;

int CountPrimes(unique_ptr<vector<int>> const &samples);

seed_seq seed{ 2016 };
default_random_engine generator{ seed };
uniform_int_distribution<int> distribution(100000, 999999);

int main()
{
    const auto samples{ make_unique<vector<int>>(100000) };

    for (auto &sample : *samples)
        sample = distribution(generator);

    cout.imbue(std::locale(""));
    cout << "Searching vector of "
        << samples->size() << " integers..."
        << endl;

    auto startTime = system_clock::now();

    int numPrimes = CountPrimes(samples);

    auto stopTime = system_clock::now();

    auto totalTime = duration_cast<milliseconds>(stopTime - startTime);

    cout << "Number of Primes: " << numPrimes << endl;
    cout << "Total run time (ms): " << totalTime.count() << endl;

    system("pause");
    return 0;
}


int CountPrimes(unique_ptr<vector<int>> const &samples)
{
    int numPrimes{};
    for (const auto &sample : *samples) {
        bool isPrime = true;
        int n{ 2 };
        int m{ 3 };
        if (sample % n == 0)
        {
            isPrime = false;
        }
        while (m < sample && m < 990)
        {
            if (sample % m == 0)
            {
                isPrime = false;
                break;
            }
            m += 2;
        }

        if (isPrime)
            numPrimes++;
    }
    return numPrimes;
}

Answer 1

Your CountPrimes function wrongly returns 3 (instead of the correct answer 0) when given the input {982081, 988027, 994009}. Can you see why?

---

Once you get down into dozens-of-milliseconds time ranges, it makes sense to increase the size of your test case so that you can distinguish real algorithmic improvements from noise. I recommend using 10,000,000 integers in your vector instead of 100,000, so that your runtimes are back up in the whole numbers of seconds instead of faster-than-human-reaction-time. A change that takes your runtime from 3.5 seconds to 1.5 seconds is vastly more likely to be a real optimization than a change that takes your reported runtime from 75 milliseconds to 20 milliseconds.

---

seed_seq seed{ 2016 };
default_random_engine generator{ seed };
uniform_int_distribution<int> distribution(100000, 999999);

Global variables are evil. In this case, these variables are used only by main; so you should make them local to main. (If you still wanted them to be statically allocated instead of stack-allocated, you could qualify them with static; but protip: there's no reason to do that.)

---

int CountPrimes(unique_ptr<vector<int>> const &samples)

Stylistically, most C++ programmers would write this as

int CountPrimes(const std::unique_ptr<std::vector<int>>& samples)

(having internalized the advice that using namespace std; is a bad habit, and finding const X& easier to read than X const &). Your mileage may vary.

However, definitely you should not be using unique_ptr here. You have three indirections here where only one is needed:

• The actual data is in a buffer on the heap...
• which is pointed to by a pointer wrapped in a std::vector...
• which is pointed to by a pointer wrapped in a std::unique_ptr...
• which is pointed to by the reference argument to CountPrimes.

Instead of all this indirection, I recommend either the "standard" two levels of indirection:

int CountPrimes(const std::vector<int>& samples)

or if you can use the C++ Core Guidelines support library, you could dispense with one more level:

int CountPrimes(gsl::span<int> samples)

Anyway, get rid of that unique_ptr. It's not buying you anything. And as a good rule of thumb: passing any kind of smart pointer by reference is just as much of a code smell as passing a core-language pointer by reference. If you find yourself doing it, something is probably wrong with your design!

---

int numPrimes{};

is IMHO a needlessly convoluted way to write

int numPrimes = 0;

Likewise,

int n{ 2 };
if (sample % n == 0)
{
    isPrime = false;
}

is IMHO a needlessly complicated way to write

if (sample % 2 == 0) {
    continue;
}

When you know the input isn't prime, any further work you do after that point is wasted. Don't spend time looping on m if you're just going to throw that work away in the end.

---

If I were writing this code, I'd make a helper function bool IsPrime(int x) that just returns true if x is prime; and then my CountPrimes function could be

int CountPrimes(const std::vector<int>& v)
{
    int result = 0;
    for (auto&& x : v) {
        if (IsPrime(x)) ++result;
    }
    return result;
}

Notice the complete lack of goto, break, or continue in this program; that is, I'm enabling the use of structured programming by breaking my code down into subroutines.

The only reason not to arrange your program logically in this way is if you expect to get some benefit from logically arranging the computations a different way. For example, maybe we could exploit SSE vectorized instructions to do the computation four times faster, something like this:

int CountPrimes4x(const int *abcd)
{
    // use some _mm_... intrinsics or something
}

int CountPrimes(const std::vector<int>& v)
{
    int result = 0;
    assert(v.size() % 4 == 0);
    for (size_t i=0; i < v.size(); i += 4) {
        result += CountPrimes4x(&v[i]);
    }
    return result;
}

Problem is, there's no fast integer division instruction on x86, so we might not come up with anything better than the plain old (slow) (non-vectorized) integer division we started with.

Answer 2

It seems to me that, since you have a series of numbers to check for primality, that making a vector with all the indexes that are prime set to true would mean only finding primes once, instead of for each odd number. Using a Sieve of Eratosthenes, makes this process very fast and efficient.

vector<bool> GetPrimes( int target )
{
    int sieveBound = (int)( target - 1 );
    int upperSqrt = ( (int)sqrt( target ) );
    vector<bool> primeBits(sieveBound,true);
    for ( int i = 3; i <= upperSqrt; i += 2 )
    {
        if ( primeBits[i] )
        {
            int step = i * 2;
            for ( int j = i * i; j <= sieveBound; j += step )
            {
                primeBits[j] = false;
            }
        }
    }

    return primeBits;
}

This algorithm has been optimized to ignore all the even indexes, since that is easily checked. Now checking your samples is a matter of identifying only the odd numbers and seeing if the index is true:

vector<bool> primes = GetPrimes( 1000000 );
int count = 0;
for ( int i : samples )
{
    if (i % 2 != 0 && primes[i] )
    {
        count++;
    }
}