What is the fastest algorithm to find the power of positive integers? [duplicate]
Possible Duplicate:
The most efficient way to implement an integer based power function pow(int, int)
The only two methods that I know is,
A single for loop: extremely slow
Rewrite
recursively calculate.
I wonder is there a faster algorithm than these two? Any bitwise technique are welcome. Thank you.
C# demos for the two algorithms:
class Math {
static public Int64 recurPow( Int64 a, Int64 e ) {
if ( e == 0 )
return 1;
if ( e == 1 )
return a;
if ( ( e % 2 ) == 0 )
return recurPow(开发者_JS百科 a * a, e / 2 );
else
return recurPow( a * a, ( e - 1 ) / 2 );
}
static public Int64 iterPow( Int64 a, Int64 e ) {
Int64 result = a;
for ( Int64 i = 1; i < e; ++i )
result *= a;
return result;
}
}
The optimal algorithm is NP-complete, see http://en.wikipedia.org/wiki/Addition-chain_exponentiation
That page also links to a number of heuristic algorithms that give pretty good answers, you probably want one of them.
Are you doing comp3212 as well?
精彩评论