Exponentiation by squaring

related topics
{math, number, function}
{style, bgcolor, rowspan}
{rate, high, increase}
{mi², represent, 1st}

Exponentiating by squaring is a general method for fast computation of large integer powers of a number. Some variants are commonly referred to as square-and-multiply algorithms or binary exponentiation. In additive notation the appropriate term is double-and-add. These can be of quite general use: for example in modular arithmetic or powering of matrices.

Contents

Underlying idea

Using the following observation, one can create a recursive algorithm that computes xn for an integer n using squaring and multiplication:


x^n=     
    \begin{cases}
                1,                                          & \mbox{if }  n = 0   \\ 
                1/x^{-n},                                        & \mbox{if }  n < 0   \\ 
                x \cdot \left( x^{\frac{n-1}{2}} \right)^2, & \mbox{if } n \mbox { is odd} \\
               \left(  x^{\frac{n}{2}} \right)^2,           & \mbox{if }n\mbox{ is even}
     \end{cases}

A brief analysis shows that such an algorithm uses log2n squarings and at most log2n multiplications. For n > about 4 this is computationally more efficient than naïvely multiplying the base with itself repeatedly.

Full article ▸

related documents
Quadratic equation
Imaginary unit
Multiplication
Finite set
General linear group
Relational database
P = NP problem
AWK
Lie algebra
Busy beaver
Control flow
Polyomino
Riemannian manifold
Stochastic process
Semidirect product
Communication complexity
Category theory
Monoid
Exponential function
Interpolation
Operator
Set (mathematics)
Dylan (programming language)
Multiplication algorithm
Vacuous truth
Metric space
Support vector machine
Mathematical constant
Sorting algorithm
Taylor series