==

h2. Inmultirea si impartirea cu puteri ale lui 10
 
Aceste functii sunt uneori utile. Ele pot folosi si functiile de inmultire a unui vector cu un scalar, care vor fi prezentate mai jos, dar se pot face si prin deplasarea intregului numar spre stanga sau spre dreapta. De exemplu, inmultirea unui numar cu $100$ presupune deplasarea lui cu doua pozitii inspre cifra cea mai semnificativa si adaugarea a doua zerouri la coada. Principalul avantaj al scrierii unor functii separate pentru inmultirea cu $10$, $100$, ..., este ca se pot folosi rutinele de acces direct al memoriei ({$FillChar$}, respectiv $memmove$). Iata functiile care realizeaza deplasarea vectorilor, atat prin mutarea blocurilor de memorie, cat si prin atribuiri succesive.
 
== code(c)|
void Shl(Huge H, int Count)
/* H <- H*10ACount */
{
  /* Shifteaza vectorul cu Count pozitii */
  memmove(&H[Count+1],&H[1],sizeof(int)*H[0]);
  /* Umple primele Count pozitii cu 0 */
  memset(&H[1],0,sizeof(int)*Count);
  /* Incrementeaza numarul de cifre */
  H[0]+=Count;
}
 
void Shl2(Huge H, int Count)
/* H <- H*10ACount */
{ int i;
 
  /* Shifteaza vectorul cu Count pozitii */
  for (i=H[0];i;i--) H[i+Count]=H[i];
  /* Umple primele Count pozitii cu 0 */
  for (i=1;i<=Count;) H[i++]=0;
  /* Incrementeaza numarul de cifre */
  H[0]+=Count;
}
 
void Shr(Huge H, int Count)
/* H <- H/10ACount */
{
  /* Shifteaza vectorul cu Count pozitii */
  memmove(&H[1],&H[Count+1],sizeof(int)*(H[0]-Count));
  /* Decrementeaza numarul de cifre */
  H[0]-=Count;
}
 
void Shr2(Huge H, int Count)
/* H <- H/10ACount */
{ int i;
 
  /* Shifteaza vectorul cu Count pozitii */
  for (i=Count+1;i<=H[0];i++) H[i-Count]=H[i];
  /* Decrementeaza numarul de cifre */
  H[0]-=Count;
}
==
 
h2. Inmultirea unui vector cu un scalar
 
Si aceasta operatie este o simpla implementare a modului manual de efectuare a calculului. La inmultirea "de mana" a unui numar mare cu unul de o singura cifra, noi parcurgem deinmultitul de la sfarsit la inceput, si pentru fiecare cifra efectuam urmatoarele operatii:
 
* Inmultim cifra respectiva cu inmultitorul;
* Adaugam "transportul" de la inmultirea precedenta;
* Separam ultima cifra a rezultatului si o trecem la produs;
* Celelalte cifre are rezultatului constituie transportul pentru urmatoarea inmultire;
* La sfarsitul inmultirii, daca exista transport, acesta are o singura cifra, care se scrie inaintea rezultatului.
 
Exact acelasi procedeu se poate aplica si daca inmultitorul are mai mult de o cifra. Singura deosebire este ca transportul poate avea mai multe cifre (poate fi mai mare ca $9$). Din aceasta cauza, la sfarsitul inmultirii, poate ramane un transport de mai multe cifre, care se vor scrie inaintea rezultatului. Iata de exemplu cum se calculeaza produsul $312$ x $87$:
 
!lucrul-cu-nr-mari?imnult1.jpg!
 
Procedura este descrisa mai jos:
 
== code(c)|
void Mult(Huge H, unsigned long X)
/* H <- H*X */
{ int i;
  unsigned long T=0;
 
  for (i=1;i<=H[0];i++)
    { H[i]=H[i]*X+T;
      T=H[i]/10;
      H[i]=H[i]%10;
    }
  while (T) /* Cat timp exista transport */
    { H[++H[0]]=T%10;
      T/=10;
    }
}
==
 
h2. Inmultirea a doi vectori
 
Daca ambele numere au dimensiuni mari si se reprezinta pe tipul de date Huge, produsul lor se calculeaza inmultind fiecare cifra a deinmultitului cu fiecare cifra a inmultitorului si trecand rezultatul la ordinul de marime (exponentul lui $10$) cuvenit. De fapt, acelasi lucru il facem si noi pe hartie. Considerand acelasi exemplu, in care ambele numere sunt "uriase", produsul lor se calculeaza de mana astfel
 
!lucrul-cu-nr-mari?inmult2.jpg!
 
S-a luat deci fiecare cifra a inmultitorului si s-a efectuat produsul partial corespunzator, corectand la fiecare pas rezultatul prin calculul transportului. Rezultatul pentru fiecare produs partial s-a scris din ce in ce mai in stanga, pentru a se alinia corect ordinele de marime. Acest procedeu este oarecum incomod de implementat. Se pot face insa unele observatii care usureaza mult scrierea codului:
 
* Prin inmultirea cifrei cu ordinul de marime $10i$ din primul numar cu cifra cu ordinul de marime $10j$ din al doilea numar se obtine o cifra corespunzatoare ordinului de marime $10i$+$j$ in rezultat (sau se obtine un numar cu mai mult de o singura cifra, caz in care transportul merge la cifra corespunzatoare ordinului de marime $10i$ + $j$ + $1$).
* Daca numerele au $M$ si respectiv $N$ cifre, atunci produsul lor va avea fie $M$ + $N$ fie    $M$ + $N$ - $1$ cifre. Intr-adevar, daca numarul $A$ are $M$ cifre, atunci $10^M-1^$ &le; $A$ < $10^M^$ si {$10^N-1^$} &le; $B$ < $10^N^$, de unde rezulta $10^M+N-2^$ &le; $A$ x $B$ < $10^M+N^$.
* La calculul produselor partiale se poate omite calculul transportului, acesta urmand a se face la sfarsit. Cu alte cuvinte, intr-o prima faza putem pur si simplu sa inmultim cifra cu cifra si sa adunam toate produsele de aceeasi putere, obtinand un numar cu "cifre" mai mari ca $9$, pe care il aducem la forma normala printr-o singura parcurgere. Sa reluam acelasi exemplu:
 
!lucrul-cu-nr-mari?inmult3.jpg!
 
Aceasta operatie efectueaza {$M$}x{$N$} produse de cifre si {$M$}{@+@}{$N$} (sau {$M$}{@+@}{$N$}-{$1$}, dupa caz) "transporturi" pentru aflarea rezultatului, deci are complexitatea O({$M$}x{$N$}). Iata si implementarea:
 
== code(c)|
void MultHuge(Huge A, Huge B, Huge C)
/* C <- A x B */
{I int i,j,T=0;
 
  C[0]=A[0]+B[0]-1;
  for (i=1;i<=A[0]+B[0];) C[i++]=0;
  for (i=1;i<=A[0];i++)
    for (j=1;j<=B[0];j++)
      C[i+j-1]+=A[i]*B[j];
  for (i=1;i<=C[0];i++)
    { T=(C[i]+=T)/10;
      C[i]%=10;
    }
  if (T) C[++C[0]]=T;
}
==
 
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):
 
!lucrul-cu-nr-mari?img3.jpg!
 
 
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$**