Mise en œuvre rapide de l'exponentiation

Question

Quelqu'un pourrait-il indiquer un site sur lequel je peux trouver un algorithme permettant de calculer efficacement l'exponentiation d'entiers pour les grandes puissances à l'aide de C #?

par exemple. Je veux calculer 2 ^ 60000 ou 3 ^ 12345

Answer 1

À moins que ce ne soit un devoir, vous ne voudrez probablement pas lancer votre propre implémentation d’exponentiation à précision arbitraire. Calculer de grands exposants du type que vous décrivez est compliqué - performances mises à part.

Je vous recommanderais d'utiliser l'une des bibliothèques d'arithmétique à précision arbitraire existantes, comme GMP. - dont la plupart ont des bibliothèques pour y accéder depuis C #.

F # prend en charge l'arithmétique en précision arbitraire à l'aide de la classe BigInt (à laquelle vous pouvez également accéder à partir de C # si vous importez l'assembly dans lequel elle se trouve). Cependant, je ne sais pas à quel point l’exponiation de BigInt est optimisée.

Si vous essayez simplement d’en apprendre davantage sur les algorithmes d’exponentiation efficaces, vous pouvez consulter le Square. Algorithme d’exponentiation -And-Multiply .

Answer 2

L’exponentiation d’entiers peut être calculée de manière efficace en utilisant une méthode appelée "Exponentiation par quadrature". lien .

Cette méthode peut également être utilisée pour calculer l’exponentiation modulaire link , utilisée dans certaines méthodes de cryptage asymétrique telles que RSA.

Answer 3

Découvrez ceci: IntX pour utiliser des entiers LARGE. Vous devrez peut-être écrire votre propre mise en oeuvre du pouvoir, mais puisque la multiplication est prise en charge, cela ne devrait pas être si difficile.

Modifier de 280Z28: une autre implémentation qui inclut les tests rapides de Pow, ModPow et de primalité est la suivante: BigInteger (Code Project), que j'avais déjà utilisé dans le passé pour résoudre des problèmes liés à Project Euler - bien que je travaille maintenant avec .NET 4.0 et que je l'utilise System.Numerics.BigInteger .