# Algorithm for computing powers

I was challenged by one of my fellow students to write a mini-library in the programming language called C that enables you to work with very large numbers (the numbers that the language offers natively have a maximum value they can hold).

After defining what a big number is, I have to re-define the basic operations such as addition and multiplication for these big numbers that I am creating. I've written algorithms for computing the sum and product, but I am stuck on calculating powers.

What efficient algorithms are there for computing powers of two numbers on paper, that I can then translate into code? (My base will always be an integer and my exponent will always be a positive integer.)

-
Removed the tag "integer programming", which refers to something else. – Noah Stein Dec 1 '11 at 15:01
One standard reference is Knuth, TAOCP vol. 2, Seminumerical Algorithms, which has a very detailed presentation of repeated squaring, addition chains, etc. Shockingly, Knuth is not referenced in said Wikipedia article, hence this comment. – Bill Dubuque Dec 1 '11 at 18:46
I would like to add that there is an excellent free library for computations with large numbers gmplib.org – Levon Haykazyan Dec 1 '11 at 19:36
@LevonHaykazyan Of course, but then I would be cheating, wouldn't I? :P – Paul Manta Dec 1 '11 at 20:34

fast exponentiation is defined as follows:

let a and n
if n=1 then a
else
if n is even then (a^2)^\frac{n}{2}
else a*a^(n-1)


$x^\frac{n}{2}$ and $x^{(n-1)}$ are computed recursively, for $a^2$ you can program a function $^2$ as follow $a= a_1^k+a_2$ where $k$ is the half of the length of $a$

$$a^2= (a_1)^2 10^2k+ 2*a_1*a_2 1°^k +a_2)^2$$

where $(a_1)^2$ and $(a_2)^2$ are computed recursively.

-

squared exponentiation is the way to go here

BigInt pow(BigInt a,BigInt n){
BigInt r= 1;
while(n>0){
if(mod(n,2)==1)r=mult(r,a);
a=mult(a,a);
n=div(n,2);
}
return r;
}


here mod(a,b) is the remainder of a/b mult(a,b) is a*b and div(a,b) is floor(a/b)

this relies on $a^n = {a^2}^{\lfloor \frac{n}{2}\rfloor }\cdot \begin{cases} a & \mbox{if }n\mbox{ is even}\\1 & \mbox{if }n\mbox{ is odd}\end{cases}$

or more precisely

$$a^n=\prod_{i=0}^{\lfloor\log n\rfloor}{\begin{cases} a^{2^i} & \mbox{if }\Big\lfloor \frac{n}{2^i}\Big\rfloor\mbox{ is even}\\1 & \mbox{if }\Big\lfloor \frac{n}{2^i}\Big\rfloor\mbox{ is odd}\end{cases}}$$

-
This solution assumes you are using some BigInt library because it is not predefined in C/C++. – hydroparadise Jan 13 '12 at 17:42
@hydroparadise the only hard function here is the mult, the div and mod functions here can be easily done with masks and shifts (it's always divide/mod by 2) – ratchet freak Jan 13 '12 at 22:25