Exponenciació binària

De Viquipèdia
Dreceres ràpides: navegació, cerca

La Exponenciació binaria és un algorisme que es fa servir per a calcular potències d'un nombre. També se'l coneix com a algorisme d'elevar al quadrat i multiplicar o exponenciació ràpida. Fa servir de forma implícita l'expressió binaria de l'exponent. Es pot fer servir de forma força general, per exemple en aritmètica modular.

Anàlisi del problema[modifica | modifica el codi]

La forma immediata de plantejar el càlcul d'una potència n^p, és multiplicar n per si mateix p cops. Tanmateix existeixen mètodes més eficients, on el nombre d'operacions necessàries en comptes de ser de ordre p és del ordre de \log _{2}\left( p \right).

Per exemple, es pot escriure p=\sum_{i\leq d} a_i2^i per a_i\in \{0,1\}, i llavors es comprova que:

n^p=n^{a_0}(n^2)^{a_1}(n^4)^{a_2}\dots (n^{2^d})^{a_d}

Calen d operacions per a calcular els n^{2^i}, més d operacions per a formar el producte dels (n^{2^i})^{a_i}. El nombre total d'operacions és doncs 2d, que és de l'ordre del logaritme de p (d és el logaritme en base 2 de p). Aquesta senzilla observació algebraica condueix a l'algorisme següent.

Algorisme[modifica | modifica el codi]

Sia n un enter estrictament superior a 1,l'algorisme es basa en els següents fets.

  • Si n és parell llavors xn=(x2)n/2. Llavors n'hi ha prou amb calcular yn/2 amb y=x2.
  • Si n és senar i n>1, llavors xn=x×(x2)(n-1)/2. N'hi ha pro amb calcular y(n-1)/2 amb y=x2 i multiplicar el resultat per x.

Això porta a l'algorisme recursiu següent que calcula xn per a un enter estrictament positiu n:


pot\grave{e}ncia\left( x,n \right)=\left\{ \begin{matrix}
 x, \\
 pot\grave{e}ncia\left( x^{2},{n}/{2}\; \right), \\
 x\times pot\grave{e}ncia\left( x^{2},{\left( n-1 \right)}/{2}\; \right), \\
\end{matrix} \right.\begin{matrix}
 si\ n=1 \\
 si\ n\ \acute{e}s\ parell \\
 si\ n>2\ \acute{e}s\ senar \\
\end{matrix}


El mètode no només funciona en els nombres reals sinó en qualsevol semigrup, en particular en criptografia per a calcular les potencies d'un anell d'enters mòdul q. També es pot fer servir per a calcular les potencies d'un element d'un grup, si es fa servir per a les potències negatives la regla : potència(x, -n) = (potència(x, n))-1.

Alternatives i generalitzacions[modifica | modifica el codi]

La exponenciació a base d'elevar al quadrat es pot veure com un algorisme que calcula l'exponent via una cadena de sumes consistent en doblar repetidament l'exponent i/o incrementant-lo en una unitat(multiplicant per x). De forma més general, si es permet que se sumin qualsevulla exponents prèviament calculats (a base de multiplicar aquestes potencies de x), de vegades es pot realitzar la exponenciació fent servir menys multiplicacions (però normalment fent servir més memòria). La potència més petita en què això passa és n=15:

a^{15} = x \times (x \times [x \times x^2]^2)^2 \! (6 multiplicacions, amb l'algorisme d'elevar al quadrat)
a^{15} = x^3 \times ([x^3]^2)^2 \! (5 multiplicacions amb una cadena òptima de sumes, si es reutilitza x3)

En general, trobar una cadena de sumes òptima per a un exponent donat és un problema difícil, per al qual no es coneixen algorismes eficients, per tant les cadenes òptimes normalment només es fan servir per a exponents petits (per exemple en compiladors on s'han pretabulat les cadenes per a potències petites). Ara bé, hi ha uns quants algorismes heurístics que, tot i que no són òptims, arriben a menys multiplicacions que la exponenciació per elevació al quadrat a canvi del cost addicional de fer servir més memòria. Respecte al nombre de multiplicacions mai creix més a poc a poc que &Theta(log n), per tant, aquests algorismes només milloren l'eficiència de l'algorisme de exponenciació per elevació al quadrat de forma asimptòtica per un factor constant en el millor dels casos.