8
\$\begingroup\$

Background info on factoring and prime factorization.

I've remade this program from my first attempt, and I'm sure it can still be improved. My questions:

  1. These calculations should only be done with positive integers. Would something like templates help keep this type-safe? What about throwing an exception?
  2. Is this an effective way to use the typedefs? Only the classes need them, so it seems better to qualify them with each class rather than a namespace.
  3. Can both calculate()s be better optimized, considering they perform numerous divisions?
  4. I'm not quite liking the call to calculate() in both display()s, even though there are no data member changes. Is this still okay? It doesn't quite make sense to perform the calculations in the constructor, and calculate() should still be private.

Factors.h

#ifndef FACTORS_H
#define FACTORS_H

#include <cstdint>
#include <map>

class Factors
{
private:
    typedef std::map<std::uint64_t, std::uint64_t> FactorsList;
    std::uint64_t integer;
    FactorsList calculate() const;

public:
    Factors(std::uint64_t);
    void display() const;
};

#endif

Factors.cpp

#include "Factors.h"
#include <cmath>
#include <iostream>

Factors::Factors(std::uint64_t i) : integer(i) {}

Factors::FactorsList Factors::calculate() const
{
    float sqrtInt = std::sqrt(static_cast<float>(integer));
    FactorsList factors;

    for (std::uint64_t i = 1; i <= sqrtInt; ++i)
    {
        if (integer % i == 0)
        {
            factors[i] = integer / i;
        }
    }

    return factors;
}

void Factors::display() const
{
    FactorsList factors = calculate();

    for (auto iter = factors.cbegin(); iter != factors.cend(); ++iter)
    {
        std::cout << iter->first << " x " << iter->second << "\n";
    }
}

Primes.h

#ifndef PRIMES_H
#define PRIMES_H

#include <cstdint>
#include <map>

class Primes
{
private:
    typedef std::map<std::uint64_t, std::uint64_t> PrimesList;
    std::uint64_t integer;
    PrimesList calculate() const;

public:
    Primes(std::uint64_t);
    void display() const;
};

#endif

Primes.cpp

#include "Primes.h"
#include <iostream>

Primes::Primes(std::uint64_t i) : integer(i) {}

Primes::PrimesList Primes::calculate() const
{
    std::uint64_t intCopy = integer;
    std::uint64_t divisor = 2;
    PrimesList primes;

    while (intCopy % divisor == 0)
    {
        intCopy /= divisor;
        primes[divisor]++;
    }

    for (divisor = 3; intCopy > 1; divisor += 2)
    {
        while (intCopy % divisor == 0)
        {
            intCopy /= divisor;
            primes[divisor]++;
        }
    }

    return primes;
}

void Primes::display() const
{
    PrimesList primes = calculate();

    for (auto iter = primes.cbegin(); iter != primes.cend(); ++iter)
    {
        if (iter != primes.cbegin()) std::cout << " x ";
        std::cout << iter->first;
        if (iter->second > 1) std::cout << '^' << iter->second;
    }
}
\$\endgroup\$
4
  • 2
    \$\begingroup\$ One thing i can say right off, you could probably roughly double the speed of Primes::calculate by checking 2 independently, and then only checking odd numbers. (Once you've factored out all the 2s, intCopy won't be divisible by any even number.) \$\endgroup\$ – cHao Sep 9 '13 at 9:31
  • \$\begingroup\$ @cHao: It works. Thanks! You may put that as an answer, along with anything else you find, and I'll vote on it. \$\endgroup\$ – Jamal Sep 9 '13 at 15:20
  • \$\begingroup\$ @cHao: I've also just realized that it was already mentioned in my previous question, but oh well. At least this has been confirmed now. \$\endgroup\$ – Jamal Sep 9 '13 at 15:22
  • \$\begingroup\$ @cHao: I'll go ahead and make this change anyway (again, I should've gotten it from the first post). Feel free to address anything else you may find. \$\endgroup\$ – Jamal Sep 9 '13 at 18:17
1
\$\begingroup\$

Yes. You can use template, if you use template, you won't be able to separate the declarations and definitions of member functions without explicit instantiations, which is exactly what you need. Only the instantiated types will then be allowed. For example;

//header file test.h
#ifndef TEST_H
#define TEST_H

template<typename T>
class Test{
public:
    T doSomething();
};

#endif

//test.cpp
#include"test.h"

//explicit instantiations
template class Test<unsigned char>;
template class Test<unsigned short>;
template class Test<unsigned int>;
template class Test<unsigned long>;
template class Test<unsigned long long>;


template<typename T>
T Test<T>::doSomething(){
    return T();
}

//main.cpp
#include<iostream>
#include"test.h"

int main(){
    std::cout << Test<long>().doSomething(); //linker error, no compilation
    std::cout << Test<unsigned long>().doSomething(); //compile and works well
}

Also the use of typedef inside the class is not a bad idea. It serves the purpose of keeping the use of the alias limited to the class and its members.

Another thing I would like to point out is , since this is a local library, you might as well have a read only file that contains the list of prime numbers attached to the primes library, this will make the prime factorization of very large numbers a lot more faster. For example in the primes.cpp file you can add

std::ifstream PRIMES;
#define OPEN_PRIMES PRIMES.open("primes");
#define CLOSE_PRIMES PRIMES.close();

and you will be able to do

std::uint64_t divisor;
OPEN_PRIMES;
for (; intCopy > 1 && PRIMES >> divisor;){
    while (intCopy % divisor == 0){
        intCopy /= divisor;
        primes[divisor]++;
    }
}
CLOSE_PRIMES;

Also you can check out how to generate factors from prime factorization.

\$\endgroup\$
7
  • \$\begingroup\$ So, Test will be a new class? Will main() include this along with the other headers, or will Test be kept inside of them (and not included in main())? \$\endgroup\$ – Jamal Sep 9 '13 at 23:15
  • \$\begingroup\$ @Jamal I don't really understand your first question. Everything depends on how you link. \$\endgroup\$ – Olayinka Sep 9 '13 at 23:18
  • \$\begingroup\$ I mean, you're defining Test as a new class. I just want to confirm if all the templating will happen in there, while being used by the client code. \$\endgroup\$ – Jamal Sep 9 '13 at 23:24
  • 1
    \$\begingroup\$ On compilation, the compiler will produce instances of the classes for each template provided and therefore will not take any other instance afterwards. msdn.microsoft.com/en-us/library/by56e477.aspx \$\endgroup\$ – Olayinka Sep 9 '13 at 23:30
  • \$\begingroup\$ I have the test working. I just need to figure out how to use this concept with the other classes. \$\endgroup\$ – Jamal Sep 9 '13 at 23:45
5
\$\begingroup\$

Factors::calculate() can be sped up by:

  1. performing two integer adds after each iteration to determine loop termination

    • std::sqrt()'s overhead, calculations, and casting can be slow
    • for-loops shouldn't increment towards a floating-point value
    • incrementing towards an integer value is faster and proper
    • adding is generally fast and can be done in place of multiplication
  2. starting the loop counter at 2 or 3 (if integer is even or odd respectively)

    • fewer increments means fewer division operations (division is slow)

This integer add method replaces multiplication as such:

0*0 = 0
1*1 = 1 = 0 + 1
2*2 = 4 = 1 + 3
3*3 = 9 = 4 + 5
4*4 = 16 = 9 + 7
// etc.

Revised function with explanations:

Factors::FactorsList Factors::calculate() const
{
    FactorsList factors;
    std::uint64_t incr = 0;    // will increment by 2 each iteration
    std::uint64_t incrSum = 1; // will accumulate value of 'incr' each iteration

    // if integer is even, i starts at 2
    // if integer is odd, i starts at 3
    std::uint64_t i = (integer % 2 == 0) ? 2 : 3;

    // 'i' is only incremented by 1 for checking each number
    // value of 'incrSum' will determine loop termination
    for (; incrSum <= integer; ++i)
    {
        if (integer % i == 0)
        {
            factors[i] = integer / i;
        }

        incr += 2;
        incrSum += incr;
    }

    return factors;
}
\$\endgroup\$
2
  • \$\begingroup\$ (Non C++ expert talking here) Is one call to std::sqrt() really more costly than multiple i*i calls? For small number of iterations I would expect this to be true, but at some point I would think that x number of i*i calls is less efficient than one std::sqrt() \$\endgroup\$ – Simon Forsberg Nov 28 '13 at 19:57
  • \$\begingroup\$ @SimonAndréForsberg: I have been told that the function itself is a bit slow. The main issue with this is that I would need to do casting to work with the function, and I cannot have that in the loop. \$\endgroup\$ – Jamal Nov 28 '13 at 19:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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