}
==

Mai exista o alta modalitate de a inmulti doua numere de cate $N$ cifre fiecare, care are complexitatea !lucrul-cu-nr-mari?img2bun.jpg!. Ea deriva de un algoritm propus de Strassen in 1969 pentru inmultirea matricelor. Diferenta se face simtita, ce-i drept pentru valori mari ale lui $N$, dar constanta multiplicativa creste destul de mult si, in plus, solutia e mai greu de implementat; de aceea nu recomandam implementarea ei in timpul concursului. Ideea de baza este sa se micsoreze numarul de inmultiri si sa se mareasca numarul de adunari, deoarece adunarea a doi vectori se face in O({$N$}), pe cand inmultirea se face in O({$N$} $2$). Sa consideram intregii $A$ si $B$, fiecare de cate $N$ cifre. Trebuie sa-i inmultim intr-un timp T({$N$}) mai bun decat O({$N$} $2$). Sa impartim numarul $A$ in doua "bucati" $C$ si $D$, fiecare de cate $N$/{$2$} cifre, iar intregul $B$ in doua bucati $E$ si $F$, tot de cate $N$/{$2$} cifre (presupunem ca $N$ este par):

Mai exista o alta modalitate de a inmulti doua numere de cate $N$ cifre fiecare, care are complexitatea <tex>O(N^{log_2 3}) \approx O(N^{1.58}) \approx O(N \sqrt{N})</tex>. Ea deriva de un algoritm propus de Strassen in 1969 pentru inmultirea matricelor. Diferenta se face simtita, ce-i drept pentru valori mari ale lui $N$, dar constanta multiplicativa creste destul de mult si, in plus, solutia e mai greu de implementat; de aceea nu recomandam implementarea ei in timpul concursului. Ideea de baza este sa se micsoreze numarul de inmultiri si sa se mareasca numarul de adunari, deoarece adunarea a doi vectori se face in O({$N$}), pe cand inmultirea se face in O({$N$} $2$). Sa consideram intregii $A$ si $B$, fiecare de cate $N$ cifre. Trebuie sa-i inmultim intr-un timp T({$N$}) mai bun decat O({$N$} $2$). Sa impartim numarul $A$ in doua "bucati" $C$ si $D$, fiecare de cate $N$/{$2$} cifre, iar intregul $B$ in doua bucati $E$ si $F$, tot de cate $N$/{$2$} cifre (presupunem ca $N$ este par):

!lucrul-cu-nr-mari?img3.jpg!