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$**

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$**
Pentru aceasta varianta, folosim doar trei inmultiri, si chiar daca avem nevoie de sase adunari si scaderi si doua inmultiri cu puteri ale lui $10$, complexitatea se va reduce la <tex> O(N^{log_2 3}) </tex>. In cazul in care $N$ este o putere a lui $2$, impartirea in doua a numerelor se poate face fara probleme la fiecare pas, pana se ajunge la numere de o singura cifra, care se inmultesc direct. In cazul in care $N$ nu este o putere a lui $2$, este comod sa se completeze numerele cu zerouri pana la o putere a lui $2$. In functiile descrise mai jos, $MultRec$ nu face decat inmultirea recursiva, pe cand $MultVect2$ se ocupa si de corectarea numarului de cifre (incrementarea pana la o putere a lui $2$). Pentru calculul produselor $C$ x $E$ si $D$ x $F$, procedura $MultRec$ se autoapeleaza; pentru calcularea produsului ({$C$}{@+@}{$D$}) x ({$E$}{@+@}{$F$}), insa, este nevoie sa fie apelata procedura $MultVect2$, deoarece prin cele doua adunari poate sa apara o crestere a numarului de cifre al factorilor, care in acest caz trebuie readusi la un numar de cifre egal cu o putere a lui $2$.
 
== code(c)|
void MultHuge2(Huge A, Huge B, Huge P);
void MultRec(Huge A, Huge B, Huge P)
{ Huge C,D,E,F,CE,DF;
  if (A[0]==1)
    { P[1]=A[1]*B[1];
      P[0]=(P[2]=P[1]/10)>0 ? 2 : 1;
      P[1]%=10;
    }
    else { P[0]=0;
           AtribHuge(C,A);Shr(C,A[0]/2);
           AtribHuge(D,A);D[0]=A[0]/2;
           AtribHuge(E,B);Shr(E,B[0]/2);
           AtribHuge(F,B);F[0]=B[0]/2;
           MultRec(C,E,CE);MultRec(D,F,DF);
           Add(C,D);Add(E,F);
           MultHuge2(C,E,P);
           Subtract(P,CE);Subtract(P,DF);
           Shl(P,A[0]/2);
           Shl(CE,A[0]);Add(P,CE);
           Add(P,DF);
         }
}
void MultHuge2(Huge A, Huge B, Huge P)
/* P <- A x B, varianta NA(lg 3) */
{ int i,j,NDig=A[0]>B[0] ? A[0] : B[0],Needed=1,SaveA,SaveB;
  /* Corecteaza numarul de cifre */
  while (Needed<NDig) Needed<<=1;
  SaveA=A[0];SaveB=B[0];A[0]=B[0]=Needed;
  for (i=SaveA+1;i<=Needed;) A[i++]=0;
  for (i=SaveB+1;i<=Needed;) B[i++]=0;
  MultRec(A,B,P);
  /* Restaureaza numarul de cifre */
  A[0]=SaveA;B[0]=SaveB;
  while (!P[P[0]] && P[0]>1) P[0]--;
}
==
 
h2.  Impartirea unui vector la un scalar
 
Ne propunem sa scriem o functie care sa imparta numarul $A$ de tip Huge la scalarul $B$, sa retina valoarea catului tot in numarul $A$ si sa intoarca restul (care este o variabila scalara). Sa pornim de la un exemplu particular si sa generalizam apoi procedeul: sa calculam catul si restul impartirii lui $1997$ la $7$. Cu alte cuvinte, sa gasim acele numere $C$ de tip Huge si <tex>R\in{0, 1, 2, 3, 4, 5, 6}</tex> cu proprietatea ca $1997$ = $7$ x $C$ + $R$.
 
!lucrul-cu-nr-mari?impart1.jpg!
 
La fiecare pas se coboara cate o cifra de la deimpartit alaturi de numarul deja existent (care initial este $0$), apoi rezultatul se imparte la impartitor ($7$ in cazul nostru). Catul este intotdeauna o cifra si se va depune la sfarsitul catului impartirii, iar restul va fi folosit pentru urmatoarea impartire. Restul care ramane dupa ultima impartire este tocmai $R$ pe care il cautam. Procedeul functioneaza si atunci cand deimpartitul are mai multe cifre. La sfarsit trebuie sa decrementam corespunzator numarul de cifre al catului, prin neglijarea zerourilor create la inceputul numarului. Numarul maxim de cifre al catului este egal cu cel al deimpartitului.
 
== code(c)|
unsigned long Divide(Huge A, unsigned long X)
/* A <- A/X si intoarce A%X */
{ int i;
  unsigned long R=0;
 
  for (i=A[0];i;i--)
    { A[i]=(R=10*R+A[i])/X;
      R%=X;
    }
  while (!A[A[0]] && A[0]>1) A[0]--;
  return R;
}
==
 
Daca dorim numai sa aflam restul impartirii, nu mai avem nevoie decat sa recalculam restul la fiecare pas, fara a mai modifica vectorul A:
 
== code(c)|
unsigned long Mod(Huge A, unsigned long X)
/* Intoarce A%X */
{ int i;
  unsigned long R=0;
 
  for (i=A[0];i;i--)
    R=(10*R+A[i])%X;
  return R;
}
==