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