Exponenciació binària: diferència entre les revisions
Contingut suprimit Contingut afegit
m neteja i estandardització de codi |
m estandarditzant codi encapçalaments i llistes |
||
Línia 1:
L{{'}}'''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 ==
La forma immediata de plantejar el càlcul d'una potència <math>n^p</math>, é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
<math>\log _{2}\left( p \right)</math>.
Línia 9:
Calen ''d'' operacions per a calcular els <math>n^{2^i}</math>, més ''d'' operacions per a formar el producte dels <math>(n^{2^i})^{a_i}</math>. 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''<sup>n</sup>=(''x''<sup>2</sup>)<sup>''n''/2</sup>. Llavors n'hi ha prou amb calcular ''y''<sup>''n''/2</sup> amb y=x<sup>2</sup>.
* Si ''n'' és senar i ''n''>1, llavors ''x''<sup>n</sup>=''x''•(''x''<sup>2</sup>)<sup>(''n''-1)/2</sup>. N'hi ha prou amb calcular ''y''<sup>(''n''-1)/2</sup> amb y=x<sup>2</sup> i multiplicar el resultat per ''x''.
Això porta a l'algorisme [[recursivitat|recursiu]] següent que calcula ''x''<sup>''n''</sup> per a un enter estrictament positiu ''n'':
Línia 27:
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''))<sup>−1</sup>.
== 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:
| |||