Logaritamsko potenciranje

Čest problem u algoritamskim zadatcima je potencirati vrijednost na potenciju pri čemu je cjelobrojan. Pri rješavanju zadataka susrećemo se s ovim problemom u raznim oblicima, pa tako naša pretpostavljena baza može biti:

linearno iterativno potenciranje (brute force)
double potencija(double b, int p) {
  double sol = 1;
  for (int j = 0; j < p; ++j)
    sol *= b;
  return sol;
}

Nakon što pročitate ovu stranicu moći ćete implementirati gornju funkciju u vremenskoj složenosti .

Korištena svojstva potenciranja

Bitno se podsjetiti dva svojstva potenciranja prije objašnjenja algoritama logaritamskog potenciranja:

Rekurzivno logaritamsko potenciranje

Promatrajmo problem potenciranja kada je prirodan broj. Pretpostavimo da znamo sve potencije baze manje od . Potenciju možemo izračunati koristeći gore navedena svojstva podjelom na dva slučaja:

Prema tome, funkcija koja izračunava proizvoljnu potenciju baze se može zapisati kao:

U jeziku C++ ova funkcija bi mogla izgledati:

double potencija(double b, int p) {
  if (p % 2) {
    return potencija(b, p - 1) * b;
  } else {
    return !p ? 1 : potencija(b, p / 2) * potencija(b, p / 2);
  }
}

Vremenska složenost prikazane funkcije je i nije ništa efikasnija od jednostavnog brute force algoritma prikazanog u prvom odjeljku.

Proučimo složenost prikazanog isječka koda. Broj iteracija očito ne ovisi o bazi već samo o cjelobrojnoj potenciji. Broj iteracija možemo također prikazati rekurzivno i u svakom koraku ovisi o parnosti potencije. Za parnu potenciju broj iteracija je dvaput veći od broja iteracija za poziv potenciranja duplo manje potencije. Za neparnu potenciju, broj iteracija je za jedan veći od potenciranja za jedan manje potencije.

No, primjetimo da je pozivanje funkcije potencija(b, p/2) nepotrebno napraviti dvaput jer njena vrijednost ostaje ista! Naizgled trivijalna modifikacija će nam donijeti moćno rezanje vremenske složenosti!

rekurzivno logaritamsko potenciranje
double potencija(double b, int p) {
  if (p % 2) {
    return potencija(b, p - 1) * b;
  } else {
    double tmp = p ? potencija(b, p / 2) : 1;
    return tmp * tmp;
  }
}

Lako je vidljivo da su ove funkcije ekvivalentne. No, analizirajmo sada složenost funkcije koja jednom računa duplo manju potenciju.

Funkcija će u svakom koraku problem spustiti ili za jedan (ako je potencija neparna) ili za duplo (ako je potencija parna). Nije moguće da se dvaput za redom potencija spusti za 1. Zato jer ne postoje dva uzastopna neparna prirodna broja. Dakle, početnu potenciju ćemo u najgorem slučaju smanjivati za 1 i djeliti sa 2 naizmjenice dok ne dobijemo nultu potenciju. Koliko će koraka nam trebati za to?

Neka je broj koraka u kojima smo oduzeli jedinicu, te prvotna potencija. Vrijedi da je jer oduzimati jedinicu možemo raditi najčešće svaki drugi korak. Preostaje nam izračunati koliko puta moramo podijeliti preostali dio potencije do trivijalnog slučaja ?

Odgovor je .

Prema tome, u najgorem slučaju broj koraka za izvršavanje logaritamskog rekurzivnog potenciranja jest

ili drugim riječima, složenost je "logaritamska".

Iterativno logaritamsko potenciranje

U primjeru na početku ove stranice stoji brute-force algoritam za potenciranje koji je iterativan. To će za nas značiti da se funkcija ne izvodi rekurzivno što je u nekim slučajevima povoljnije:

Kako bi iterativno došli do rješenja moramo od nekud početi. Naš početak je nulta potencija jer odgovor za taj slučaj znamo - .

Trenutni rezultat ćemo u svakoj iteraciji kvadrirati, a u nekim iteracijama ćemo ga dodatno pomnožiti sa bazom. Pogledajmo još jednom redosljed operacija u rekurzivnom pozivu za 2^6:

operacijatrenutna potencijarezultat
potencija(2, 6/2) ^ 2p = 664
potencija(2, 3-1) * 2p = 38
potencija(2, 2/2) ^ 2p = 24
potencija(2, 1-1) * 2p = 12
trivijalap = 01

Radi jednostavnosti, promotrimo sada izvršavanje malo brže rekurzivne funkcije potenciranja u kojoj u svakom koraku dijelimo potenciju sa dva, a u neparnim koracima radimo oduzimanje:

rekurzivno logaritamsko potenciranje s malo manje koraka
double potencija(double b, int p) {
  double tmp = potencija(b, p / 2);
  if (p % 2) {
    return tmp * tmp * b;
  } else {
    return !p ? 1 : tmp * tmp;
  }
}

Osim što je ovdje puno jednostavnije vidjeti logaritamski broj koraka pri izvršavanju, lakše ćemo zaključiti kako izgraditi iterativno potenciranje. Pogledajmo sada tablicu operacija.

operacijatrenutna potencijarezultat
potencija(2, 6/2) ^ 2p = 664
potencija(2, 3/2) ^ 2 * 2p = 38
potencija(2, 1/2) ^ 2 * 2p = 12
trivijalap = 01

Podsjeća na pretvaranje dekadskog broja u binarni iz prvog srednje? Pa, u pravu ste. Vidimo da je algoritam jako sličan. Pri pretvaranju dekadskog broja u binarni u svakom koraku pišemo 1 za neparni trenutni rezultat i 0 za parni trenutni rezultat. U slučaju potenciranja, za svaki neparni rezultat kvadriramo upola manju potenciju (sljedeći rezultat, ako idemo od gore) i pomnožimo sa bazom, dok za svaki parni rezultat samo kvadriamo.

Budući da je množenje komutativno i asocijativno, možemo samo obrnuti redosljed operacija i nagraditi potenciju "od dna" bottom-top. Za primjer uzmimo broj 10 za potenciju. U binarnom rastavu taj broj glasi 1010:

međurezultatbinarna znamenkakomentar
100broj je paran, pišemo 0 i dijelimo
51broj je paran, pišemo 1 i dijelimo
20broj je paran, pišemo 0 i dijelimo
11broj je paran, pišemo 1 i dijelimo
00broj je paran, pišemo 0 i dijelimo
00... mogli bi i stati?

Budući da broj čitamo od dolje prema gore nije bitno koliko nula smo na početku napisali. Sada probajmo napraviti iterativno potenciju 2^10. Rečeno je da krećemo od dna tablice i za svaki redak trenutni rezultat kvadriramo, a ako smo napisali 1 onda jos radimo množenje sa bazom.

Početni međurezultat je 1 (nulta potencija svakog broja). Koliko god 0-redova imali na kraju tablice mi ćemo kvadrirati 1 i ponovno dobiti 1. Tek sa prvom zapisanom jedinicom od dna ćemo promijeniti međurezultat u nešto različito od 1. Čitajući tablicu od dna i izvođeči naznačene radnje dobijamo sljedeći izraz:

Budući da računalo već svaki cijeli broj prikazuje u binarnom rastavu, iterativno potenciranje u programskom jeziku C možemo domišljato implementirati sa operatorima nad bitmaskama.

iterativno logaritamsko potenciranje
double potencija(double b, unsigned int p) {
  double sol = 1;
  for (unsigned int mask = (1<<31); mask; mask >>= 1)
    sol = (sol * sol) * (mask & p ? b : 1);
  return sol;
}

Ovaj kod efektivno ide po binarnim znamenkama od s lijeva na desno, kvadrira trenutno rješenje svakim korakom i dodatno na svaku binarnu znamenku 1 množi rješenje s bazom.

Mogući škripci i mnemotehnike:

jos jednostavnije iterativno logaritamsko potenciranje
double potencija(double b, unsigned int p) {
  double sol = 1;
  for (; p; p >>= 1)
    if (p & 1) sol *= b;
    b *= b;
  }
  return sol;
}

U posljednjem primjeru prikazano je još jednostavnije iterativno logaritamsko potenciranje koje pregledava bitove od desna na lijevo. Do ovog rezultata smo došli prikazujući potenciju kao sumu potencija broja dva (binarni zapis broja):

Te koristeći pravilo za potenciju zbroja:

Primjene

U svim gore navedenim primjerima koristili smo tip podataka za rješenje double i čitatelj se mogao zapitati zašto jednostavno ne koristimo ugrađenu cmath funkciju double pow(double x, double y). Istina je, za tipove podataka s posmačnom točkom je možda i bolje koristiti ugrađenu funkciju, no što je s cjelobrojnim tipovima podataka?

Čitatelj također može primjetiti da rezanje složenosti s linearne na logaritamsku nije bilo vrijedno svog ovog truda jer za svaki cjelobrojni tip najveća potencija koja ne izaziva preljev je samo 63, i to ako koristimo za bazu broj 2 i koristimo long long.

No, možda se dogodi da ćemo morati potencirati matricu b, a znamo da je množenje matrica jako skupa operacija!

I uostalom, što ako nas zanima samo ostatak pri djeljenju neke potencije kao što je ?

Zaključak

Operaciju cjelobrojnog potenciranja , moguće je izvesti koristeći operacija množenja.

Primjer svih algoritama koje smo koristili kroz ovaj članak vidljiv je na ovdje.

Zadaci

n-th Power
The last digit
CALCULATE POW(2004,X) MOD 29
Accomodate the palace

© 2012. Anton Grbin Creative Commons License

Ovaj članak objavljen je pod
Creative Commons Attribution-ShareAlike 3.0 Croatia License