Effective implementation of algorithms (Master Thesis)
Effective and error-free implementation of algorithms
|
00001 #ifndef H_MATH_POWERMOD 00002 #define H_MATH_POWERMOD 00003 00007 #include "utils/static_assert/static_assert.h" 00008 #include "utils/preconditions/preconditions.h" 00009 #include <limits> 00010 #include "multmod_simple.h" 00011 #include "multmod_extended.h" 00012 00013 namespace math { 00014 namespace powermod { 00015 00016 # pragma GCC diagnostic ignored "-Wtype-limits" 00017 template <class MultModImpl> 00018 class Powermod_ { 00019 public: 00020 template <typename T> 00021 static T powermod(T base, T power, T modulo) { 00022 Preconditions::check(modulo > 0, "Modulo should be positive."); 00023 Preconditions::check(power >= 0, "We don't support modular inverses."); 00024 Preconditions::checkRange(base, modulo); 00025 const T max = MultModImpl::max_argument((T) 0); 00026 Preconditions::check(modulo <= max, "Too big argument for powermod"); 00027 // Beware of special case power==0 && modulo==1 (result is 0 not 1) 00028 if (modulo == 1) { 00029 return 0; 00030 } 00031 T result = 1; 00032 T current = base; 00033 while (power > 0) { 00034 if (power % 2) { 00035 result = MultModImpl::multmod(result, current, modulo); 00036 } 00037 current = MultModImpl::multmod(current, current, modulo); 00038 power /= 2; 00039 } 00040 return result; 00041 } 00042 00043 template <typename T> 00044 static T multmod(T a, T b, T modulo) { 00045 Preconditions::check(modulo > 0, "Modulo should be positive."); 00046 Preconditions::checkRange(a, modulo); 00047 Preconditions::checkRange(b, modulo); 00048 const T max = MultModImpl::max_argument((T) 0); 00049 Preconditions::check(modulo <= max, "Too big argument for multmod"); 00050 00051 return MultModImpl::multmod(a, b, modulo); 00052 } 00053 }; 00054 00055 typedef Powermod_<MultmodSimple> PowermodSimple; 00056 typedef Powermod_<MultmodExtendedOpt> PowermodExtended; 00057 00058 } // namespace powermod 00059 } // namespace math 00060 00061 #endif