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.)
Best Answer
squared exponentiation is the way to go here
here
mod(a,b)
is the remainder ofa/b
mult(a,b)
isa*b
anddiv(a,b)
isfloor(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}} $$