Szybkie potęgowanie iteracyjnie

Szybkie potęgowanie - Algorytmy: zakres rozszerzony (Python)

Wersja iteracyjna czyta wykładnik bit po bicie od najmłodszego. 13 = 1101 (dwójkowo), więc 3^13 = 3^8 * 3^4 * 3^1. Zmienna `a` przechodzi przez kolejne kwadraty (3, 3^2, 3^4, 3^8), a do wyniku trafiają te, przy których bit wykładnika to 1.

def fast_power(a, n):
    result = 1
    while n > 0:
        if n % 2 == 1:
            result *= a
        a *= a
        n //= 2
        print("n =", n, "wynik =", result)
    return result


print("3^13 =", fast_power(3, 13))

Ładowanie interaktywnego edytora... Jeśli się nie pojawi, włącz JavaScript.

Wszystkie lekcje kursu Algorytmy: zakres rozszerzony·Zaloguj się, aby zapisać postęp na koncie.