Est-ce que quelqu'un pourrait me signaler un site où je peux trouver un algorithme pour calculer efficacement l'exponentiation d'entiers en grandes puissances en utilisant C#?Implémentation d'exponentiation rapide
par ex. Je veux calculer 2^60000 ou 3^12345
À moins que ce soit un devoir, vous ne voulez probablement pas lancer votre propre implémentation de l'exponentiation de précision arbitraire. Calculer de grands exposants du type que vous décrivez est compliqué - performance mise à part.
Je recommanderais d'utiliser l'un des existing arbitrary precision arithmetic libraries, like GMP - dont la plupart ont des bibliothèques pour y accéder à partir de C#. F # a la prise en charge de l'arithmétique de 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 comment BigInt exponentiation est optimisée.
Si vous essayez simplement d'en savoir plus sur les algorithmes efficaces pour l'exponentiation, vous pouvez vous intéresser à l'algorithme Square-And-Multiply pour l'exponentiation.
Check out out: IntX pour travailler avec des entiers LARGE. Vous devrez peut-être écrire votre propre implémentation de puissance, mais comme la multiplication est supportée, cela ne devrait pas être si difficile.
Édition par 280Z28: Une autre implémentation qui inclut le test rapide Pow, ModPow et la primalité est cette implémentation BigInteger (Projet de code), que j'ai déjà utilisée sur des problèmes Project Euler - même si je travaille maintenant avec .NET 4.0 et utiliser son implémentation System.Numerics.BigInteger.
Je conseillerais d'utiliser une bibliothèque plus mature que IntX si les résultats des calculs sont importants. Ecrire une bibliothèque correcte pour une précision arbitraire est plus difficile qu'elle n'en a l'air - et beaucoup de petits projets n'ont pas encore eu l'occasion de détecter et de résoudre les types de problèmes qui affectent la plupart des implémentations. – LBushkin
L'exponentiation entière peut être efficacement calculée en utilisant une méthode connue sous le nom de "Exponentiation by squaring" link.
Cette méthode peut également être utilisée pour calculer l'exponentiation modulaire link, qui est utilisée dans certaines méthodes de chiffrement asymétrique comme RSA.
Excellente réponse. –
+1. Très intéressant. – RichardOD