CP DSA Implementations

Binary Exponentiation

source: cp-algorithms

Generic binary exponentiation to compute \( b^N \) in \( O(logN) \). Any type with the T * T operator defined can be used. In case the type does not have an identity value simply exponentiate until \( N-1 \) and set the initial value of res to the base.

template <typename T> T binexp(T a, ull b) {
  T res = 1; //@ identity
  while(b > 0) {
    if(b & 1) res = res * a;
    a = a * a;
    b /= 2;
  }
  return res;
}

Dependencies.

typedef unsigned long long ull;
type operator*(const type& a, const type& b);

Computation of Exponents Modulo a Number

source: cp-algorithms

Compute \( x^N mod m \) efficiently. Any type which can be used in the previous binexp can also be used in the modular version, with the additional constraint of needing to define the T % T operator defined.

template <typename T> T binexp(T a, ull b, T m) {
  a = a % m;
  T res = 1;
  while(b > 0) {
    if(b & 1) res = res * a % m;
    a = a * a % m;
    b /= 2;
  }
  return res;
}