Snelle modulaire machtsverheffing
Machten berekenen met pow(a, b, m)
Snelle modulaire machtsverheffing is een gratis Competitive Programming Academy-les op CoddyKit. Dit is les 2 van 4. Je kunt de volledige les hieronder gratis lezen en daarna in de browser praktisch oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is. Deze les maakt deel uit van het leertraject Competitive Programming Academy. Je voortgang wordt gesynchroniseerd op het web en in de CoddyKit-app. De cursus Competitive Programming Academy bevat in totaal 4 lessen.
Het machtsprobleem
Vaak moet je een getal tot een enorme exponent verheffen, allemaal onder een modulo. Elke factor afzonderlijk vermenigvuldigen zou veel te veel stappen kosten. ⚡
Naïef is te traag
Een lus die b keer vermenigvuldigt, werkt in O(b) stappen. Met een exponent van bijna een miljard overschrijdt dat de tijdslimiet al voordat de berekening klaar is.
for _ in range(b): r = r * a % MODKwadrateren voor meer snelheid
De truc is kwadrateren: a tot de achtste macht is gelijk aan ((a in het kwadraat) in het kwadraat) in het kwadraat. Elke kwadratering verdubbelt de exponent, waardoor je in weinig stappen enorme machten bereikt.
Lees de exponent binair
Elke exponent is een som van machten van twee, oftewel zijn binaire vorm. Daarom vermenigvuldig je alleen met de basismachten waarvan de bit is ingesteld en sla je de rest over.
# 13 = 1101 -> a^8 * a^4 * a^1Controleer de laagste bit
Bekijk b & 1 om de laagste bit te testen. Als die 1 is, neem je de huidige basis op in je tussenresultaat voordat je verdergaat.
if b & 1: result = result * base % MODVerschuif en kwadrateer elke ronde
Na elke bit kwadrateer je de basis en verschuif je de exponent één positie naar rechts. Voor elke realistische invoer loopt de lus maar ongeveer 30 tot 60 keer.
base = base * base % MOD
b >>= 1Alles samenvoegen
Begin met result op 1 en blijf daarna lussen zolang de exponent positief is. Dit hele idee van snelle machtsverheffing heet ook binaire machtsverheffing of machtsverheffing door kwadrateren.
result = 1
while b > 0:
if b & 1: result = result*base%MOD
base = base*base%MOD
b >>= 1Het werkt in logaritmische tijd
Omdat de exponent in elke ronde wordt gehalveerd, zijn de kosten O(log b). Zo veranderen een miljard vermenigvuldigingen in ongeveer dertig, ruim binnen elke limiet.
Python geeft je pow
Je schrijft de lus bijna nooit zelf: de ingebouwde functie pow(a, b, m) van Python voert de snelle modulaire machtsverheffing voor je uit met de snelheid van pure C.
print(pow(2, 100, MOD))Waarom dit straks belangrijk is
Snelle machtsverheffing vormt de basis voor de modulaire inverse volgens Fermat, die je hierna tegenkomt. Beheers dit nu en delen onder een modulo wordt eenvoudig.
Let eerst op de basis
Verklein de basis met base % MOD voordat de lus begint. Een basis die al groter is dan de modulus zou anders elke kwadrateringsstap groter maken.
base = a % MODKorte controle
Hoe snel is snelle modulaire machtsverheffing?
Samenvatting
Je kunt getallen nu tot enorme exponenten verheffen in O(log b) door te kwadrateren en bits te lezen. In Python roep je gewoon pow(a, b, m) aan en ga je verder. 🚀
Leer Python met een AI-tutor — gratis
Schrijf echte code en voer die uit in je browser, krijg direct hulp van een AI-tutor die 24/7 beschikbaar is en ga verder waar je gebleven bent op het web of in de app.
- Cursussen
- 30
- Lessen
- 120
Veelgestelde vragen
Is de les “Snelle modulaire machtsverheffing” gratis?
Ja — de volledige tekst van “Snelle modulaire machtsverheffing” kun je hier gratis op het web lezen. Als je interactief wilt oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is, en de rest van de cursus Competitive Programming Academy wilt ontgrendelen, kun je upgraden naar CoddyKit PRO. De cursus Competitive Programming Academy bevat in totaal 4 lessen.
Wat leer ik in “Snelle modulaire machtsverheffing”?
Machten berekenen met pow(a, b, m) Je oefent met Competitive Programming Academy door code rechtstreeks in de browser uit te voeren. Een AI-begeleider die 24/7 beschikbaar is beantwoordt je vragen terwijl je de les doorwerkt.
Heb ik ervaring nodig om met Competitive Programming Academy te beginnen?
Ervaring vooraf is niet nodig. Competitive Programming Academy op CoddyKit is opgebouwd voor beginners tot gevorderden, zodat je hier of bij het begin kunt starten en in je eigen tempo kunt leren. Dit is les 2 van 4.
Hoe lang duurt de les “Snelle modulaire machtsverheffing”?
De meeste lessen van CoddyKit duren ongeveer 5–10 minuten. Elke les is kort en interactief, zodat je gestaag vooruitgaat en op het web en in de app precies verdergaat waar je was gebleven.
Kan ik code schrijven en uitvoeren in deze les over Competitive Programming Academy?
Ja. Elke les over Competitive Programming Academy bevat een ingebouwde code-editor, zodat je rechtstreeks in je browser echte code kunt schrijven en uitvoeren en direct feedback van AI krijgt — lokale installatie is niet nodig.
Alle lessen in deze cursus
- Rekenen modulo een priemgetal
- Snelle modulaire machtsverheffing
- Modulair inverse via Fermat
- nCr met vooraf berekende faculteiten