Effective implementation of algorithms (Master Thesis)
Effective and error-free implementation of algorithms
|
00001 #ifndef H_MATH_FACTORIZE_FACTORIZE_WITH_ORACLE 00002 #define H_MATH_FACTORIZE_FACTORIZE_WITH_ORACLE 00003 00007 #include "utils/preconditions/preconditions.h" 00008 #include <vector> 00009 #include <utility> 00010 #include <limits> 00011 #include <map> 00012 #include <stdexcept> 00013 #include "math/primes/primes_fast.h" 00014 #include "oracle_pollard.h" 00015 #include "oracle_brent.h" 00016 00017 namespace math { 00018 namespace factorize { 00019 00020 // Note: We can't use math::primes::PrimesBasic because it will ruin our 00021 // complexity (usually Oracles are O(n^(1/4)) versus PrimesBasic O(n^(1/2))). 00022 template <typename CountType, class Oracle, class Primes = math::primes::PrimesFast> 00023 class FactorizeWithOracle_ { 00024 public: 00025 template <typename T> 00026 static std::vector<std::pair<T, CountType> > 00027 factorize(T number) 00028 { 00029 typedef typename std::vector<std::pair<T, CountType> > ResultType; 00030 00031 Preconditions::check(number > 1, "Too small or negative to factorize"); 00032 00033 std::map<T, CountType> factors; 00034 while (!Primes::isPrime(number)) { 00035 T factor = Oracle::findFactor(number); 00036 // safety checks on factor 00037 assert(factor > 1); 00038 assert(factor != number); 00039 assert(number % factor == 0); 00040 number /= factor; 00041 ResultType tmp = factorize(factor); 00042 for (typename ResultType::size_type i = 0; i < tmp.size(); i++) 00043 factors[tmp[i].first] += tmp[i].second; 00044 } 00045 factors[number]++; 00046 return ResultType(factors.begin(), factors.end()); 00047 } 00048 00049 }; 00050 00051 typedef FactorizeWithOracle_<int, OraclePollard> FactorizePollard; 00052 typedef FactorizeWithOracle_<int, OracleBrent> FactorizeBrent; 00053 00054 00055 } // namespace factorize 00056 } // namespace math 00057 #endif