Potęgowanie szybkie w języku Python

---

powrót

Wersja iteracyjna

Do wyjaśnienia działania algorytmu posłużę się przykładem: $$2^{25}$$

Przedstawimy wykładnik w postaci binarnej: $$25 = 11001_2$$ Zatem $$2^{25}=2^{11001_2}=2^{1\cdot 2^4+1\cdot 2^3+0\cdot 2^2+0\cdot 2^1+1\cdot 2^0}=2^{16+8+1}=2^{16}\cdot 2^8 \cdot 2^1 = 33 554 432$$ Aby uzyskać kolejne wartosci potęg $$2^1$$ $$2^2$$ $$2^4$$ $$2^8$$ $$2^{16}$$ wykorzystamy zapis:$$a = 2$$ $$a*=a$$

Jak zapewne zauważyłeś, złożoność czasowa jest zależna od liczby bitów wykładnika n, ktora wynosi $$\log n$$

#----------algorytm.edu.pl-------------
#wersja iteracyjna
def pot_szybkie(a, b): #potęgowanie szybkie a^b
    w = 1 # tu będziemy przechowywać wynik
    while b > 0:  
        if b%2: # jeśli b%2 == 1
            w*=a;
        a*=a
        b//=2 # ucinamy najmniej znaczący bit
    return w

#--------główna część programu----------
a, b = map(int, input("Podaj podstawę i wykładnik: ").split()) #podaj dwie liczby w jednym wierszu
print(pot_szybkie(a, b))

Wersja rekurencyjna

Ten sam przykład rozwiążmy techniką rekurencyjną.

$$2^{25}=2\cdot 2^{24} = 2\cdot \left(2^{12}\right )^2 = 2\cdot \left(\left(2^6\right)^2\right )^2 =$$ $$2\cdot \left(\left(\left(2^3\right)^2\right)^2\right )^2 = 2\cdot \left(\left(\left(2\cdot 2^2\right)^2\right)^2\right )^2$$

#----------algorytm.edu.pl-------------
#wersja iteracyjna
def pot_szybkie(a, b): #potęgowanie szybkie a^b
   if b == 0: return 1
   if b%2: # jeśli b%2 == 1
        return a*pot_szybkie(a, b-1) #odłączamy jedno 'a', aby 'b' było parzyste
   w = pot_szybkie(a, b//2)
   return w*w

#--------główna część programu----------
a, b = map(int, input("Podaj podstawę i wykładnik: ").split()) #podaj dwie liczby w jednym wierszu
print(pot_szybkie(a, b))