Exponenciació binària: diferència entre les revisions

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 &Theta(log ''n''), per tant, aquests algorismes només milloren la 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.