Fast Exponentiation
Compute (a^b) % m efficiently in O(log b) time using Binary Exponentiation.
Ready to calculate.
Result (res)
1
Current Base (a)
0
Exponent (b)
0
Current Exponent (Binary)
0
Calculation Complete!
Always: Square the Base
a = (0 * 0) % 1000
See the Logic in Motion
Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.Intuition
Calculating a^b by multiplying a, b times takes O(b) time. We can do better by squaring the base repeatedly. For example, a^8 = ((a^2)^2)^2. This takes only O(log b) steps.
Concept
- Binary Representation: Any number
bcan be written as a sum of powers of 2 (e.g., 13 = 8 + 4 + 1). - Decomposition:
a^13 = a^(8+4+1) = a^8 * a^4 * a^1. - Algorithm: Iterate through bits of
b. If the current bit is 1, multiply the result by the current power ofa. In every step, squareato get the next power.
How it Works
Steps:
- Initialize
res = 1. - While
b > 0:- If
bis odd (last bit is 1),res = res * a. a = a * a(Square the base).b = b / 2(Shift right to process next bit).
- If
Step-by-Step Breakdown
Watch the visualization:
- Purple: Current exponent bit being checked.
- Green: Result updates when bit is 1.
- Blue: Base squaring happens every step.
When to Use
- Calculating large powers modulo M (Cryptography).
- Matrix Exponentiation (solving recurrences like Fibonacci in O(log N)).
When NOT to Use
- Small exponents where simple loop is sufficient.
- When precision is required for non-integer exponents.
How to Identify
"Calculate (A^B) % M", "N-th Fibonacci number for very large N".
Stop Guessing, Start Mastering.
Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.