Exponenciació binària

L'exponenciació binària é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ó binària de l'exponent. Es pot fer servir de forma força general, per exemple en aritmètica modular.

Anàlisi del problema

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 d'ordre p és de l'ordre de $\log _{2}\left(p\right)$.

Per exemple, es pot escriure $p=\sum _{i\leq d}a_{i}2^{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

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

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

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

${\text{potència}}\left(x,n\right)=\left\{{\begin{matrix}x,\\{\text{potència}}\left(x^{2},{n}/{2}\;\right),\\x\times {\text{potència}}\left(x^{2},{\left(n-1\right)}/{2}\;\right),\\\end{matrix}}\right.{\begin{matrix}{\text{si }}n=1\\{\text{si }}n{\text{ és parell}}\\{\text{si }}n>2{\text{ é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 potències d'un anell d'enters mòdul q. També es pot fer servir per a calcular les potències 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))⁻¹.

Alternatives i generalitzacions

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 potències 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 x³)

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 Θ(log n), per tant, aquests algorismes només milloren l'eficiència de l'algorisme d'exponenciació per elevació al quadrat de forma asimptòtica per un factor constant en el millor dels casos.