Info & MatematicăMatematică şi informatică pe pâine…

9 Inmultirea numerelor intregi mari

Pentru anumite aplicatii, trebuie sa consideram numere intregi foarte mari.
Daca ati implementat algoritmii pentru generarea numerelor lui Fibonacci, probabil
ca v-ati confruntat deja cu aceasta problema. Acelasi lucru s-a intamplat in
1987, atunci cand s-au calculat primele 134 de milioane de cifre ale lui p.
In criptologie, numerele intregi mari sunt de asemenea extrem de importante
(am vazut acest lucru in Sectiunea 7.7). Operatiile aritmetice cu operanzi intregi
foarte mari nu mai pot fi efectuate direct prin hardware, deci nu mai putem
presupune, ca pana acum, ca operatiile necesita un timp constant. Reprezentarea
operanzilor in virgula flotanta ar duce la aproximari nedorite. Suntem nevoiti
deci sa implementam prin software operatiile aritmetice respective.

In cele ce urmeaza, vom da un algoritm divide et impera pentru inmultirea intregilor
foarte mari. Fie u si v doi intregi foarte mari, fiecare de n
cifre zecimale (convenim sa spunem ca un intreg k are j cifre
daca k < 10 ^j, chiar daca k < 10
^j-1). Daca s = n/2,
reprezentam pe u si v astfel:

u = 10^sw + x, v = 10^sy + z,    unde  0  x < 10^s, 0  z < 10^s

Intregii w si y au cate n/2 cifre, iar intregii x si z
au cate n/2 cifre. Din relatia

uv = 10^2swy + 10^s(wz+xy) + xz

obtinem urmatorul algoritm divide et impera
pentru inmultirea a doua numere intregi mari.

function inmultire(u, v)
n  cel mai mic intreg astfel incat u si v sa aiba fiecare n cifre
if
n este mic then calculeaza in mod clasic
produsul uv
return produsul uv astfel calculat
s  n div 2
w  u div 10^s ; x  u mod 10^s
y  v div 10^s ; z  v mod 10^s
return inmultire(w, y)  10^2s
+ (inmultire(w, z)+inmultire(x,
y))  10^s
+ inmultire(x, z)

Presupunand ca folosim reprezentarea din
Exercitiul 7.28, inmultirile
sau impartirile cu 10^2s
si 10^s, ca si adunarile, sunt
executate intr-un timp liniar. Acelasi lucru este atunci adevarat si
pentru restul impartirii intregi, deoarece

u mod 10^s = u - 10^sw, v mod 10^s = v - 10^s y

Notam cu t_d (n) timpul necesar acestui algoritm, in cazul cel mai nefavorabil,
pentru a inmulti doi intregi de n
cifre. Avem

t_d (n)  3t_d (n/2) + t_d (n/2) + Q(n)

Daca n
este o putere a lui 2, aceasta relatie devine

t_d (n)  4t_d (n/2) + Q(n)

Folosind Proprietatea 5.2, obtinem relatia t_d  Q(n²).
(Se observa ca am reintalnit un exemplu din Sectiunea 5.3.5). Inmultirea clasica
necesita insa tot un timp patratic (Exercitiul 5.29). Nu am castigat astfel
nimic; dimpotriva, am reusit sa marim constanta multiplicativa!

Ideea care ne va ajuta am mai folosit-o la metoda lui Strassen (Sectiunea 7.8).
Deoarece inmultirea intregilor mari este mult mai lenta decat adunarea, incercam
sa reducem numarul inmultirilor, chiar daca prin aceasta marim numarul adunarilor.
Adica, incercam sa calculam wy, wz+xy
si xz prin mai putin de patru inmultiri. Considerand produsul

r = (w+x)(y+z) = wy + (wz+xy) + xz

observam ca putem inlocui ultima linie din
algoritm cu

r  inmult(w+x, y+z)
p  inmult(w, y);
q  inmult(x, z)
return 10^2sp + 10^s(r-p-q)  + q

Fie t(n) timpul necesar algoritmului modificat pentru a inmulti
doi intregi, fiecare cu cel mult n cifre. Tinand cont ca w+x
si y+z pot avea cel mult 1+n/2
cifre, obtinem

t(n)  t(n/2) + t(n/2) + t(1+n/2) + O(n)

Prin definitie, functia t este nedescrescatoare. Deci,

t(n)  3t(1+n/2) + O(n)

Notand T(n) = t(n+2) si
presupunand ca n este o putere a lui
2, obtinem

T(n)  3T(n/2)  + O(n)

Prin metoda iteratiei (ca in Exercitiul 7.24), puteti arata ca

T  O(n^lg 3 | n
este o putere a lui 2)

Sau, mai elegant, puteti ajunge la acelasi rezultat aplicand o schimbare de
variabila (o recurenta asemanatoare a fost discutata in Sectiunea 5.3.5). Deci,

t  O(n^lg 3 | n este o putere a lui 2)

Tinand din nou cont ca t este nedescrescatoare, aplicam Proprietatea
5.1 si obtinem t  O(n^lg 3).

In concluzie, este posibil sa inmultim doi intregi
de n cifre intr-un timp in O(n^lg 3), deci
si in O(n^1,59). Ca si la metoda lui Strassen, datorita constantelor
multiplicative implicate, acest algoritm este interesant in practica doar
pentru valori mari ale lui n. O
implementare buna nu va folosi probabil baza 10, ci baza cea mai mare pentru
care hardware-ul permite ca doua cifre sa fie inmultite direct.

clear=all>

Pagini: 1 2 3 4 5 6 7 8 9 10