Schnelle modulare Exponentiation
Berechnen Sie Potenzen mit pow(a, b, m)
Schnelle modulare Exponentiation ist eine kostenlose Coding Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 2 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des Coding Interview Prep-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Das Potenzproblem
Oft müssen Sie eine Zahl mit einem riesigen Exponenten potenzieren, und zwar vollständig unter einem Modulo. Jeden Faktor einzeln zu multiplizieren würde viel zu viele Schritte erfordern. ⚡
Naiv ist zu langsam
Eine Schleife, die b-mal multipliziert, benötigt O(b) Schritte. Bei einem Exponenten nahe einer Milliarde überschreitet das Zeitlimit, bevor die Berechnung abgeschlossen ist.
for _ in range(b): r = r * a % MODDurch Quadrieren schneller vorankommen
Der Trick ist das Quadrieren: a hoch 8 entspricht ((a zum Quadrat) zum Quadrat) zum Quadrat. Durch jedes Quadrieren verdoppelt sich der Exponent, sodass Sie große Potenzen in wenigen Schritten erreichen.
Den Exponenten binär lesen
Jeder Exponent ist eine Summe von Zweierpotenzen, also seine Binärdarstellung. Deshalb multiplizieren Sie nur mit den Basispotenzen, deren Bit gesetzt ist, und überspringen den Rest.
# 13 = 1101 -> a^8 * a^4 * a^1Das niedrigste Bit prüfen
Prüfen Sie mit b & 1 das niedrigste Bit. Wenn es 1 ist, übernehmen Sie die aktuelle Basis in das bisherige Ergebnis, bevor Sie fortfahren.
if b & 1: result = result * base % MODIn jeder Runde verschieben und quadrieren
Nach jedem Bit quadrieren Sie die Basis und verschieben den Exponenten um eins nach rechts. Für jede realistische Eingabe läuft die Schleife nur etwa 30 bis 60 Mal.
base = base * base % MOD
b >>= 1Alles zusammenfügen
Setzen Sie result zunächst auf 1 und wiederholen Sie die Schleife, solange der Exponent positiv ist. Diese Idee der schnellen Exponentiation wird auch binäre Exponentiation oder Exponentiation durch Quadrieren genannt.
result = 1
while b > 0:
if b & 1: result = result*base%MOD
base = base*base%MOD
b >>= 1Die Laufzeit ist logarithmisch
Da sich der Exponent in jeder Runde halbiert, beträgt die Laufzeit O(log b). So werden aus einer Milliarde Multiplikationen ungefähr dreißig – weit innerhalb jedes Zeitlimits.
Python stellt Ihnen pow bereit
Sie müssen die Schleife nur selten selbst schreiben: Pythons eingebaute Funktion pow(a, b, m) führt die schnelle modulare Exponentiation mit der Geschwindigkeit von reinem C-Code für Sie aus.
print(pow(2, 100, MOD))Warum das gleich wichtig wird
Schnelle Potenzierung ist die Grundlage für das modulare Inverse nach Fermat, das Sie als Nächstes kennenlernen. Wenn Sie sie jetzt beherrschen, wird Division unter einem Modulo einfach.
Achten Sie zuerst auf die Basis
Reduzieren Sie die Basis mit base % MOD, bevor die Schleife beginnt. Eine Basis, die bereits größer als der Modulus ist, würde sonst jeden Quadrierungsschritt unnötig vergrößern.
base = a % MODSchnelltest
Wie schnell ist die schnelle modulare Exponentiation?
Rückblick
Sie können Zahlen nun durch Quadrieren und Auslesen der Bits in O(log b) mit riesigen Exponenten potenzieren. In Python rufen Sie einfach pow(a, b, m) auf und machen weiter. 🚀
Häufig gestellte Fragen
Ist die Lektion „Schnelle modulare Exponentiation“ kostenlos?
Ja — der vollständige Text von „Schnelle modulare Exponentiation“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Coding Interview Prep-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Schnelle modulare Exponentiation“?
Berechnen Sie Potenzen mit pow(a, b, m) Du übst Coding Interview Prep mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um Coding Interview Prep zu starten?
Keine Vorkenntnisse erforderlich. Coding Interview Prep auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 2 von 4.
Wie lange dauert die Lektion „Schnelle modulare Exponentiation“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser Coding Interview Prep-Lektion Code schreiben und ausführen?
Ja. Jede Coding Interview Prep-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- Rechnen modulo einer Primzahl
- Schnelle modulare Exponentiation
- Modulares Inverses mit Fermat
- nCr mit vorberechneten Fakultäten