/* Adica A[i]=A[i]-(B[i]+T);
       if (A[i]<0) T=1; else T=0;
       if (T) A[i]+=10; */

  while (!A[A[0]]) A[0]--;

  while (!A[A[0]]&&A[0]>1) A[0]--;

}
==

Atunci se poate scrie relatia:

**$A$ x $B$ = ({$C$} x $10^N/2^$ + $D$) x ({$E$} x $10^N/2^$ + $F$) = $CE$ x $10^N^$ ({$CF$} + $DE$) x $10^N/2^$ + $DF$**

**$A$ x $B$ = ({$C$} x $10^N/2^$ + $D$) x ({$E$} x $10^N/2^$ + $F$) = $CE$ x $10^N^$ + ({$CF$} + $DE$) x $10^N/2^$ + $DF$**

Pentru a putea calcula produsul $A$ x $B$ avem, prin urmare, nevoie de patru produse partiale, de trei adunari si de doua inmultiri cu puteri ale lui $10$. Adunarile si inmultirile cu puteri ale lui $10$ se fac in timp liniar. Daca efectuam cele patru produse partiale prin patru inmultiri, rezulta formula recurenta de calcul **T({$N$})=4T({$N$}/{$2$})+O({$N$})** care duce prin eliminarea recurentei la <tex>T(N)\in O(N)^2</tex>. Cu alte cuvinte, inca n-am castigat nimic. Trebuie sa reusim cumva sa reducem numarul de inmultiri de la $4$ la $3$, chiar daca prin aceasta vom mari numarul de adunari necesare. Sa definim produsul **$G$ = ({$C$} + $D$) x ({$E$} + $F$) = $CE$ + $CF$ + $DE$ + $DF$ = $CE$ + $DF$ + ({$CF$} + $DE$)**
Atunci putem scrie: **$A$ x $B$ = $CE$ x $10$^{$N$}^ + ({$G$} - $CE$ - $DF$) x $10$^{$N$}/{$2$}^ + $DF$**

public

protected