implementação rápida exponenciação

Question

Alguém poderia apontar um site onde eu posso encontrar um algoritmo para exponenciação inteiro de forma eficiente calcular a grandes potências usando C #?

por exemplo. Eu quero calcular 2 ^ 60000 ou 3 ^ 12345

Answer 1

A menos que esta é a lição de casa, você provavelmente não desejar construir sua própria implementação de exponenciação precisão arbitrária. Calculando grandes expoentes do tipo que você descreve é ??complicado -. Desempenho de lado

Eu recomendaria usando um dos bibliotecas bignum existentes, como GMP - a maioria dos quais têm bibliotecas para acessá-los a partir de C #.

F # tem suporte para bignum usando a classe BigInt (que você pode também acesso a partir de C # se você importar a montagem é in). No entanto, eu não sei como otimizado exponenciação BigInt é.

Se você está simplesmente tentando aprender sobre algoritmos eficientes para exponenciação, você pode querer olhar para o Praça -e-Multiply algoritmo para exponenciação.

Answer 2

Integer exponenciação pode efetivamente ser calculado usando um método conhecido como "exponenciação por quadratura" ligação .

Este método também pode ser usado para calcular a modular exponenciação ligação , que é usado em alguns métodos de criptografia assimétrica, como RSA.

Answer 3

Veja isto: IntX para trabalhar com números inteiros grandes. Você pode ter que escrever sua própria implementação do poder, mas desde que a multiplicação é suportado, este não deve ser tão difícil.

Editar por 280Z28: Outra implementação que inclui Pow rápido, ModPow, e teste de primalidade é este BigInteger implementação (Code Project), que eu usei em problemas de projeto Euler no passado - embora eu agora trabalho com .NET 4.0 e usar sua implementação System.Numerics.BigInteger .