AdvancedMath for DSABit Manipulation & Math
Fast power: xⁿ in O(log n)
x¹³ = x⁸ · x⁴ · x¹: square x repeatedly and multiply in the squares where n's binary has a 1. With a mod, it also gives modular inverses.
The idea
Multiplying x by itself n times is O(n). Instead write n in binary: 13 = 1101₂ = 8 + 4 + 1, so x¹³ = x⁸ · x⁴ · x¹. Squaring gives x, x², x⁴, x⁸… in log n steps; multiply in the ones you need.
With a prime modulus p, Fermat's little theorem gives division: a⁻¹ ≡ a^(p−2) mod p. That's how you compute nCr mod 10⁹ + 7.
Worked example
3¹³
- 13 = 1101 in binary. Squares: 3¹ = 3, 3² = 9, 3⁴ = 81, 3⁸ = 6,561.
- Bits set for 1, 4 and 8 → 3 × 81 × 6,561 = 1,594,323.
- 4 squarings instead of 12 multiplications.
In code (Python)
def power(x, n, mod=None):
result = 1
while n > 0:
if n & 1: # this bit is set: use the current square
result = result * x if mod is None else result * x % mod
x = x * x if mod is None else x * x % mod
n >>= 1
return result
def inverse(a, p=10**9 + 7): # p must be prime
return power(a, p - 2, p)
# Python's built-in pow(x, n, mod) does the same.O(log n) multiplications.
How to spot it
- Pow(x, n), huge exponents, “mod 10⁹+7” with division, matrix powers for fast Fibonacci.
Common mistakes
- Negative exponents: compute power(1/x, −n).
- Using a ** b % m in Python for huge b: pow(a, b, m) is far faster.
Where it comes up
Go further
Up next for you · Beginner
“Have I seen this?” is a set →