Exponentiation modulaire rapide
Calculer des puissances avec pow(a, b, m)
Exponentiation modulaire rapide est une leçon Coding Interview Prep gratuite sur CoddyKit. Ceci est la leçon 2 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Coding Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Coding Interview Prep comprend 4 leçons au total.
Le problème des puissances
Vous devez souvent élever un nombre à une puissance gigantesque, le tout sous un modulo. Multiplier un facteur à la fois demanderait beaucoup trop d’étapes. ⚡
La méthode naïve est trop lente
Une boucle qui multiplie b fois s’exécute en O(b) étapes. Avec un exposant proche d’un milliard, elle dépasse la limite de temps avant même d’avoir terminé.
for _ in range(b): r = r * a % MODMettre au carré pour aller plus vite
L’astuce consiste à effectuer des élévations au carré : a puissance 8 est égale à ((a au carré) au carré) au carré. Chaque élévation au carré double l’exposant, ce qui permet d’atteindre de grandes puissances en peu d’étapes.
Lire l’exposant en binaire
Tout exposant est une somme de puissances de deux : c’est sa forme binaire. Vous ne multipliez donc que par les puissances de la base correspondant aux bits activés, en ignorant les autres.
# 13 = 1101 -> a^8 * a^4 * a^1Vérifier le bit de poids faible
Examinez b & 1 pour tester le bit de poids faible. S’il vaut 1, incorporez la base actuelle au résultat en cours avant de continuer.
if b & 1: result = result * base % MODDécaler et mettre au carré à chaque tour
Après chaque bit, mettez la base au carré et décalez l’exposant vers la droite d’une position. La boucle ne s’exécute qu’environ 30 à 60 fois pour toute entrée réaliste.
base = base * base % MOD
b >>= 1Assembler le tout
Initialisez result à 1, puis bouclez tant que l’exposant est positif. Cette idée d’exponentiation rapide est aussi appelée exponentiation binaire ou exponentiation par élévations au carré.
result = 1
while b > 0:
if b & 1: result = result*base%MOD
base = base*base%MOD
b >>= 1Une durée logarithmique
Comme chaque tour divise l’exposant par deux, le coût est de O(log b). Un milliard de multiplications devient ainsi environ trente multiplications, ce qui respecte largement toute limite.
Python vous fournit pow
Vous écrivez rarement la boucle vous-même : la fonction intégrée pow(a, b, m) de Python effectue pour vous une exponentiation modulaire rapide, à la vitesse du langage C.
print(pow(2, 100, MOD))Pourquoi ce sera bientôt utile
L’exponentiation rapide est le moteur de l’inverse modulaire de Fermat, que vous découvrirez ensuite. Maîtrisez-la maintenant et la division sous un modulo deviendra simple.
Surveiller d’abord la base
Réduisez la base avec base % MOD avant la boucle. Une base déjà supérieure au modulo ferait sinon grossir chaque étape d’élévation au carré.
base = a % MODVérification rapide
Quelle est la vitesse de l’exponentiation modulaire rapide ?
Récapitulatif
Vous pouvez maintenant élever des nombres à de très grands exposants en O(log b) en utilisant les carrés successifs et la lecture des bits. En Python, appelez simplement pow(a, b, m), puis continuez. 🚀
Questions Fréquemment Posées
La leçon « Exponentiation modulaire rapide » est-elle gratuite ?
Oui — le texte complet de « Exponentiation modulaire rapide » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Coding Interview Prep, passe à CoddyKit PRO. Le cours Coding Interview Prep comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Exponentiation modulaire rapide » ?
Calculer des puissances avec pow(a, b, m) Tu pratiques Coding Interview Prep avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer Coding Interview Prep ?
Aucune expérience préalable n'est requise. Coding Interview Prep sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 2 sur 4.
Combien de temps prend la leçon « Exponentiation modulaire rapide » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon Coding Interview Prep ?
Oui. Chaque leçon Coding Interview Prep inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- Calculer modulo un nombre premier
- Exponentiation modulaire rapide
- Inverse modulaire par Fermat
- nCr avec des factorielles précalculées