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
A:
Use the Math.Pow method:
double result = Math.Pow(2, 600000);
UPDATE: Didnt read the question properly - this wont work as the result is large than the maximum value of a double.
Kragen
2009-10-27 14:51:40
Try putting that in your Visual Studio Immedidate Window
RichardOD
2009-10-27 14:53:32
The decimal type covers the range up to approx. 10^28 which is obviously not suitable for the above stated requirements
Manu
2009-10-27 14:54:29
`Infinity` ....
Tinister
2009-10-27 14:54:43
+10
A:
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.
LBushkin
2009-10-27 14:56:29
A:
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.
Manu
2009-10-27 14:57:31
I would advise using a more mature library than IntX if the results of the computations are at all important. Writing a correct library for arbitrary precision is harder than it looks - and many of the smaller projects out there have not yet had an opportunity to detect and resolve the types of problems that plague most implementations.
LBushkin
2009-10-27 15:02:41