Czego się nauczysz
Nauczysz się liczyć potęgę kolejnymi kwadratami podstawy: zamiast n mnożeń wystarczy ich około dwa razy tyle, ile cyfr ma wykładnik zapisany dwójkowo. Do tego reszta z dzielenia po każdym mnożeniu, dzięki której liczby nie rosną.
Po co ci to na maturze
Zadania o ostatnich cyfrach ogromnych potęg albo o resztach z dzielenia potęg wymagają liczenia, którego mnożenie po kolei nie skończy w rozsądnym czasie. Szybkie potęgowanie bywa też tematem zadań na analizę algorytmu.
Etapy lekcji
Spis lekcji
Teoria
5 rozdziałówNie zaczęte- 1.1Potęga przez mnożeniePętla mnoży wynik przez podstawę tyle razy, ile wynosi wykładnik, a wynik zaczyna od 1.
- 1.2Wykładnik zapisany dwójkowoKażdy wykładnik da się zapisać jako sumę liczb 1, 2, 4, 8 i dalszych, więc potęgę składasz z kilku kolejnych kwadratów.
- 1.3Szybkie potęgowanie w pętliPętla czyta cyfry dwójkowe wykładnika od prawej, przy jedynce mnoży wynik przez podstawę, a potem podnosi podstawę do kwadratu.
- 1.4Reszta po każdym mnożeniuGdy potrzebne są tylko ostatnie cyfry wyniku, po każdym mnożeniu zostawiasz samą końcówkę i liczby nigdy nie rosną.
- 1.5PodsumowanieNajważniejsze rzeczy z każdego rozdziału na jednej stronie, do szybkiej powtórki.