Potęgowanie to dość podstawowa, a jednocześnie przydatna operacja w matematyce. Jednak wykonując je według definicji, możemy nie dać rady zrobić tego szybko, szczególnie gdy podnosimy liczby do wysokich potęg. Mimo to jest na to sposób, jak można potęgi obliczać szybko, i to na tyle prostym algorytmem, że jest zwykle jednym z pierwszych, które poznajemy przy nauce programowania. Opowiedzmy sobie o nim, przetestujmy, a także sprawdźmy, czy naprawdę jest taki szybki.

Obliczanie największego wspólnego dzielnika dwóch liczb to prawdopodobnie jeden z pierwszych algorytmów, które poznajemy podczas swojej edukacji. Zarazem jest to też bardzo proste do zapamiętania. Omówmy sobie to klasyczne podejście, a także różne inne podejścia.

W poprzednim wpisie napisałem nieco o liczbach binarnych, i że komputery w tej formie trzymają dosłownie wszystko. Jednak ktoś, kto nigdy komputera nie widział na oczy, mógłby pomyśleć, że w środku takiej maszyny coś trzyma jedynki i zera. A jak już wspomniałem o spojrzeniu w pamięć, gdzie liczby przelatują jak w Matriksie, to jeszcze ktoś, kto jeździł koleją w Polsce w czasach sprzed wszechobecnych elektronicznych tablic, mógłby oczyma wyobraźni zobaczyć taki mechanizm, który w każdej komórce pamięci obraca się i wyświetla albo 0, albo 1, albo pustkę, a może nawet i jakiś napis typu „WARSZAWA ZACH. przez KOLUSZKI, Opóźnienie 180 min”. Oczywiście tak nie jest, nikt nie chciałby mieć w komputerze takich opóźnień ani żeby jego dane były dostarczane przez Koluszki. Takiego sposobu zapisu danych też nie, bo może i by działał, ale zbyt efektywnym raczej by nie był. Ale wróćmy do rzeczy. To, jak komputery zapisują liczby, możemy rozpatrzeć na dwa sposoby. Fizyczny (czyli jak to w świecie fizycznym się dzieje) i logiczny (czyli jak to jest interpretowane).

Zapewne wiecie bądź jakoś domyśliliście się po tytule, że komputery trzymają wszystkie informacje w postaci cyfr. I to nie takich zwykłych od 0 do 9 dobrze znanych nam na co dzień. Wszystko to, co znajduje się w komputerach, jest opisane zaledwie dwoma cyframi: 0 i 1. Dokładnie tyle wystarczy, aby opisać dosłownie wszystko — liczby, zdjęcia, muzykę, filmy, programy, teksty… Gdybyśmy zajrzeli w pamięć komputera tak, żeby zobaczyć w niej surowy zapis danych, ujrzelibyśmy widok zbliżony do tego z filmu Matrix — deszcz zer i jedynek. Pochylmy się jednak nad tym, dlaczego tak jest? Po co? Skąd to się wzięło, jak to ogarnąć i jakie to ma niesamowite właściwości?