Implementación rápida de exponenciación

Question

¿Podría alguien señalar un sitio donde pueda encontrar un algoritmo para calcular eficientemente la exponenciación de enteros a grandes potencias usando C #?

por ejemplo. Quiero calcular 2 ^ 60000 o 3 ^ 12345

Answer 1

A menos que esto sea tarea, probablemente no desee lanzar su propia implementación de exponenciación de precisión arbitraria. Calcular grandes exponentes del tipo que describe es complicado, aparte del rendimiento.

Recomendaría usar una de las bibliotecas aritméticas de precisión arbitraria existentes, como GMP - la mayoría de las cuales tienen bibliotecas para acceder a ellas desde C #.

F # admite la aritmética de precisión arbitraria utilizando la clase BigInt (a la que también puede acceder desde C # si importa el ensamblaje en el que se encuentra). Sin embargo, no sé cuán optimizada es la exponenciación de BigInt.

Si simplemente está tratando de aprender acerca de algoritmos eficientes para la exponenciación, es posible que desee examinar el Square -Y Multiplicar algoritmo para exponenciación.

Answer 2

La exponenciación de enteros se puede calcular de manera efectiva utilizando un método conocido como "Exponenciación por cuadratura" enlace .

Este método también se puede utilizar para calcular la exponenciación modular enlace , que se utiliza en algunos métodos de encriptación asimétrica como RSA.

Answer 3

Mira esto: IntX para trabajar con enteros GRANDES. Puede que tenga que escribir su propia implementación de poder, pero como se admite la multiplicación, esto no debería ser tan difícil.

Editar por 280Z28: Otra implementación que incluye pruebas rápidas de Pow, ModPow y primality es esta Implementación BigInteger (Proyecto de código), que he usado en problemas del Proyecto Euler en el pasado, aunque ahora trabajo con .NET 4.0 y uso su Implementación de System.Numerics.BigInteger .