Binary Exponentiation Calculator
Calculate integer powers quickly using binary exponentiation, also called exponentiation by squaring or square-and-multiply. Compute exact powers or modular powers, inspect the exponent's binary representation, and follow every squaring and multiplication step.
Calculate a power
Calculation result
Step-by-step square-and-multiply trace
The exponent is processed from its least significant bit to its most significant bit. A set bit (1) means the current factor is multiplied into the running result.
| Step | Exponent bit | Bit value | Result after step | Factor used | Action |
|---|
What is binary exponentiation?
Binary exponentiation is a fast way to calculate powers by using the binary representation of the exponent. Instead of multiplying the base by itself one exponent unit at a time, the algorithm repeatedly squares intermediate factors and multiplies only when the relevant exponent bit is 1.
aⁿ = a^(b₀·2⁰ + b₁·2¹ + ... + bₖ·2ᵏ)Each exponent bit \(b_i\) is either 0 or 1. A bit of 1 means its corresponding power of the base contributes to the final product. This approach requires a number of steps proportional to the number of bits in the exponent.
Example: calculate 3¹³
The exponent 13 has binary representation 1101.
Its set bits represent 8, 4 and 1, so:
Binary exponentiation builds these powers using repeated squaring. The interactive trace above shows how the running result and factor change at each bit.
Modular exponentiation
Modular exponentiation computes the remainder after raising a base to an exponent:
r = aⁿ mod m
Rather than calculating the entire power and taking the remainder
only at the end, the algorithm reduces intermediate values modulo
m. For a positive modulus, this keeps the intermediate
values smaller and is particularly useful in number theory and
cryptographic algorithms.
Example: 3¹³ mod 17
The exact power is 1,594,323. Dividing by 17 leaves remainder 12, so the modular result is:
3¹³ mod 17 = 12Binary exponentiation versus repeated multiplication
| Feature | Repeated multiplication | Binary exponentiation |
|---|---|---|
| Basic approach | Multiply by the base repeatedly | Square factors and multiply for set bits |
| Number of steps | Proportional to the exponent | Proportional to the exponent's bit length |
| Time complexity in arithmetic operations | O(n) for exponent n | O(log n) for exponent n greater than zero |
| Modular computation | Possible but potentially inefficient | Reduces intermediate values modulo m |
| Large exponents | Can require many multiplications | Usually far fewer multiplications |
These complexity figures count arithmetic operations, not the cost of multiplying increasingly large integers.
Binary exponentiation FAQs
What is binary exponentiation used for?
It efficiently calculates integer powers and modular powers. Related applications include number theory, powering matrices, and algorithms used in cryptography.
Does an exponent of zero always give 1?
For ordinary exponentiation, a⁰ = 1 for a nonzero base, and the usual algebraic convention also defines 0⁰ as 1 in many computational settings. In modular mode, the result is 1 mod m, which is 0 when m = 1.
Why does the calculator use BigInt?
JavaScript's ordinary Number type cannot represent every large integer exactly. BigInt allows exact integer arithmetic for the supported base, exponent, and modulus inputs.
Can the calculator handle negative bases?
Yes. Negative integer bases are supported in both modes. For ordinary powers, an odd exponent produces a negative result for a negative base, while an even exponent produces a positive result. Modular results are normalized to a non-negative remainder for a positive modulus.
Are negative exponents supported?
No. This page focuses on exact integer powers and modular exponentiation with non-negative integer exponents. A negative exponent generally requires rational or fractional results.