开发者

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

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

    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?

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜