Skip to content

Instantly share code, notes, and snippets.

@Chillee

Chillee/binExp32.cpp

Last active March 28, 2019 19:58
Show Gist options
  • Save Chillee/cfeef064991315737f8edba0837bf3f6 to your computer and use it in GitHub Desktop.
Save Chillee/cfeef064991315737f8edba0837bf3f6 to your computer and use it in GitHub Desktop.
Download ZIP
Binary Exponentiation
Raw
binExp32.cpp
int binExp(int b, int pw) {
if (pw == 0)
return 1;
return binExp(b * b % MOD, pw / 2) * (pw & 1 ? b : 1) % MOD;
}
Raw
binExp64.cpp
const int bits = 10;
const int po = 1 << bits;
// if all numbers are less than 2ˆk , set bits = 64−k
ull modMul(ull a, ull b, ull &c) {
ull x = a * (b & (po - 1)) % c;
while ((b >>= bits) > 0) {
a = (a << bits) % c;
x += (a * (b & (po - 1))) % c;
}
return x % c;
}
ull binExp(ull b, ull pw, ull MOD) {
if (pw == 0)
return 1;
return modMul(binExp(modMul(b, b, MOD), pw / 2, MOD), (pw & 1 ? b : 1), MOD);
};
@Chillee
Copy link
Author

Chillee commented Mar 28, 2019

BinExp64 runs in O(64/bits * log b)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment