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

Question

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( 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;
        }
    }

@John Zwinck: Thanks a lot. I searched 3 times but couldn't find that thread. — roxrook, Apr 24 '11 at 23:42
The fastest algorithm is almost always a pre-computed table lookup :-) — paxdiablo, Apr 25 '11 at 00:01
I believe second recursive call should be like this `recurPow( a * a, ( e - 1 ) / 2 ) * a`. Test it on a = 2, e = 5 — Dennis Krut, Mar 05 '13 at 22:08

score 3 · Accepted Answer · answered Apr 24 '11 at 23:45

3

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?

answered Apr 24 '11 at 23:45

riri

519
4
15

Thanks. I'm not in that class, just get to know it when reading a math book. – roxrook Apr 24 '11 at 23:48
Well we had that problem assigned to us. The lecturer has a habit of "accidentally" assigning unsolvable problems. – riri Apr 24 '11 at 23:57

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

1 Answers1