Algorytmy na liczbach
Wstęp do działu
Masz już warsztat: zmienne, warunki, pętle, funkcje. Czas ruszyć na pierwszy prawdziwy poligon algorytmiki — liczby. Nie dlatego, że informatycy kochają arytmetykę. Dlatego, że na liczbach najlepiej widać istotę rzemiosła: ten sam problem można rozwiązać topornie albo pięknie, w milionie kroków albo w dwudziestu — i różnica nie siedzi w komputerze, tylko w pomyśle.
Po drodze spotkasz algorytmy z historią dłuższą niż jakakolwiek maszyna: przepis Euklidesa sprzed 2300 lat (wciąż w codziennym użyciu — bije go mało który wynalazek), sito Eratostenesa, które przetrwało od starożytnej Aleksandrii do współczesnych bibliotek kryptograficznych, i schemat Hornera, który — jak zobaczysz — potajemnie liczyłeś już w dziale o systemach dwójkowych. A na końcu tej drogi czeka niespodzianka: to właśnie „zabawy liczbami" — pierwszość, rozkład na czynniki, wielkie potęgi — strzegą dziś Twoich haseł i przelewów. Dział 5 pokaże jak; ten dział da Ci narzędzia.
Mapa pojęć działu
ALGORYTMY NA LICZBACH
|
┌──────────────┬─────────┴─────────┬──────────────────┐
pierwszość NWD i NWW ciągi [R] przyspieszacze
(dzielniki (Euklides: (Fibonacci: sito Eratostenesa
tylko do √n) odejmowanie, iteracyjnie schemat Hornera
reszta, i rekurencyjnie) szybkie potęgowanie
rekurencja) |
| wspólny sekret:
KOSZT ZALEŻY OD POMYSŁU nie licz tego samego
(nie od gigaherców) dwa razy
Jednostki w tym dziale
- 4.1 Czy liczba jest pierwsza? — test dzielników i sprytne obcięcie
- 4.2 NWD, NWW i ułamki — najstarszy algorytm świata
- 4.3 Ciągi: iteracyjnie i rekurencyjnie — Fibonacci na dwa sposoby
- 4.4 Sito Eratostenesa i rozkład na czynniki (rozszerzenie)
- 4.5 Schemat Hornera — wielomiany bez wysiłku (rozszerzenie)
- 4.6 Szybkie potęgowanie (rozszerzenie)