Fast implementation of exponentiation
Can anyone point out a site where I can find an algorithm to efficiently compute high cardinality integer exponentiation using C #?
eg. I want to calculate 2 ^ 60000 or 3 ^ 12345
Unless this is homework, you probably don't want to rollback your own implementation of arbitrary precision exponentiation. Computing large metrics of the type you describe is tricky - performance aside.
I would recommend using one of the existing arbitrary precision arithmetic libraries like GMP - most of them have libraries to access them from C #.
F # supports arbitrary precision arithmetic using the BigInt class (which you can also access from C # if you import it into an assembly). However, I don't know how optimized BigInt's optimization is.
If you're just trying to learn about efficient algorithms for exponentiation, you may need to learn the Square-and-Multiply algorithm for exponentiation.
Integer exponentiation can be efficiently calculated using a technique called "squaring", ref .
This method can also be used to calculate the modular exponentiation of a link , which is used in some asymmetric encryption methods such as RSA.
Check this out: IntX for working with LARGE integers. You may have to write your own power implementation, but since multiplication is supported, it shouldn't be that hard.
Edit by 280Z28: Another implementation that includes quick testing of Pow, ModPow, and primality is the BigInteger implementation (Code Project), which I have used in Project Euler projects in the past - although I am now working with .NET 4.0 and using System .Numerics.BigInteger .