1
\$\begingroup\$

I have a class which lazily factors numbers. It provides the user with these methods:

  1. getFactors returns a vector<unsigned int> containing the argument's factors
  2. getFactorCount returns the number of an argument's factors
  3. compareFactors takes 2 arguments returning a negative integer if the 1st argument has fewer factors, a positive number if the 2nd argument has fewer factors, and a 0 if the arguments have the same number of factors
  4. findNextPrime returns the next prime after the current number
  5. gcd returns the Greatest Common Denominator of its arguments
  6. lcm returns the Least Common Multiple of its arguments

I welcome general advice on the class, but I have specific concerns in these areas:

  1. I'm varying a lot of extra memory to maintain the index of a numbers next factor as the my vector becomes large
  2. I have to reconstruct the vector of factors for every method I provide that seems expensive time wise

Is there a way that I could structure my data differently to avoid such costs?


#include <algorithm>
#include <functional>
#include <iostream>
#include <iterator>
#include <numeric>
#include <utility>
#include <vector>

using namespace std;

class Factor {
    vector<pair<unsigned int, size_t>> factors;

    void factor(const unsigned int input) {
        auto i = 2U;

        while (input % i != 0U) {
            ++i;
        }

        const auto second = input / i;

        factors[input] = make_pair(i, second);

        if (second >= 2 && factors[second].first == 0U) {
            factor(second);
        }
    }
public:
    vector<unsigned int> getFactors(unsigned int input) {
        if (input <= 1) {
            return vector<unsigned int>{};
        } else if (input >= size(factors)) {
            factors.resize(input + 1U);
            factor(input);
        } else if (factors[input].first == 0U) {
            factor(input);
        }

        vector<unsigned int> result;

        do {
            result.push_back(factors[input].first);
            input = factors[input].second;
        } while (factors[input].first != 0U);

        return result;
    }

    size_t getFactorCount(const unsigned int input) {
        return size(getFactors(input));
    }

    int compareFactors(const unsigned int lhs, const unsigned int rhs) {
        return getFactorCount(lhs) - getFactorCount(rhs);
    }

    unsigned int findNextPrime(unsigned int input) {
        if (++input == 1U) {
            return 1U;
        }

        do {
            if (input >= size(factors)) {
                factors.resize(input + 1U);
            }

            if (factors[input].first == 0U) {
                factor(input);
            }
        } while (factors[input++].second != 1U);

        return input - 1U;
    }

    unsigned int gcd(const unsigned int lhs, const unsigned int rhs) {
        vector<unsigned int> result;
        const vector<unsigned int> lhsFactors = getFactors(lhs);
        const vector<unsigned int> rhsFactors = getFactors(rhs);

        set_intersection(cbegin(lhsFactors), cend(lhsFactors), cbegin(rhsFactors), cend(rhsFactors), back_inserter(result));

        return accumulate(cbegin(result), cend(result), 1U, multiplies<unsigned int>());
    }

    unsigned int lcm(const unsigned int lhs, const unsigned int rhs) {
        const vector<unsigned int> lhsFactors = getFactors(lhs);
        const vector<unsigned int> rhsFactors = getFactors(rhs);
        const auto it = find_first_of(cbegin(lhsFactors), cend(lhsFactors), cbegin(rhsFactors), cend(rhsFactors));

        return it == cend(lhsFactors) ? 1U : *it;
    }
};

I've included some testing demonstrating class functionality here: http://ideone.com/njH34A

\$\endgroup\$

1 Answer 1

1
\$\begingroup\$
  • I think that adding U obfuscates the code

Two remarks regarding algorithms for gcd and lcm. I think much more readable would be :

int gcd(int lhs, int rhs)
{
    if (lhs == 0) return rhs;
    return gcd(rhs % lhs, lhs);
}


int lcm(int lhs, int rhs)
{
    int temp = gcd(lhs, rhs);
    return temp ? (lhs / temp * rhs) : 0;
}
  • If you can use auto, then do it where it can make code more readable, e.g. const vector<unsigned int>

  • I would also take a closer look at factor method - it is not very efficient. I think you don't have to check i to value greater than sqrt(input) and maybe consider using some kind of sieve (you could google the general idea), but I would first deal with other problems.

  • Resizing looks sketchy...

Great you want to use std !

\$\endgroup\$
4
  • \$\begingroup\$ Hmmm... I felt as though factor was the one thing in the whole class that was efficient. Why do you say it's inefficient? I may be misinterpreting your comment, but you know it's lazily populated, right? For example if I factor 4, 8, and 10, 3 will never be populated. \$\endgroup\$ Commented Aug 10, 2016 at 23:43
  • \$\begingroup\$ @JonathanMee as a general note, lazily populated != efficient (and in fact it isn't uncommon for it to mean that the computation is inefficient, or at least slow, so execution is deferred until such time as it needs to be done). \$\endgroup\$ Commented Aug 11, 2016 at 0:34
  • \$\begingroup\$ @Dannnno Really? You got a source for that relative to number factorization? That just sounds crazy to me, if I factor 1 large number, and the rest of my numbers are under 100 all the sudden I have to fill the entire vector<vector<pair<int, size_t>>? \$\endgroup\$ Commented Aug 11, 2016 at 12:40
  • \$\begingroup\$ @JonathanMee Besides common sense? No. In general, lazy initialization is really just deferred execution - it has nothing to do with how efficient that execution will be whenever it runs. Not doing more calculations than you need to when you need to is good, and is more efficient than the alternative, but lazy initialization isn't sufficient to call your algorithm "efficient". \$\endgroup\$ Commented Aug 11, 2016 at 13:23

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.