3.2 Szybkie potęgowanie

Matura pokazowa marzec 2022 - Matura z informatyki: arkusze krok po kroku (Python)

Zadanie 3.2 (4 pkt, na kartce): algorytm liczący a^x mod M w O(log x) mnożeniach. Pomysł: a^x rozkłada się według zapisu dwójkowego x, np. a^13 = a^8 · a^4 · a^1, bo 13 = 1101₂. Kolejne kwadraty a, a², a⁴, a⁸, ... daje podnoszenie poprzedniego do kwadratu, a wynik mnoży się przez kwadrat tam, gdzie bit x jest jedynką (ostatni bit to `x % 2`, następne po `x // 2`). Pętla obraca się tyle razy, ile cyfr ma x w systemie dwójkowym. Zasady oceniania przyjmują też wersję rekurencyjną: a^x = (a^(x/2))² dla parzystego x i a · (a^((x-1)/2))² dla nieparzystego. Program porównuje liczbę mnożeń z wersją wolną.

def power(a, x, M):
    global steps
    b = 1 % M
    z = a % M  # kolejne kwadraty: a, a^2, a^4, a^8, ... (modulo M)
    while x > 0:
        if x % 2 == 1:  # bit x równy 1: mnożymy wynik przez bieżący kwadrat
            b = b * z % M
        z = z * z % M
        x = x // 2
        steps = steps + 1
    return b


steps = 0
print(power(3, 1000, 1000003), "obrotów pętli:", steps)
print(power(2, 5, 7), power(3, 3, 11), power(10, 2, 13), power(9, 2, 80))

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

Wszystkie lekcje kursu Matura z informatyki: arkusze krok po kroku·Zaloguj się, aby zapisać postęp na koncie.