Effective implementation of algorithms (Master Thesis)
Effective and error-free implementation of algorithms
|
00001 #ifndef H_MATH_FACTORIZE_FACTORIZE_NAIVE 00002 #define H_MATH_FACTORIZE_FACTORIZE_NAIVE 00003 00006 #include "utils/preconditions/preconditions.h" 00007 #include <vector> 00008 #include <utility> 00009 #include <limits> 00010 #include <stdexcept> 00011 #include "utils/static_assert/static_assert.h" 00012 00013 namespace math { 00014 namespace factorize { 00015 00022 template <typename CountType> 00023 class FactorizeNaive_ { 00024 public: 00034 template <typename T> 00035 static std::vector<std::pair<T, CountType> > 00036 factorize(T number) 00037 { 00038 STATIC_ASSERT(std::numeric_limits<T>::is_integer, 00039 "T should be integral"); 00040 Preconditions::check(number > 1, "Too small or negative to factorize"); 00041 std::vector<std::pair<T, CountType> > result; 00042 00043 // Note: following check is a bit relaxed, exact value is 00044 // sqr(sqrt(max)-1), but it is a way complicated to check 00045 // This simple check is sufficient 00046 if (number > std::numeric_limits<T>::max() >> 1) { 00047 throw std::overflow_error("Sorry, argument is too big to process"); 00048 } 00049 for (T i = 2; i * i <= number; i++) { 00050 if (number % i == 0) { 00051 CountType cnt = 0; 00052 while (number % i == 0) { 00053 cnt++; 00054 number /= i; 00055 } 00056 result.push_back(std::make_pair(i, cnt)); 00057 } 00058 } 00059 00060 if (number > 1) { 00061 result.push_back(std::make_pair(number, 1)); 00062 } 00063 return result; 00064 } 00065 }; 00066 00068 typedef FactorizeNaive_<int> FactorizeNaive; 00069 00070 } // namespace factorize 00071 } // namespace math 00072 #endif