Fast exponentiation implementation

Question

Could someone please point out a site where I can find an algorithm to efficiently calculate integer exponentiation to large powers using C#?

eg. I want to calculate 2^60000 or 3^12345

Answer 1

Unless this is homework, you probably don't want to roll your own implementation of arbitrary precision exponentiation. Calculating large exponents of the type you describe is complicated - performance aside.

I would recommend using one of the existing arbitrary precision arithmetic libraries, like GMP - most of which have libraries to access them from C#.

F# has support for arbitrary precision arithmetic using the BigInt class (which you can also access from C# if you import the assembly it's in). However, I don't know how optimized BigInt exponentiation is.

If you're simply trying to learn about efficient algorithms for exponentiation, you may want to look into the Square-And-Multiply algorithm for exponentiation.

Answer 2

Integer exponentiation can effectively be calculated using a method known as "Exponentiation by squaring" link.

This method can also be used to calculate the modular exponentiation link, which is used in some asymmetric encryption methods like RSA.

Answer 3

Check this out: IntX for working with LARGE integers. You might have to write your own implementation of power, but since multiplication is supported, this should not be so hard.

Edit by 280Z28: Another implementation which includes fast Pow, ModPow, and primality testing is this BigInteger implementation (Code Project), which I've used on Project Euler problems in the past - though I now work with .NET 4.0 and use its System.Numerics.BigInteger implementation.