Clever Geek Handbook

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

+2


source to share


3 answers


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.

+13


source


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.

+2


source


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 .

0


source






More articles:


All Articles