Effective implementation of algorithms (Master Thesis)
Effective and error-free implementation of algorithms
src/math/factorize/factorize_naive.h
Go to the documentation of this file.
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
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Defines