Algoritam brzog stepenovanja — objašnjenje i primeri

Brzo stepenovanje (exponentiation by squaring) je efikasan algoritam za računanje vrednosti izraza Xn — odnosno broja X stepenovanog na eksponent n. Ovaj pristup značajno ubrzava izračunavanje u poređenju sa jednostavnim ponavljanim množenjem.

Korak 1 — Naivan pristup

Naivan pristup podrazumeva da se rezultat na početku postavi na 1, a zatim se u svakoj iteraciji petlje množi brojem X ukupno n puta. Iako jednostavan, ovaj pristup ima složenost O(n) i postaje prespor za veće vrednosti eksponenta.

#include <iostream>
using namespace std;

// Naivan pristup stepenovanju broja
long long naivnoStepenovanje(long long broj, long long stepen) {
    long long rezultat = 1;

    // Rezultat se množi brojem 'broj' onoliko puta koliko iznosi 'stepen'
    for (long long i = 0; i < stepen; ++i) {
        rezultat *= broj;
    }

    return rezultat;
}

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

Korak 2 — Ključna ideja algoritma

Ključna opservacija brzog stepenovanja je da se eksponent može deliti na pola kada je paran:
Xn = Xn/2 × Xn/2

Dakle, umesto da vršimo n uzastopnih množenja, eksponent se u svakom koraku prepolovi. Na ovaj način se broj operacija smanjuje sa n na oko log₂(n) množenja, što značajno ubrzava izračunavanje.

Na slici 1 prikazan je primer brzog stepenovanja za n = 16. Vidimo da se zadatak rešava rekurzivnim prepolavljanjem izložioca u svakom nivou:
X16 = X8 × X8, zatim X8 = X4 × X4, i tako dalje dok ne dođemo do osnovnog slučaja X1.

Na slici su jasno označeni nivoi rekurzije:

• Plavo – prvi nivo rekurzije, gde se X16 deli na dva dela X8 i X8
• Zeleno – drugi nivo, gde se svako X8 deli na X4 × X4
• Crveno – treći nivo, gde se X4 deli na X2 × X2, a zatim na osnovne elemente X

Ovaj prikaz pomaže da se vizuelno razume kako algoritam smanjuje broj operacija: svaka podela eksponenta na pola predstavlja jedan nivo rekurzije, pa je ukupan broj nivoa jednak log₂(n).

 #include <iostream> using namespace std; // Rekurzivna funkcija za brzo stepenovanje 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 polovinu stepena long long polovina = brzoStepenovanje(broj, stepen / 2); // Ako je stepen paran: Xⁿ = (X^(n/2))² if (stepen % 2 == 0) return polovina * polovina; else // Ako je neparan: Xⁿ = X × (X^(n/2))² return broj * polovina * polovina; } int main() { cout << brzoStepenovanje(2, 16) << endl; // Ispisuje: 65536 return 0; } 

Korak 3 — Slučaj neparnog eksponenta

Kada je eksponent neparan, on se može zapisati u obliku n = 2k + 1. Tada važi sledeće:
X2k+1 = X × X2k

Dakle, u slučaju neparnog stepena najpre se izračuna X2k (kao da je stepen paran), a zatim se rezultat pomnoži još jednom sa X. Ovako algoritam ostaje jednostavan i efikasan, uz samo jedno dodatno množenje.

 #include <iostream> using namespace std; // Brzo stepenovanje sa eksplicitnim obradama za paran i neparan slučaj long long brzoStepenovanjeDetaljno(long long broj, long long stepen) { if (stepen == 0) return 1; if (stepen % 2 == 0) { // Ako je stepen paran: n = 2k long long polovina = brzoStepenovanjeDetaljno(broj, stepen / 2); return polovina * polovina; } else { // Ako je stepen neparan: n = 2k + 1 long long polovina = brzoStepenovanjeDetaljno(broj, (stepen - 1) / 2); long long kvadrat = polovina * polovina; return broj * kvadrat; } } int main() { cout << brzoStepenovanjeDetaljno(3, 13) << endl; // Ispisuje: 1594323 return 0; } 

Ovaj pristup se lako proširuje i na modularno stepenovanje, gde se rezultat svodi po nekom modulu (npr. mod 1000000007), što je česta primena u programiranju i kriptografiji.

Korak 4 — Brzo stepenovanje u slučaju neparnog eksponenta

Do sada smo videli da za paran eksponent n važi:
Xn = Xn/2 × Xn/2.

Međutim, kada je eksponent neparan, možemo ga zapisati kao:
n = 2k + 1, gde je k ceo broj.

Tada važi sledeća relacija:
Xn = X × X2k, odnosno:
X2k+1 = X × (Xk)².

To znači da algoritam za brzo stepenovanje treba da obuhvati i dodatno množenje sa brojem X kada je eksponent neparan. Ovim pristupom zadržavamo efikasnost algoritma, jer se broj rekurzivnih poziva i dalje smanjuje približno logaritamski u odnosu na veličinu eksponenta.

#include <iostream>
using namespace std;

// Funkcija koja implementira brzo stepenovanje za sve slučajeve
long long brzoStepenovanjeNeparno(long long broj, long long stepen) {
    // Bazni slučaj — svaki broj na nulti stepen je 1
    if (stepen == 0)
        return 1;

    // Rekurzivno izračunavanje polovine stepena
    long long polovina = brzoStepenovanjeNeparno(broj, stepen / 2);

    // Ako je stepen paran: n = 2k
    if (stepen % 2 == 0)
        return polovina * polovina;
    else {
        // Ako je stepen neparan: n = 2k + 1
        // Rezultat se dobija kao: X × (X^(k))²
        return broj * polovina * polovina;
    }
}

int main() {
    cout << "2^7 = " << brzoStepenovanjeNeparno(2, 7) << endl;   // Ispisuje: 128
    cout << "3^5 = " << brzoStepenovanjeNeparno(3, 5) << endl;   // Ispisuje: 243
    cout << "5^3 = " << brzoStepenovanjeNeparno(5, 3) << endl;   // Ispisuje: 125
    return 0;
}
    

Kao što se vidi u primeru, algoritam pravilno obrađuje i neparne stepene. Za svaki neparan eksponent vrši se jedno dodatno množenje sa osnovnim brojem X, dok se za paran slučaj rezultat dobija kvadriranjem polovine stepena.

Ukupna složenost algoritma i dalje je O(log n), što ga čini višestruko bržim od jednostavnog pristupa.

// Primer za 3^13
// n = 13 → 13 = 2*6 + 1 → X^(13) = X * (X^6)^2

// Prvo se izračuna X^6:
// X^6 = (X^3)^2 = ((X^1)^2 * X)^2
// a zatim X^13 = X * (X^6)^2

// Dakle, 3^13 = 3 * (3^6)^2 = 3 * (729)^2 = 3 * 531441 = 1594323
    

Ovako možemo lako razumeti rekurzivni tok algoritma: svaka rekurzivna grana smanjuje eksponent za polovinu, sve dok ne dođe do nule, gde se vraća osnovna vrednost 1.

Korak 5 — Modularno brzo stepenovanje

U mnogim zadacima, posebno u algoritmima i takmičarskom programiranju, potrebno je izračunati velike stepene brojeva, ali da rezultat ostane u granicama određenog modula (m), najčešće da bi se izbeglo prekoračenje tipa (overflow).

Takvi izrazi se obično zapisuju kao:
(Xn) mod m

Modularno brzo stepenovanje zasniva se na istom principu kao i klasična verzija:

• Ako je eksponent paran, Xn = (Xn/2)²
• Ako je eksponent neparan, Xn = X × (X(n−1))

#include <iostream>
using namespace std;

// Funkcija koja računa (broj^stepen) % mod efikasno
long long modularnoStepenovanje(long long broj, long long stepen, long long mod) {
    // Bazni slučaj: bilo koji broj na nulti stepen je 1
    if (stepen == 0)
        return 1;

    // Rekurzivno računanje polovine stepena
    long long polovina = modularnoStepenovanje(broj, stepen / 2, mod);

    // Računanje kvadrata mod m
    long long rezultat = (polovina * polovina) % mod;

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

    return rezultat;
}

int main() {
    long long broj = 7, stepen = 13, mod = 1000;
    cout << "(" << broj << "^" << stepen << ") % " << mod << " = "
         << modularnoStepenovanje(broj, stepen, mod) << endl;

    // Dodatni testovi
    cout << "(3^20) % 50 = " << modularnoStepenovanje(3, 20, 50) << endl;
    cout << "(2^30) % 17 = " << modularnoStepenovanje(2, 30, 17) << endl;

    return 0;
}
    

U svakom koraku se vrši operacija % mod kako bi rezultati ostali u zadatim granicama. Na taj način se izbegava prelivanje brojeva, što je posebno važno kada su X i n vrlo veliki.

Na primer, izraz:
(713) mod 1000 daje rezultat:
343, a izračunava se efikasno kroz samo nekoliko rekurzivnih poziva.

Kratka analiza složenosti:
Algoritam radi u vremenskoj složenosti O(log n), jer se u svakom koraku eksponent prepolovi. To je višestruko brže od jednostavnog pristupa koji bi imao složenost O(n).

// (7^13) % 1000
// n = 13 → neparan → 7 * (7^6)^2 % 1000
// (7^6) = ((7^3)^2) % 1000
// (7^3) = 7 * (7^1)^2 % 1000
// Svaki međurezultat se računa po modulu 1000

// Konačni rezultat: 343
    

Modularno brzo stepenovanje je osnovni alat u mnogim algoritmima — koristi se u kriptografiji, kodovima za hash funkcije, teoriji brojeva, kao i u većini zadataka sa velikim brojevima na programerskim takmičenjima.

Iterativna verzija algoritma brzog stepenovanja

Rekurzivna verzija algoritma brzog stepenovanja jasno pokazuje princip „deljenja eksponenta na pola“, ali u praksi se često koristi iterativna verzija jer ne koristi dodatni prostor na steku i obično je brža. U ovoj verziji koristi se binarni zapis eksponenta — svaka cifra u binarnoj reprezentaciji eksponenta određuje da li će trenutna vrednost baze biti uključena u rezultat.

Na primer, ako je eksponent n = 13, njegov binarni zapis je 1101₂. To znači da je:

X¹³ = X⁸ × X⁴ × X¹

Iterativna verzija koristi petlju u kojoj se eksponent postepeno deli sa 2 (odnosno pomera ulevo u binarnom zapisu), dok se baza kvadrira u svakom koraku. Ako je trenutni bit eksponenta jednak 1, tada se rezultat množi sa trenutnom vrednošću baze.

// Iterativna verzija brzog stepenovanja (bez rekurzije)
#include <iostream>
using namespace std;

double brzoStepenovanjeIterativno(double baza, int stepen)
{
    double rezultat = 1.0;

    // Dok je stepen veći od nule
    while (stepen > 0)
    {
        // Ako je trenutni bit eksponenta 1, uključujemo bazu u rezultat
        if (stepen % 2 == 1)
            rezultat *= baza;

        // Kvadriramo bazu (odgovara pomeranju bita ulevo)
        baza *= baza;

        // Delimo eksponent sa 2 (odsecamo najmanji bit)
        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;
}

Objašnjenje koraka algoritma

• Korak 1: Inicijalizuje se promenljiva rezultat sa 1.0.
• Korak 2: Ako je eksponent neparan (tj. poslednji bit je 1), rezultat se množi trenutnom bazom.
• Korak 3: Kvadrira se baza (odgovara pomeranju na sledeći bit eksponenta).
• Korak 4: Eksponent se deli sa 2, čime se pomera ka sledećem bitu.
• Korak 5: Kada eksponent postane 0, algoritam se završava — rezultat sadrži konačnu vrednost Xⁿ.

Ovaj pristup ima istu vremensku složenost kao i rekurzivni algoritam — O(log n), ali izbegava rekurzivne pozive i dodatni prostor na steku, što ga čini pogodnijim za rad sa velikim eksponentima.

Modularna verzija algoritma

U mnogim problemima u programiranju i kriptografiji nije potrebno izračunati ceo rezultat Xⁿ, već samo njegov ostatak pri deljenju sa nekim brojem m, tj. izraz (Xⁿ) mod m. Ovo se naziva modularno stepenovanje i veoma je važno u oblastima kao što su:

• kriptografija (RSA algoritam, Diffie–Hellman razmena ključeva),
• takmičarsko programiranje (računanje velikih stepena sa ograničenim rezultatima),
• optimizacija aritmetike sa velikim brojevima.

Glavna ideja je da se u svakom koraku algoritma uzima ostatak pri deljenju sa m, čime se vrednosti zadržavaju male i izbegava prekoračenje tipa. Osnovna svojstva modularne aritmetike omogućavaju sledeće:

(X × Y) mod m = ((X mod m) × (Y mod m)) mod m

Na osnovu toga, može se jednostavno prilagoditi iterativna verzija algoritma brzog stepenovanja:

// Modularna verzija brzog stepenovanja (X^n mod m)
#include <iostream>
using namespace std;

long long brzoStepenovanjeModularno(long long baza, long long stepen, long long mod)
{
    long long rezultat = 1;
    baza = baza % mod; // osiguravamo da je baza u granicama modula

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

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

        // Delimo eksponent sa 2
        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 algoritma

• Korak 1: U svakom množenju koristi se mod m da bi se sprečilo prekoračenje.
• Korak 2: Kada je eksponent neparan, trenutna baza se uključuje u rezultat (takođe pod modulom).
• Korak 3: Baza se kvadrira i ponovo uzima mod, što čini algoritam efikasnim i bezbednim.
• Korak 4: Eksponent se deli sa 2 u svakom prolazu petlje (kao kod binarne dekompozicije).

Primene u praksi

Modularno stepenovanje se koristi svuda gde su potrebne velike potencije brojeva u kontrolisanim granicama:

• Kriptografija: u RSA algoritmu koristi se izraz (M^e mod n) za šifrovanje poruke.
• Takmičarsko programiranje: u mnogim zadacima se traži rezultat izraza Xⁿ modulo 10⁹+7.
• Simulacije i igre: gde je potrebno ponavljano računanje potencija uz kontrolu rezultata.

Analiza složenosti

Složenost algoritma je O(log n), jer se eksponent u svakom koraku deli sa 2. Ovo znači da je broj operacija proporcionalan broju bitova u binarnoj reprezentaciji eksponenta.

13. MEŠALICA — Primena algoritma brzog stepenovanja

Tekst zadatka nalazi se ovde

Pogledaj kompletno rešenje i objašnjenje zadatka

Zadatak „Mešalica“ zahteva da se niz 0, 1, 2, ..., n-1 permutuje m puta pomoću zadate šeme mešanja. Ako bismo primenili naivno m puta jedno po jedno mešanje, vreme izvršavanja bi bilo predugo za velike m (do 10¹⁸). Ovde dolazi do izražaja algoritam brzog stepenovanja permutacija.

Opis algoritma

• Posmatramo jedno mešanje kao permutaciju niza.
• Primena mešanja m puta ekvivalentna je podizanju permutacije na m-ti stepen.
• Kombinovanjem permutacija putem binarnog eksponenciranja dobijamo krajnju poziciju svakog elementa.
• Ovaj pristup ima vremensku složenost O(n log m), što je optimalno za zadate granice.

Primer rešenja u C++

#include <iostream>
#include <vector>

using namespace std;

// Funkcija koja kombinuje dve permutacije
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]]; // Element iz b[i]-te pozicije ide na i-tu poziciju
    }
    return c;
}

// Brzo stepenovanje permutacije
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; // Identitet permutacije

    while (m > 0) {
        if (m % 2 == 1) {
            rezultat = kombinujPermutacije(rezultat, perm); // Ako je bit 1, kombinujemo
        }
        perm = kombinujPermutacije(perm, perm); // Kvadriranje permutacije
        m /= 2;
    }

    return rezultat;
}

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

    vector<int> mesanje(n);
    for (int i = 0; i < n; i++) cin >> mesanje[i];

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

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

    return 0;
}

Objašnjenje koda

• kombinujPermutacije: spaja dve permutacije tako da dobijemo novu permutaciju ekvivalentnu primeni obe redom.
• brzoStepenujPermutaciju: koristi binarno eksponenciranje za permutaciju; svaki bit eksponenta m odlučuje da li se trenutna permutacija kombinuje sa rezultatom.
• Na kraju dobijamo krajnju permutaciju niza nakon m mešanja.
• Efikasnost: O(n log m), što omogućava rešavanje velikih vrednosti m i n.

Zaključak

Ovaj primer pokazuje kako se algoritam brzog stepenovanja može koristiti i van numeričkih problema, konkretno na permutacijama. Takva primena je česta u takmičarskom programiranju, simulacijama i problemima sa cikličnim transformacijama nizova.