CODEWITHSUNDEEP
algorithmdivide-and-conquer
andandandand
andandandand

Reputation: 22270

divide and conquer approach for exponentiation?

As homework, I should implement a divide and conquer approach for exponentiation of big integers. I know Karatsuba's algorithm for multiplication, what divide and conquer algorithm could I apply to get the result of x^y, both being large integers?.

Upvotes: 5

Views: 10339

Answers (3)

ninjagecko
ninjagecko

Reputation: 91092

Consider x^256. Rather than doing x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x, one could do (...(((x^2)^2)^2...)^2 a mere 8 times (log2 of 256).

In general, write out your exponent as binary and apply the exponent-of-sum rule. Then as you calculate successive powers of x, multiply them in to an accumulator if they appear in the exponent (they will appear if there is a "1" in that digit in the exponent).

See http://en.wikipedia.org/wiki/Exponentiation_by_squaring

Upvotes: 4

Rezo Megrelidze
Rezo Megrelidze

Reputation: 3060

Here's a nice recursive algorithm. 

int pow(int a,int b)
{
    if(b == 0) return 1;
    else if(b % 2 == 0) return pow(a,b/2) * pow(a,b/2);
    else return a * pow(a,b-1);
}

Upvotes: 1

Femaref
Femaref

Reputation: 61437

There are a couple of algorithms grouped together under the name square and multiply. You could get some inspiration from them.

Upvotes: 8

Related Questions