zadania z informatyki - Tworzenie algorytmów

W algorytmach szybkiego potęgowania można wykorzystać binarną reprezentację wykładnika dla obliczenia wartości x^k , gdzie k jest liczbą naturalną, k ≠ 0, zaś x jest liczbą rzeczywistą. Przyjmijmy, że binarnym rozwinięciem wykładnika k jest ciąg (݇k_nk_n–1k_n–2 ... k₂k₁k₀)₂.

Jedna z metod wyznaczania x^k polega na obliczaniu potęg liczby x dla wykładników o binarnych reprezentacjach:
݇k_n,
݇k_nk_n–1,
k_nk_n–1k_n–2,
…,
k_nk_n–1k_n–2 …݇k₁,
k_nk_n–1k_n–2 …݇k₁k₀,

Inaczej mówiąc, uwzględniamy coraz dłuższe fragmenty ciągu (݇k_nk_n–1k_n–2 ... k₂k₁k₀)₂. W pierwszym kroku przyjmujemy, że wynik jest równy x, gdyż k_n = 1. Znając wartość x do potęgi o binarnym zapisie (݇k_nk_n–1k_n–2 ... k_i)₂, możemy łatwo wyliczyć x do potęgi o binarnym zapisie (݇k_nk_n–1k_n–2 ... k_ik_i–1)₂: podnosimy dotychczasowy wynik do kwadratu (do czego wystarczy jedno mnożenie). Jeśli k_i–1 = 1, dodatkowo mnożymy uzyskany wynik przez x.

Przykład

Niech ݇ k = 13 = (1101)₂. Kolejne wyznaczane w naszym algorytmie potęgi to:


zaś liczba wykonanych mnożeń jest równa 5 (zauważ, że aby obliczyć x³, musisz najpierw obliczyć x², a aby obliczyć x², musisz wykonać jedno mnożenie: x² = x ⋅ x).