Tag: code

I'm trying to improve the examples of Own code* by re-implementing them in C ++. This time, it is the sieve of Eratosthenes, an example of computation based on the primordial computer science on pp.

Below, the original adapted for C ++, without improvements:

.h

class PrimeGenerator { 
public:
    PrimeGenerator() = default;
    ~PrimeGenerator() = default;

    static std::vector generatePrimes(unsigned maxValue);

private:
    static void uncrossIntegersUpTo(unsigned maxValue);
    static void crossOutMultiples();
    static unsigned determineIterationLimit();
    static void crossOutMultiplesOf(unsigned i);
    static bool notCrossed(unsigned i);
    static void putUncrossedIntegersIntoResult();
    static unsigned numberOfUncrossedIntegers();

    static std::vector crossedOut;
    static std::vector result; 
};

cpp

std::vector PrimeGenerator::crossedOut;
std::vector PrimeGenerator::result;

std::vector PrimeGenerator::generatePrimes(unsigned maxValue)
{
    if (maxValue < 2)
        return {};

    uncrossIntegersUpTo(maxValue);
    crossOutMultiples();
    putUncrossedIntegersIntoResult();
    return result;
}

void PrimeGenerator::uncrossIntegersUpTo(unsigned maxValue)
{
    crossedOut = std::vector(maxValue + 1, false);
    crossedOut(0) = true;
    crossedOut(1) = true;
}

void PrimeGenerator::crossOutMultiples()
{
    unsigned limit = determineIterationLimit();
    for (size_t i = 2; i <= limit; ++i)
    {
        if (notCrossed(i))
            crossOutMultiplesOf(i);
    }
}

unsigned PrimeGenerator::determineIterationLimit()
{
    // Every multiple in the array has a prime factor that
    // is less than or equal to the root of the array size,
    // so we don't have to cross out multiples of numbers
    // larger than that root.
    double iterationLimit = std::sqrt(crossedOut.size());
    return static_cast(iterationLimit);
}

void PrimeGenerator::crossOutMultiplesOf(unsigned i)
{
    for (size_t multiple = 2 * i; multiple < crossedOut.size(); multiple += i)
    {
        crossedOut(multiple) = true;
    }
}

bool PrimeGenerator::notCrossed(unsigned i)
{
    return !crossedOut(i);
}

void PrimeGenerator::putUncrossedIntegersIntoResult()
{
    result = std::vector(numberOfUncrossedIntegers());
    size_t j = 0;
    for (size_t i = 2; i < crossedOut.size(); ++i)
    {
        if (notCrossed(i))
            result(j++) = i;
    }
}

unsigned PrimeGenerator::numberOfUncrossedIntegers()
{
    unsigned count = 0;
    for (size_t i = 2; i < crossedOut.size(); ++i)
    {
        if (notCrossed(i))
            count++;
    }

    return count;
}

What we see here is a static class with static functions and members. We do not like this in C ++, so it seems that this code could be better served with a namespace and free functions. Let's try - my attempt at improvement comes below.

.h

namespace PrimeGenerator
{
    std::vector generatePrimes(unsigned maxValue);
}

cpp

namespace {

std::vector uncrossIntegersUpTo(int maxValue)
{
    std::vector crossedOut(maxValue + 1, false);
    crossedOut(0) = true;
    crossedOut(1) = true;

    return crossedOut;
}

unsigned determineIterationLimit(size_t size)
{
    // Every multiple in the array has a prime factor that
    // is less than or equal to the root of the array size,
    // so we don't have to cross out multiples of numbers
    // larger than that root.
    double iterationLimit = std::sqrt(size);
    return static_cast(iterationLimit);
}

void crossOutMultiplesOf(unsigned i, std::vector& crossedOut)
{
    for (size_t multiple = 2 * i; multiple < crossedOut.size(); multiple += i)
    {
        crossedOut(multiple) = true;
    }
}

void crossOutMultiples(std::vector& crossedOut)
{
    unsigned limit = determineIterationLimit(crossedOut.size());
    for (size_t i = 2; i <= limit; ++i)
    {
        if (!crossedOut(i))
            crossOutMultiplesOf(i, crossedOut);
    }
}

std::vector putUncrossedIntegersIntoResult(const std::vector& crossedOut)
{
    std::vector result;
    for (size_t i = 2; i < crossedOut.size(); ++i)
    {
        if (!crossedOut(i))
            result.push_back(i);
    }

    return result;
}

}

namespace PrimeGenerator {

std::vector generatePrimes(unsigned maxValue)
{
    if (maxValue < 2)
        return {};

    auto crossedOut = uncrossIntegersUpTo(maxValue);
    crossOutMultiples(crossedOut);
    return putUncrossedIntegersIntoResult(crossedOut);
}

}

A quick summary of the changes:
- I deleted the class, leaving only one interface function in a PrimeGenerator namespace.
- The numberOfUncrossedIntegers() the function did not seem to make much sense, so I refactored putUncrossedIntegersIntoResult(...) get rid of the old.
- notCrossed(...) would now need two parameters, so that makes no sense. It's gone now.

Now, I have two questions about my code. First of all, we must now pass the crossedOut vector around, which is a disadvantage compared to the previous design. Would you suggest an alternative solution to mitigate this? Secondly, are there any additional places where I should have used size_t instead of unsigned?

Cheers!

* Clean Code: An Agile Software Craft ManualRobert C. Martin