
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 squareandmultiply algorithms or binary exponentiation. In additive notation the appropriate term is doubleandadd. 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 x^{n} for an integer n using squaring and multiplication:
A brief analysis shows that such an algorithm uses log_{2}n squarings and at most log_{2}n 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 
