Algorytm szybkiego potęgowania

Z Wikipedii

Algorytm szybkiego potęgowania – metoda pozwalająca na szybkie obliczenie potęgi o wykładniku naturalnym. Metoda ta wykorzystuje pośrednio dwójkową reprezentację wykładnika potęgi, a jej złożoność, wyrażona jako liczba wykonywanych mnożeń, wynosi $Θ(log n)$ , gdzie n oznacza wykładnik obliczanej potęgi.

Szybkie podnoszenie do potęgi w praktyce stosuje się do liczenia reszty z dzielenia potęgi przez ustaloną liczbę. Używa się go np. w algorytmach szyfru RSA.

[edytuj] Wprowadzenie

Potęgowanie definiuje się za pomocą mnożenia

$\begin{matrix} x^k = x \cdot x^{k-1} = & \underbrace{x \cdot x \cdot x \cdot \ldots \cdot x }\\ & {}^k \end{matrix}$ ,

co daje łącznie $k - 1$ mnożeń.

Dla dużego $k$ liczba wymaganych operacji może być bardzo duża. Jeśli $k$ ma $j$ cyfr, liczba operacji byłaby wykładnicza wobec $j$ .

[edytuj] Algorytm

Algorytm szybkiego potęgowania jest konsekwencją obserwacji, że aby obliczyć wartość $a b$ wystarczy znać $a [b / 2]$ ( $[\cdot]$ oznacza część całkowitą), a następnie wykonać jedno lub dwa mnożenia. Np. aby obliczyć $5175$ wystarczy znać wartość $x = 5 87$ , a następnie policzyć $y = x 2 = 5 174$ i wynik wynosi $=y\cdot 5$ . W ten sposób aby przejść od $587$ do $5175$ wystarczy wykonać 2 mnożenia zamiast 88, jak wynikałoby to z przytoczonej wyżej definicji.

[edytuj] Pseudokod

Dostajemy z powyższej obserwacji rekurencyjną funkcję szybkiego podnoszenia do potęgi.

funkcja potęga(x, n)
    jeżeli n = 0
        zwróć 1
    jeżeli n jest nieparzysta
        zwróć x · potęga(x, n - 1)
    w przeciwnym przypadku
        a = potęga(x, n/2)
    zwróć a²

Ten sam algorytm w wersji iteracyjnej wygląda następująco:

funkcja potęga(x, n)
    w = x
    dla każdej, poczynając od drugiej, cyfry c rozwinięcia dwójkowego n
        w = w²
        jeżeli c jest jedynką
            w = w · x
    zwróć w

Nowa StrefaWWW

Po pierwsze chcielibyśmy przeprosić za brak aktualizacji strony. Jest on związany z tworzeniem nowej wersji naszej strony i rozbudową wortalu. Na ten czas mamy dla Was niespodziankę- pierwszy screenshot nowej wersji naszej strony. Mamy nadzieję, że nowa wersja się bardziej spodoba.

Co nowego w GNOME 2.20?

Na blogu tłumacza środowiska GNOME, Tomasza Dominikowskiego, pojawiła się lista nowości wprowadzonych w GNOME w wersji 2.20. Prezentujemy ją na naszych łamach.

Nowe wersje Firefoksa

Mozilla poinformowała o wydaniu nowych wersji swojej flagowej przeglądarki. Są to wersje, które zostały zapowiedziane m.in. w naszym serwisie. Zostały one oznaczone numerami: 2.0.0.4 oraz 1.5.0.12. Trzeba pamiętać, że wersja 1.5.0.12 jest ostatnią wersją z gałęzi 1.x. Podczas kilku następnych tygodni użytkownicy tej wersji zostaną poinformowaniu o możliwości aktualizacji do wersji 2.

1 mln blogów w Wordpress.com

Tak... To już ponad milion blogów opartych na popularnym skrypcie Wordpress utrzymuje serwis Wordpress.com. Taki prezent zrobili użytkownicy im twórcom na czwarte urodziny serwisu. Obecnie w serwisie założonych jest 1 022 129 blogów.

Nowy Firefox?

W Mozilla Developer Center pojawiła się informacja, która sugeruje że pojawią się dwie nowe wersje przeglądarki Mozilla Firefox z gałęzi 2.x i 1.x. Od połowy maja gałąź 1.x nie powinna być rozwijana, jednakże najnowsza wersja - 1.5.0.12 zostanie wydana. Będzie to ostatnia edycja starszej wersji tej przeglądarki.

tutaj muzykunia na p domeny moda wyposa�enie domu Dreamgirl Gorset Dreamgirl Gorset objawy ciąży humor angielski lublin

gry.kompedium.net

Algorytm szybkiego potęgowania

Z Wikipedii

[edytuj] Wprowadzenie

[edytuj] Algorytm

[edytuj] Pseudokod