# 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.