Remake of factoring/prime factorization calculator

Question

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:

These calculations should only be done with positive integers. Would something like templates help keep this type-safe? What about throwing an exception?
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.
Can both calculate()s be better optimized, considering they perform numerous divisions?
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; } }

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.) — cHao
– cHao, Commented Sep 9, 2013 at 9:31
@cHao: It works. Thanks! You may put that as an answer, along with anything else you find, and I'll vote on it. — Jamal
– Jamal, Commented Sep 9, 2013 at 15:20
@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. — Jamal
– Jamal, Commented Sep 9, 2013 at 15:22
@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. — Jamal
– Jamal, Commented Sep 9, 2013 at 18:17

Jamal · Accepted Answer · 2013-09-09 23:17:23Z

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.

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())? — Jamal
– Jamal, Commented Sep 9, 2013 at 23:15
@Jamal I don't really understand your first question. Everything depends on how you link. — Olayinka
– Olayinka, Commented Sep 9, 2013 at 23:18
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. — Jamal
– Jamal, Commented Sep 9, 2013 at 23:24
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 — Olayinka
– Olayinka, Commented Sep 9, 2013 at 23:30
I have the test working. I just need to figure out how to use this concept with the other classes. — Jamal
– Jamal, Commented Sep 9, 2013 at 23:45

Jamal · Accepted Answer · 2013-12-26 23:51:09Z

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

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
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; }

(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() — Simon Forsberg
– Simon Forsberg, Commented Nov 28, 2013 at 19:57
@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. — Jamal
– Jamal, Commented Nov 28, 2013 at 19:59

Stack Exchange Network

Remake of factoring/prime factorization calculator

2 Answers 2

You must log in to answer this question.

Linked

Hot Network Questions

Remake of factoring/prime factorization calculator

2 Answers 2

You must log in to answer this question.

Linked

Related

Hot Network Questions