Exponenciación modular rápida
Calcule potencias con pow(a, b, m)
Exponenciación modular rápida es una lección gratuita de Coding Interview Prep en CoddyKit. Esta es la lección 2 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de Coding Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Coding Interview Prep incluye 4 lecciones en total.
El problema de las potencias
A menudo necesitará elevar un número a un exponente enorme, todo ello bajo un módulo. Multiplicar un factor cada vez requeriría demasiados pasos. ⚡
El método ingenuo es demasiado lento
Un bucle que multiplica b veces se ejecuta en O(b) pasos. Con un exponente cercano a mil millones, superaría el límite de tiempo antes de terminar.
for _ in range(b): r = r * a % MODEleve al cuadrado para avanzar más rápido
El truco consiste en elevar al cuadrado: a elevado a la 8 es igual a ((a al cuadrado) al cuadrado) al cuadrado. Cada elevación al cuadrado duplica el exponente, por lo que puede alcanzar potencias enormes en pocos pasos.
Lea el exponente en binario
Cada exponente es una suma de potencias de dos: su forma binaria. Por eso, solo multiplica las potencias de la base correspondientes a los bits activados y omite las demás.
# 13 = 1101 -> a^8 * a^4 * a^1Compruebe el bit menos significativo
Observe b & 1 para comprobar el bit menos significativo. Si es 1, incorpore la base actual al resultado acumulado antes de continuar.
if b & 1: result = result * base % MODDesplace y eleve al cuadrado en cada ronda
Después de cada bit, eleve la base al cuadrado y desplace el exponente un bit a la derecha. El bucle solo se ejecuta unas 30 a 60 veces para cualquier entrada realista.
base = base * base % MOD
b >>= 1Reúna todas las piezas
Comience el resultado en 1 y repita mientras el exponente sea positivo. Toda esta idea de exponenciación rápida también se denomina binaria o exponenciación por cuadrados sucesivos.
result = 1
while b > 0:
if b & 1: result = result*base%MOD
base = base*base%MOD
b >>= 1Se ejecuta en tiempo logarítmico
Como cada ronda divide el exponente entre dos, el coste es O(log b). Así, mil millones de multiplicaciones se convierten en aproximadamente treinta, muy por debajo de cualquier límite.
Python le ofrece pow
Rara vez tendrá que escribir el bucle usted mismo: la función integrada pow(a, b, m) de Python realiza la exponenciación modular rápida a la velocidad del código C.
print(pow(2, 100, MOD))Por qué será importante pronto
La exponenciación rápida es la base del inverso modular mediante Fermat, que verá a continuación. Domínela ahora y la división bajo un módulo resultará sencilla.
Controle primero la base
Reduzca la base con base % MOD antes del bucle. De lo contrario, una base mayor que el módulo haría crecer cada paso de elevación al cuadrado.
base = a % MODComprobación rápida
¿Qué velocidad tiene la exponenciación modular rápida?
Resumen
Ahora puede elevar números a exponentes enormes en O(log b) mediante cuadrados sucesivos y la lectura de bits. En Python, basta con llamar a pow(a, b, m) y continuar. 🚀
Preguntas frecuentes
¿La lección «Exponenciación modular rápida» es gratis?
Sí — el texto completo de «Exponenciación modular rápida» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de Coding Interview Prep, actualiza a CoddyKit PRO. El curso de Coding Interview Prep incluye 4 lecciones en total.
¿Qué aprenderé en «Exponenciación modular rápida»?
Calcule potencias con pow(a, b, m) Practicas Coding Interview Prep con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar Coding Interview Prep?
No se requiere experiencia previa. Coding Interview Prep en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 2 de 4.
¿Cuánto tiempo toma la lección «Exponenciación modular rápida»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de Coding Interview Prep?
Sí. Cada lección de Coding Interview Prep incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.
Todas las lecciones de este curso
- Trabaje módulo un primo
- Exponenciación modular rápida
- Inverso modular mediante Fermat
- nCr con factoriales precalculados