Așa cum îi spune și numele, exponențierea logaritmică (exponențierea rapidă, ridicarea la putere în timp logaritmic, exponențierea prin ridicare la pătrat) este metoda optimă pentru a ridica un număr $x$ la o putere $n$, ce are complexitatea logaritmică. În acest articol voi prezenta cum se poate implementa exponențierea logaritmică în C++, și cum se poate utiliza acest concept pentru a genera eficient al $n$-lea termen dintr-un șir de numere ce se bazează pe o recurență liniară.

Exponențierea liniară

Soluția naivă pentru calcularea lui $x^n$, ce se bazează pe definiția puterii, este să inițializăm o variabilă p cu 1, iar apoi să o înmulțim cu x de n ori. Iată implementarea iterativă a algoritmului:

Există deja o funcție pow definită în biblioteca cmath, dar dacă definiți funcția de mai sus înainte de main este OK. Compilatorul va ști că nu vă referiți la cea din biblioteca respectivă.

Că tot vorbeam de funcția pow din cmath. Este periculoasă, deoarece lucrează cu tipul double, nu cu int, așa că uneori un apel de genul pow(10, 2) poate returna 99. Prefer să-mi definesc propria funcție pentru ridicarea la putere decât să o folosesc pe asta.

Mai jos este și o implementare recursivă ce se bazează pe recurența următoare:

$$x^{n}={\begin{cases}x \cdot x^{n-1}&{\mbox{, pentru }}n>0\\1&{\mbox{, pentru }}n=0\end{cases}}$$

Se observă că, indiferent de modul de implementare, această metodă are complexitatea liniară, mai exact $O(n)$. Bine, în cazul variantei recursive se face un apel în plus, pow(x, 0), dar nu contează.

Exponențierea logaritmică

Pornim de la un alt mod de a defini ridicarea la putere:

$$x^{n}={\begin{cases}x(x^{2})^{(n-1)/2}&{\mbox{, pentru }}n{\mbox{ impar}}\\(x^{2})^{n/2}&{\mbox{, pentru }}n{\mbox{ par}}\end{cases}}$$

De data asta, voi începe cu varianta recursivă, pentru că e mai ușor de înțeles.

Implementare recursivă

Știm deja că acest algoritm are complexitatea $O(\log_2 n)$, dar hai să o și demonstrăm. De exemplu, pentru apelul pow(3, 618), lanțul de apeluri recursive arată cam așa:

Se observă că, la fiecare pas al doilea parametru se înjumătățește, exact cum la căutarea binară, la fiecare pas se înjumătățește intervalul de căutare. Numărul de pași făcuți de exponențierea logaritmică este $\left[\log_2 n \right] + 1$. Acel $+ 1$ vine de la apelul final, când se returnează 1. Iată deci, cum pentru 618 se efectuează doar 11 apeluri, pe când prin ridicarea la putere obișnuită, s-ar fi executat 618 pași.

Ei bine, de obicei, pentru exponenți suficienți de mari ca să se simtă diferența dintre cele două variante de ridicare la putere, rezultatul final ar depăși long long int-ul. De aceea, de cele mai multe ori, se cere doar restul lui modulo un anumit număr prim. Aplicând regulile clasice de aritmetică modulară, o funcție ce calculează acest rest arată așa:

Implementare iterativă

Exponențierea logaritmică poate fi implementată și iterativ, dar aici este nevoie de un pic mai multă atenție.

În variabila p rețin rezultatul. Parametrul x se ridică la pătrat la fiecare intrare în while, iar exponentul n se înjumătățește. Când n este impar, se actualizează rezultatul printr-o înmulțire cu x și o decrementare a lui n. Întotdeauna n va fi impar măcar o dată, pentru că la ultima intrare în while, n va fi 1.

Generarea rapidă a șirurilor recurente prin exponențiere logaritmică

Cele mai importante două aplicații ale exponențierii rapide sunt calcularea inversului modular (despre care voi vorbi în alt articol) și generarea celui de-al $n$-lea termen dintr-un șir ce se bazează pe o recurență liniară, ambele, desigur, în timp logaritmic.

Voi lua ca exemplu șirul lui Fibonacci, care este definit astfel:

$$f(n)={\begin{cases}f(n-1)+f(n-2)&{\mbox{, pentru }}n>1\\n&{\mbox{, pentru }}0 \le n \le 1\end{cases}}$$

Pentru a genera al $n$-lea termen din șirul lui Fibonacci (tot modulo un număr dat, pentru că numerele lui Fibonacci cresc foarte repede), ar trebui, în mod obișnuit, să generăm mai întâi toți termenii mai mici decât $n$. Complexitatea este $O(n)$. Există totuși o soluție mult mai bună, care necesită niște matematică de a 11-a, ce se bazează pe înmulțirea matricelor. Voi da mai întâi soluția și o explic după. Am notat al $n$-lea termen din șirul lui Fibonacci cu $f(n)$.

$$\begin{pmatrix} 1 & 1 \\ 1 & 0 \\ \end{pmatrix}^{n} = \begin{pmatrix} f(n + 1) & f(n) \\ f(n) & f(n - 1) \\ \end{pmatrix}$$

Folosim inducție matematică. Presupunând că ceea ce am scris mai sus este adevărat, demonstrăm că:

$$\begin{pmatrix} f(n + 1) & f(n) \\ f(n) & f(n - 1) \\ \end{pmatrix} \cdot \begin{pmatrix} 1 & 1 \\ 1 & 0 \\ \end{pmatrix} = \begin{pmatrix} f(n + 2) & f(n + 1) \\ f(n + 1) & f(n) \\ \end{pmatrix}$$

Păi, respectând regulile de înmulțire a matricelor, obținem următoarele relații:

$$\begin{align} f(n+1) \cdot 1 + f(n) \cdot 1 &= f(n + 2) \\
f(n+1) \cdot 1 + f(n) \cdot 0 &= f(n + 1) \\
f(n) \cdot 1 + f(n-1) \cdot 1 &= f(n + 1) \\
f(n) \cdot 1 + f(n-1) \cdot 0 &= f(n) \end{align}$$

Care, se vede clar că sunt adevărate. Ei bine, știind că înmulțirea matricelor este asociativă, putem folosi exponențierea logaritmică pentru ridicarea matricei de mai sus la puterea $n$. Iată o sursă elegantă, de 100 de puncte, pentru problema Kfib de pe InfoArena (care cere generarea celui de-al $k$-lea termen Fibonacci):

Observați că în funcția pow am folosit operații pe biți. Este una dintre funcțiile în care ador să folosesc operații pe biți pentru împărțirea la 2, ține de coding-style-ul meu 😀

Constanta din spatele complexității logaritmice din această problemă este dată de numărul de înmulțiri pe scalari ce se efectuează la înmulțirea a două matrice. Care, pentru matricele pătratice este dimensiunea lor la puterea a treia; în cazul nostru $8$.

Generalizare

Mai rămâne să găsim generalizarea acestei metode pentru generarea celui de-al $n$-lea termen al șirului recurent:

$$f(n)={\begin{cases}
a_{1}\cdot f(n-1)+a_{2}\cdot f(n-2)+\cdots+a_{k}\cdot f(n-k)&{\mbox{, pentru }}n>k\\
x_{1}&{\mbox{, pentru }}n = 1\\
x_{2}&{\mbox{, pentru }}n = 2\\
\cdots\\
x_{k}&{\mbox{, pentru }}n = k
\end{cases}}$$

Fără alte introduceri, relația este:

$$\begin{pmatrix}
x_{k} & x_{k-1} & \cdots & x_{1} \end{pmatrix} \cdot
\begin{pmatrix}
a_{1} & 1 & 0 & 0 & \cdots & 0\\
a_{2} & 0 & 1 & 0 & \cdots & 0\\
a_{3} & 0 & 0 & 1 & \cdots & 0\\
\vdots & \vdots & \vdots & \vdots & \ddots & \vdots\\
a_{k-1} & 0 & 0 & 0 & \cdots & 1\\
a_{k} & 0 & 0 & 0 & \cdots & 0\\
\end{pmatrix}^{n-k} =
\begin{pmatrix}
x_{n} & x_{n-1} & \cdots & x_{n-k+1} \end{pmatrix}$$

Luați-vă un exemplu mic și veți vedea că este chiar o relație intuitivă; un antrenament bun este problema Iepuri de pe InfoArena. Recurența asta se poate aplica la fel de bine și la șirul lui Fibonacci. Însă acolo, întâmplător:

$$\begin{pmatrix}
1 & 1 \\
1 & 0 \\
\end{pmatrix} = \begin{pmatrix}
f(2) & f(1) \\
f(1) & f(0) \\
\end{pmatrix}$$

Așa că, următoarele două relații sunt la fel de corecte și de utile:

$$\begin{align} \begin{pmatrix}
1 & 1 \\
1 & 0 \\
\end{pmatrix} \cdot
\begin{pmatrix}
1 & 1 \\
1 & 0 \\
\end{pmatrix}^{n-1} &=
\begin{pmatrix}
f(n+1) & f(n) \\
f(n) & f(n-1) \\
\end{pmatrix} \\ \begin{pmatrix}
1 & 0
\end{pmatrix} \cdot
\begin{pmatrix}
1 & 1 \\
1 & 0 \\
\end{pmatrix}^{n-1} &=
\begin{pmatrix}
f(n) & f(n-1)
\end{pmatrix} \end{align}$$

Am ales-o totuși pe prima, pentru că necesită un pic mai puțin cod.

Probleme recomandate

Sper că am explicat suficient de clar cum stă treaba cu exponențierea logaritmică și cu șirurile recurente. Dacă aveți vreo întrebare despre acest subiect, nu ezitați să o adresați printr-un comentariu mai jos 🙂

Îți place conținutul acestui site?

Dacă vrei să mă susții în întreținerea server-ului și în a scrie mai multe articole de calitate pe acest blog, mă poți ajuta printr-o mică donație. Află aici cum o poți face!