Algoritam brzog stepenovanja — objašnjenje i primeri

Brzo stepenovanje (exponentiation by squaring) je efikasan algoritam za računanje vrednosti Xⁿ, odnosno broja X stepenovanog na eksponent n. Umesto n množenja, potrebno je samo oko log₂ n množenja.

Naivan pristup

Rezultat se na početku postavi na 1, a zatim se u petlji množi brojem X ukupno n puta. Pristup je jednostavan, ali ima složenost O(n) i postaje prespor za velike eksponente (na primer n = 10¹⁸).

#include <iostream>
using namespace std;

// Naivan pristup: broj se množi sam sobom onoliko puta koliko iznosi stepen
long long naivnoStepenovanje(long long broj, long long stepen) {
    long long rezultat = 1;

    for (long long i = 0; i < stepen; ++i) {
        rezultat *= broj;
    }

    return rezultat;
}

int main() {
    cout << naivnoStepenovanje(2, 10) << endl; // Ispisuje: 1024
    return 0;
}

Ključna ideja algoritma

Kada je eksponent paran, može se podeliti na pola:

X^n = X^(n/2) · X^(n/2) = (X^(n/2))^2

Vrednost X^n/2 računamo samo jednom i kvadriramo je. Tako se eksponent u svakom koraku prepolovi, pa je broj koraka oko log₂ n.

Shematski prikaz algoritma brzog stepenovanja - deljenje eksponenta i kvadriranje rezultata

Slika 1: Ilustracija algoritma brzog stepenovanja za n = 16

Na slici 1 prikazan je primer za n = 16: X¹⁶ = X⁸ · X⁸, zatim X⁸ = X⁴ · X⁴ i tako dalje, do X¹. Nivoi su označeni bojama:

plavo – prvi nivo, gde se X¹⁶ deli na X⁸ · X⁸,
zeleno – drugi nivo, gde se X⁸ deli na X⁴ · X⁴,
crveno – treći nivo, gde se X⁴ deli na X² · X², a zatim na X.

Svaki nivo odgovara jednom prepolovljavanju eksponenta, pa je broj nivoa log₂ 16 = 4. Pošto se isti podproblem računa samo jednom, ukupno su potrebna 4 množenja umesto 15.

Neparan eksponent

Neparan eksponent zapisujemo kao n = 2k + 1. Tada važi:

X^(2k+1) = X · X^(2k) = X · (X^k)^2

Dakle, kao i kod parnog eksponenta izračunamo X^k i kvadriramo ga, a zatim rezultat pomnožimo još jednom sa X. Pošto je k = (n − 1) / 2, a celobrojno deljenje daje n / 2 = (n − 1) / 2 za neparno n, isti rekurzivni poziv važi u oba slučaja.

Rekurzivna implementacija

#include <iostream>
using namespace std;

// Rekurzivno brzo stepenovanje (stepen >= 0)
long long brzoStepenovanje(long long broj, long long stepen) {
    // Bazni slučaj: svaki broj na nulti stepen je 1
    if (stepen == 0)
        return 1;

    // Rekurzivno računamo X^(n/2) samo JEDNOM
    long long polovina = brzoStepenovanje(broj, stepen / 2);

    if (stepen % 2 == 0)
        return polovina * polovina;          // paran:   X^n = (X^(n/2))^2
    else
        return broj * polovina * polovina;   // neparan: X^n = X * (X^(n/2))^2
}

int main() {
    cout << "2^16 = " << brzoStepenovanje(2, 16) << endl;  // 65536
    cout << "3^13 = " << brzoStepenovanje(3, 13) << endl;  // 1594323
    cout << "2^7  = " << brzoStepenovanje(2, 7) << endl;   // 128
    cout << "5^3  = " << brzoStepenovanje(5, 3) << endl;   // 125
    return 0;
}

Česta greška

Ako se napiše return brzoStepenovanje(broj, stepen / 2) * brzoStepenovanje(broj, stepen / 2);, ista vrednost se računa dva puta na svakom nivou i algoritam ponovo ima O(n) množenja. Rezultat rekurzivnog poziva treba sačuvati u promenljivoj i tek onda kvadrirati.

Primer: 3¹³

13 = 2·6 + 1  →  3^13 = 3 · (3^6)^2
 6 = 2·3      →  3^6  = (3^3)^2
 3 = 2·1 + 1  →  3^3  = 3 · (3^1)^2 = 27
                 3^6  = 27^2 = 729
                 3^13 = 3 · 729^2 = 3 · 531441 = 1594323

Rekurzija se spušta dok eksponent ne postane 0, kada se vraća osnovna vrednost 1, a zatim se rezultati sklapaju unazad.

Modularno brzo stepenovanje

U mnogim zadacima treba izračunati veliki stepen broja, ali je potreban samo ostatak pri deljenju sa nekim brojem m:

(X^n) mod m

Sam broj Xⁿ brzo prelazi opseg svakog celobrojnog tipa. Zato se ostatak uzima u svakom koraku, koristeći pravilo:

(a · b) mod m = ((a mod m) · (b mod m)) mod m

#include <iostream>
using namespace std;

// Rekurzivno računa (broj^stepen) % mod
long long modularnoStepenovanje(long long broj, long long stepen, long long mod) {
    if (stepen == 0)
        return 1 % mod;   // 1 % mod, da bi za mod = 1 rezultat bio 0

    long long polovina = modularnoStepenovanje(broj, stepen / 2, mod);

    // Kvadrat polovine, po modulu
    long long rezultat = (polovina * polovina) % mod;

    // Ako je stepen neparan, još jedno množenje sa X, po modulu
    if (stepen % 2 == 1)
        rezultat = (rezultat * (broj % mod)) % mod;

    return rezultat;
}

int main() {
    cout << "(7^13) % 1000 = " << modularnoStepenovanje(7, 13, 1000) << endl;
    cout << "(3^20) % 50 = " << modularnoStepenovanje(3, 20, 50) << endl;
    cout << "(2^30) % 17 = " << modularnoStepenovanje(2, 30, 17) << endl;
    return 0;
}

Program ispisuje:

(7^13) % 1000 = 407
(3^20) % 50 = 1
(2^30) % 17 = 13

Primer: (7¹³) mod 1000

7^1  mod 1000 = 7
7^3  mod 1000 = 7 · 7^2       = 343
7^6  mod 1000 = 343^2 = 117649 → 649
7^13 mod 1000 = 7 · 649^2 = 7 · 421201 → 7 · 201 = 1407 → 407

Svaki međurezultat ostaje manji od 1000, pa nema prekoračenja.

Iterativna verzija

Rekurzivna verzija jasno pokazuje princip prepolovljavanja, ali se u praksi često koristi iterativna verzija, koja ne troši prostor na steku. Ona koristi binarni zapis eksponenta: svaki bit određuje da li se odgovarajući stepen baze uključuje u rezultat.

Na primer, 13 = 1101₂ = 8 + 4 + 1, pa je:

X^13 = X^8 · X^4 · X^1

U petlji se baza kvadrira (X, X², X⁴, X⁸, ...), a eksponent deli sa 2, odnosno pomera udesno za jedan bit. Ako je poslednji bit eksponenta 1, rezultat se množi trenutnom bazom.

#include <iostream>
using namespace std;

// Iterativno brzo stepenovanje (stepen >= 0)
double brzoStepenovanjeIterativno(double baza, int stepen)
{
    double rezultat = 1.0;

    while (stepen > 0)
    {
        // Ako je poslednji bit eksponenta 1, uključujemo trenutnu bazu u rezultat
        if (stepen % 2 == 1)
            rezultat *= baza;

        // Baza postaje X^2, X^4, X^8, ... (vrednost za sledeći bit)
        baza *= baza;

        // Delimo eksponent sa 2: odbacujemo poslednji bit (pomeranje udesno)
        stepen /= 2;
    }

    return rezultat;
}

int main()
{
    double x;
    int n;

    cout << "Unesite bazu: ";
    cin >> x;

    cout << "Unesite stepen: ";
    cin >> n;

    cout << "Rezultat je: " << brzoStepenovanjeIterativno(x, n) << endl;

    return 0;
}

Koraci za n = 13

stepen	poslednji bit	baza	rezultat posle koraka
13	1	X	X
6	0	X²	X
3	1	X⁴	X⁵
1	1	X⁸	X¹³

Složenost je ista kao kod rekurzivne verzije, O(log n). Ova verzija radi samo za nenegativne eksponente; za negativan eksponent računa se 1 / X^|n|.

Iterativna modularna verzija

Iterativna verzija se lako prilagođava za računanje (Xⁿ) mod m: posle svakog množenja uzima se ostatak pri deljenju sa m. Ovo je verzija koja se najčešće koristi na takmičenjima.

#include <iostream>
using namespace std;

// Iterativno računa (baza^stepen) mod m
long long brzoStepenovanjeModularno(long long baza, long long stepen, long long mod)
{
    long long rezultat = 1 % mod;
    baza = baza % mod;   // baza u granicama modula

    while (stepen > 0)
    {
        // Ako je poslednji bit eksponenta 1, uključujemo bazu u rezultat
        if (stepen % 2 == 1)
            rezultat = (rezultat * baza) % mod;

        // Kvadriramo bazu i uzimamo ostatak
        baza = (baza * baza) % mod;

        // Prelazimo na sledeći bit eksponenta
        stepen /= 2;
    }

    return rezultat;
}

int main()
{
    long long x, n, m;

    cout << "Unesite bazu: ";
    cin >> x;

    cout << "Unesite stepen: ";
    cin >> n;

    cout << "Unesite mod: ";
    cin >> m;

    cout << "(" << x << "^" << n << ") mod " << m << " = "
         << brzoStepenovanjeModularno(x, n, m) << endl;

    return 0;
}

Objašnjenje

Posle svakog množenja uzima se ostatak, pa vrednosti ostaju manje od m.
Kada je poslednji bit eksponenta 1, trenutna baza se uključuje u rezultat.
Baza se kvadrira i ponovo svodi po modulu.
Eksponent se deli sa 2 u svakom prolazu petlje.

Granica za modul Proizvod dva broja manja od m mora da stane u long long. Za uobičajeni modul 10⁹ + 7 to važi, ali za modul veći od oko 3 · 10⁹ nastaje prekoračenje.

Primene

Kriptografija: u RSA algoritmu šifrovanje je izraz M^e mod n, a i Diffie–Hellman razmena ključeva zasniva se na modularnom stepenovanju.
Takmičarsko programiranje: mnogi zadaci traže rezultat po modulu 10⁹ + 7.
Teorija brojeva: modularni inverz (za prost modul), testovi prostosti, heš funkcije.

Primena: zadatak Mešalica

Tekst zadatka Mešalica nalazi se na strani sa kvalifikacijama, a kompletno rešenje na strani Mešalica — rešenje.

Niz 0, 1, 2, ..., n−1 treba izmešati m puta po istoj šemi. Ako bismo mešanje ponovili jedno po jedno, za m do 10¹⁸ program bi bio prespor. Jedno mešanje je permutacija, a m mešanja odgovara m-tom stepenu te permutacije. Zato se može primeniti isti algoritam brzog stepenovanja, samo umesto množenja brojeva slažemo permutacije.

#include <iostream>
#include <vector>

using namespace std;

// Slaganje dve permutacije: rezultat odgovara primeni a, pa zatim b.
// Na poziciju i dolazi element koji je posle a bio na poziciji b[i].
vector<int> kombinujPermutacije(const vector<int>& a, const vector<int>& b) {
    int n = a.size();
    vector<int> c(n);
    for (int i = 0; i < n; i++) {
        c[i] = a[b[i]];
    }
    return c;
}

// Brzo stepenovanje permutacije: perm primenjena m puta
vector<int> brzoStepenujPermutaciju(vector<int> perm, long long m) {
    int n = perm.size();
    vector<int> rezultat(n);
    for (int i = 0; i < n; i++)
        rezultat[i] = i;   // identička permutacija (0 mešanja)

    while (m > 0) {
        if (m % 2 == 1)
            rezultat = kombinujPermutacije(rezultat, perm);   // bit je 1: dodajemo trenutni stepen
        perm = kombinujPermutacije(perm, perm);              // perm^2, perm^4, perm^8, ...
        m /= 2;
    }

    return rezultat;
}

int main() {
    int n;
    long long m;
    cin >> n >> m;

    // mesanje[i] - element na poziciji i posle jednog mešanja niza 0 1 ... n-1
    vector<int> mesanje(n);
    for (int i = 0; i < n; i++)
        cin >> mesanje[i];

    vector<int> konacno = brzoStepenujPermutaciju(mesanje, m);

    for (int i = 0; i < n; i++) {
        if (i > 0) cout << " ";
        cout << konacno[i];
    }
    cout << endl;

    return 0;
}

Objašnjenje koda

kombinujPermutacije slaže dve permutacije u jednu koja odgovara njihovoj primeni redom.
brzoStepenujPermutaciju radi kao iterativno brzo stepenovanje: počinje od identičke permutacije (ekvivalent broja 1), a svaki bit broja m odlučuje da li se trenutni stepen uključuje u rezultat.
Složenost je O(n log m), što je dovoljno brzo i za m = 10¹⁸.

Program daje tačne izlaze za sva tri primera iz teksta zadatka. Ovaj primer pokazuje da se brzo stepenovanje može koristiti za svaku operaciju koja je asocijativna, a ne samo za množenje brojeva (na primer i za matrice).

Složenost

Naivno stepenovanje: O(n) množenja
Brzo stepenovanje (rekurzivno, iterativno, modularno): O(log n) množenja
Stepenovanje permutacije dužine k: O(k log n)

Prethodno
|<Kadaneov algoritam

Sledeće
Mapa učenja — Strukture podataka>|

Algoritam brzog stepenovanja — objašnjenje i primeri

Naivan pristup

Ključna ideja algoritma

Neparan eksponent

Rekurzivna implementacija

Primer: 313

Modularno brzo stepenovanje

Primer: (713) mod 1000

Iterativna verzija

Koraci za n = 13

Iterativna modularna verzija

Objašnjenje

Primene

Primena: zadatak Mešalica

Objašnjenje koda

Složenost

Primer: 3¹³

Primer: (7¹³) mod 1000