Exponenciació binària: diferència entre les revisions
Contingut suprimit Contingut afegit
m →Algorisme: TeX Etiquetes: Edita des de mòbil Edició web per a mòbils |
m →Alternatives i generalitzacions: neteja Etiquetes: Edita des de mòbil Edició web per a mòbils |
||
Línia 34:
:<math>a^{15} = x^3 \times ([x^3]^2)^2 \!</math> (5 multiplicacions amb una cadena òptima de sumes, si es reutilitza ''x''<sup>3</sup>)
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 [[compilador]]s on s'han pretabulat les cadenes per a potències petites). Ara bé, hi ha uns quants algorismes [[heurística|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 de exponenciació per elevació al quadrat de forma asimptòtica per un factor constant en el millor dels casos.
{{ORDENA:Exponenciacio Binaria}} <!--ORDENA generat per bot-->
| |||