Effective implementation of algorithms (Master Thesis)
Effective and error-free implementation of algorithms
|
#include <modular_inverse_precomputed.h>
Public Member Functions | |
template<typename T > | |
void | initialize (T t_size) |
template<typename T > | |
SizeType | getInverse (T t_pos) |
Private Types | |
typedef std::vector< bool > ::size_type | SizeType |
Private Attributes | |
std::vector< SizeType > | inverses |
Calculate the modular inverses of all numbers modulo prime p in O(p) time and 2*p space.
The initialization is in O(p), query is in O(1). The implementation is thus useful for medium-sized p (limited memory), for which you will ask for many different inverses. If you will ask only limited number of questions, but the p is big, it is probably better to use ModularInverseGcd class
typedef std::vector<bool>::size_type math::modular_inverse::ModularInversePrecomputed_< PowerModImpl >::SizeType [private] |
SizeType math::modular_inverse::ModularInversePrecomputed_< PowerModImpl >::getInverse | ( | T | t_pos | ) | [inline] |
Return inverse of number pos
void math::modular_inverse::ModularInversePrecomputed_< PowerModImpl >::initialize | ( | T | t_size | ) | [inline] |
std::vector<SizeType> math::modular_inverse::ModularInversePrecomputed_< PowerModImpl >::inverses [private] |