What is the fastest algorithm to find the power of positive integers? [duplicate]

This question already has answers here: Closed 11 years ago.

Possible Duplicate:

The most efficient way to implement an integer based power function pow(int, int)

The only two methods that I know is,

1. A single for loop: extremely slow

2. 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?