Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Exponentiation by squaring
Summary
In mathematics and computer programming, exponentiating by squaring is a general method for fast computation of large positive integer powers of a number, or more generally of an element of a semigroup, like a polynomial or a square matrix. Some variants are commonly referred to as square-and-multiply algorithms or binary exponentiation. These can be of quite general use, for example in modular arithmetic or powering of matrices. For semigroups for which additive notation is commonly used, like elliptic curves used in cryptography, this method is also referred to as double-and-add.
The method is based on the observation that, for any integer , one has:
If the exponent is zero then the answer is 1 and if the exponent is negative then we can reuse the previous formula by rewriting the value using a positive exponent. That is,
Together, these may be implemented directly as the following recursive algorithm:
In: an integer x; an integer n
Out: xn
exp_by_squaring(x, n)
if n < 0 then
return exp_by_squaring(1 / x, -n);
else if n = 0 then
return 1;
else if n is even then
return exp_by_squaring(x * x, n / 2);
else if n is odd then
return x * exp_by_squaring(x * x, (n - 1) / 2);
end function
In each recursive call, the least significant digits of the binary representation of n is removed. It follows that the number of recursive calls is the number of bits of the binary representation of n. So this algorithm computes this number of squares and a lower number of multiplication, which is equal to the number of 1 in the binary representation of n. This logarithmic number of operations is to be compared with the trivial algorithm which requires n − 1 multiplications.
This algorithm is not tail-recursive. This implies that it requires an amount of auxiliary memory that is roughly proportional to the number of recursive calls -- or perhaps higher if the amount of data per iteration is increasing.
The algorithms of the next section use a different approach, and the resulting algorithms needs the same number of operations, but use an auxiliary memory that is roughly the same as the memory required to store the result.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.