Exponențiere rapidă

În informatică , exponențierea rapidă este un algoritm folosit pentru a calcula rapid puteri întregi mari . În limba engleză , această metodă se mai numește pătrat și multiplică .

Scrierea matematică

Prima modalitate de a calcula o putere $n p$ este de a multiplica $n$ de la sine $p de$ ori. Cu toate acestea, există metode mult mai eficiente, în care numărul de operații necesare nu mai este de ordinul lui $p,$ ci de ordinul $jurnalului ( p )$ .

De exemplu, dacă scriem pentru , vedem asta $p = \ sum _ {{i \ leq d}} a_ {i} 2 ^ {i}$ $a_ {i} \ in \ {0,1 \}$

n ^ {p} = n ^ {{a_ {0}}} (n ^ {2}) ^ {{a_ {1}}} (n ^ {{2 ^ {2}}}) ^ {{a_ { 2}}} \ dots (n ^ {{2 ^ {d}}}) ^ {{a_ {d}}}

Este nevoie de $d$ operații pentru a calcula toate , apoi $d$ operații suplimentare pentru a forma produsul . Numărul total de operații este deci de $2$ $d$ , ceea ce este într-adevăr de ordinul logaritmului lui $p$ . Această simplă remarcă algebrică duce la algoritmul prezentat în secțiunea următoare. $n ^ {{2 ^ {i}}}$ $(n ^ {{2 ^ {i}}}) ^ {{a_ {i}}}$

Algoritm

Fie $n$ un întreg strict mai mare decât $1$ , să presupunem că știm să calculăm, pentru fiecare $x$ real , toate puterile $x k$ ale $x$ , pentru toate $k$ , astfel încât $1 \leq k < n$ .

Dacă $n$ este egal, atunci $x n = ( x 2 ) n / 2$ . Apoi este suficient să se calculeze $y n / 2$ pentru $y = x 2$ .
Dacă $n$ este impar și $n > 1$ , atunci $x n = x ( x 2 ) ( n - 1) / 2$ . Calculați doar $y ( n - 1) / 2$ pentru $y = x 2$ și înmulțiți rezultatul cu $x$ .

Această remarcă ne aduce la următorul algoritm recursiv care calculează $x n$ pentru un întreg strict pozitiv $n$ :

{\ displaystyle {\ mbox {power}} (x, \, n) = \ left \ {{\ begin {matrix} x și {\ mbox {si}} n {\ mbox {= 1}} \\ { \ mbox {power}} (x ^ {2}, \, n / 2) și {\ mbox {si}} n {\ mbox {este chiar}} \\ x \ times {\ mbox {power}} ( x ^ {2}, \, (n-1) / 2), și {\ mbox {dacă n este impar}} \\\ end {matrix}} \ right.}

În comparație cu metoda obișnuită de înmulțire $x$ de la sine $n - 1$ ori, acest algoritm necesită în ordinea $O (log n )$ multiplicări și, astfel, accelerează calculul lui $x n$ dramatic pentru numerele întregi mari.

Metoda funcționează în orice semi-grup și este adesea utilizată pentru a calcula puterile matricilor , în special în criptografie , dar și pentru a calcula puterile într-un inel de numere întregi modulo $q$ . Poate fi, de asemenea, utilizat pentru a calcula puterile unui element dintr-un grup, folosind pentru puteri negative regula: $putere ( x , - n ) = (putere ( x , n )) -1$ . Această metodă o aplicăm atunci când înmulțim două cifre cifră cu cifră în baza 2 : grupul este . ${\ displaystyle (\ mathbb {Z}, +)}$

Vezi și tu

Articole similare

linkuri externe

(ro) Implementare în diferite limbaje de programare , pe rosettacode.org
(ro) Număr exact de înmulțiri cu acest algoritm: suita A014701 de la OEIS