Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
Removed the tag "integer programming", which refers to something else. –  Noah Stein Dec 1 '11 at 15:01
7  
1  
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

2 Answers 2

up vote 1 down vote accepted

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.

share|improve this answer

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}} $$

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.