FoundationSource checked

Exponentiation by Squaring

Computes powers efficiently by repeatedly squaring the base and using the exponent's binary digits.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Numerical Methods
Difficulty: Beginner
Family: Number Theory
Tier: Foundation
Status: Verified
Review: Source Checked
Sources: 2
Formulas: 1
Relationships: 6
Code example: Ready
Visualization: Ready

Overview

Exponentiation by Squaring rewrites an exponent in binary. It squares the base each step and multiplies the result only when the current exponent bit is set.

Core Concepts

binary exponentsquaringassociativitymultiplicative identity

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(n)

Average

O(n log n)

Worst

O(n^2)

Space

O(n)

When to Use

Use it when powers with large nonnegative integer exponents are needed.
Use it when multiplication is associative, such as numbers, matrices, or modular residues.
Use it as the core of modular exponentiation.

When Not to Use

Avoid it for non-integer exponents.
Avoid it when multiplication is not associative or has side effects.
Avoid unchecked intermediate growth when no modulus or bounded representation is used.

What It Does

Computes powers in logarithmic multiplication count
Uses binary decomposition of the exponent

Use Cases

Fast integer or matrix powers
Modular exponentiation
Repeated function composition

Inputs

Numbers, vectors, matrices, or functions
Tolerance or precision settings

Outputs

Computed numeric result
Residual, factorization, or approximation

Key Formulas (1)

Square-and-multiply step

if bit is 1: result = result · base; base = base · base

if bit is 1: result = result * base; base = base * base

Uses the binary expansion of the exponent to reduce multiplications.

Pseudocode

1.Set result to the multiplicative identity.
2.While exponent is greater than zero:
3.If exponent is odd, multiply result by base.
4.Square the base.
5.Divide exponent by 2 using integer division.
6.Return result.

Canonical Example

Input: base = 3, exponent = 13
Output: 1594323
Explanation: 13 = 8 + 4 + 1, so the result multiplies 3^8, 3^4, and 3^1.

Implementation Notes

Maintain a result initialized to the multiplicative identity.
At each step, multiply result by base when the current exponent bit is one.
Square the base and shift the exponent until no bits remain.

Common Pitfalls

Forgetting the exponent-zero case.
Multiplying in the wrong order for noncommutative operations such as matrices.
Letting intermediate values overflow before modular reduction.

Interactive Mechanism Walkthrough

Iterative Convergence & State Trajectory

Show squaring the base and multiplying only when a binary exponent bit is set on a small fast exponentiation example.

Step 1 of 6: Set result to the multiplicative identity.

numerical-methods-mechanism

Notes

The same pattern works for matrices and modular residues when the operation has an identity and is associative.

Sources (2)

What each reference supports for this entry.

Modern Computer Arithmetic

Book

Reference for Exponentiation by Squaring's arithmetic operations, modular arithmetic, multiplication, division, or number-theoretic implementation details.

Open source