Revizia anterioară Revizia următoare
Lucrul cu numere mari
De multe ori, in probleme, apar situatii cand este nevoie sa memoram numere intregi foarte mari (de ordinul sutelor de cifre), iar uneori trebuie sa efectuam si operatii aritmetice cu aceste numere.
Numerele reprezentate pe vectori le vom numi pur si simplu "vectori", iar numerele reprezentate printr-un tip ordinal de date le vom numi, printr-o analogie usor fortata cu matematica, "scalari". Sa vedem acum cum se efectueaza operatiile elementare pe aceste numere.
Initializarea
Un vector poate fi initializat in trei feluri: cu 0, cu un scalar sau cu un alt vector.
La initializarea cu 0, singurul lucru pe care il avem de facut este sa setam numarul de cifre pe 0. De aceea, este practic inutil sa implementam aceasta functie ca atare; putem folosi in loc singura instructiune pe care ea o contine.
void Atrib0(Huge H);
{ Hi0s=0; }La initializarea cu un scalar nenul, trebuie sa asezam fiecare cifra pe pozitia corespunzatoare, afland in paralel si numarul de cifre. Se incepe cu cifra unitatilor, si la fiecare pas se pune in vector cifra cea mai putin semnificativa, dupa care numarul de reprezentat se imparte la 10 (neglijandu-se restul), iar numarul de cifre se incrementeaza.
void AtribValue(Huge H, unsigned long X)
{ Hi0s=0;
while (X)
{ Hi++Hi0ss=X%10;
X/=10;
}
}Iata, de exemplu, cum se pune pe vector numarul 195:
In sfarsit, initializarea unui vector cu altul se face printr-o simpla copiere (se pot folosi cu succes rutine de lucru cu memoria, cum ar fi FillChar in Pascal sau memmove in C). Pentru eleganta, poate fi folosita si atribuirea cifra cu cifra:
void AtribHuge(Huge H, Huge X)
{ int i;
for (i=0;i<=Xi0s;i++) Hiis=Xiis;
}Compararea
Pentru a compara doua numere "uriase", incepem prin a afla numarul de cifre semnificative (deoarece, in urma anumitor operatii pot rezulta zerouri nesemnificative care "atarna" totusi la numarul de cifre). Aceasta se face decrementand numarul de cifre al fiecarui numar atata timp cat cifra cea mai semnificativa este 0. Dupa ce ne-am asigurat asupra acestui punct, comparam numarul de cifre al celor doua cifre. Numarul cu mai multe cifre este cel mai mare. Daca ambele numere au acelasi numar de cifre, pornim de la cifra cea mai semnificativa si comparam cifrele celor doua numere pana la prima diferenta intalnita. In acest moment, numarul a carui cifra este mai mare este el insusi mai mare.
Daca toate cifrele numerelor sunt egale doua cate doua, atunci in mod evident numerele sunt egale.
Dupa cum se vede, algoritmul seamana foarte bine cu ceea ce s-a invatat la matematica prin clasa a II-a (doar ca atunci nu ni s-a spus ca este vorba de un "algoritm"). Rutina de mai jos compara doua numere uriase H1 si H2 si intoarce -1, 0 sau 1, dupa H1 este mai mic, egal sau mai mare decat H2.
int Sgn(Huge H1,Huge H2)
{ int i;
while (!H1[H1[0]] && H1[0]) H1[0]--;
while (!H2[H2[0]] && H2[0]) H2[0]--;
if (H1[0]!=H2[0])
return H1[0]<H2[0] ? -1 : 1;
i=H1[0];
while (H1[i]==H2[i] && i) i--;
return H1[i]<H2[i] ? -1 : H1[i]==H2[i] ? 0 : 1;
}Adunarea a doi vectori
Fiind dati doi vectori, A cu M cifre si B cu N cifre, adunarea lor se face in mod obisnuit, ca la aritmetica. Pentru a evita testele de depasire, se recomanda sa se completeze mai intai vectorul cu mai putine cifre cu zerouri pana la dimensiunea vectorului mai mare. La sfarsit, vectorul suma va avea dimensiunea vectorului mai mare dintre A si B, sau cu 1 mai mult daca apare transport de la cifra cea mai semnificativa. Procedura de mai jos adauga numarul B la numarul A.
void Add(Huge A, Huge B)
/* A <- A+B */
{ int i,T=0;
if (B[0]>A[0])
{ for (i=A[0]+1;i<=B[0];) A[i++]=0;
A[0]=B[0];
}
else for (i=B[0]+1;i<=A[0];) B[i++]=0;
for (i=1;i<=A[0];i++)
{ A[i]+=B[i]+T;
T=A[i]/10;
A[i]%=10;
}
if (T) A[++A[0]]=T;
}Scaderea a doi vectori
Se dau doi vectori A si B si se cere sa se calculeze diferenta A - B. Se presupune B ≤ A (acest lucru se poate testa cu functia Sgn). Pentru aceasta, se porneste de la cifra unitatilor si se memoreaza la fiecare pas "imprumutul" care trebuie efectuat de la cifra de ordin imediat superior (imprumutul poate fi doar 0 sau 1). Deoarece B ≤ A, avem garantia ca pentru a scadea cifra cea mai semnificativa a lui B din cifra cea mai semnificativa a lui A nu e nevoie de imprumut.
void Subtract(Huge A, Huge B)
/* A <- A-B */
{ int i, T=0;
for (i=B[0]+1;i<=A[0];) B[i++]=0;
for (i=1;i<=A[0];i++)
A[i]+= (T=(A[i]-=B[i]+T)<0) ? 10 : 0;
/* 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]--;
}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.
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;
}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:
Procedura este descrisa mai jos:
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;
}
}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
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 10M-1 ≤ A < 10M si 10N-1 ≤ B < 10N, de unde rezulta 10M+N-2 ≤ A x B < 10M+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:
Aceasta operatie efectueaza MxN produse de cifre si M+N (sau M+N-1, dupa caz) "transporturi" pentru aflarea rezultatului, deci are complexitatea O(MxN). Iata si implementarea:
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 
. 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):
Atunci se poate scrie relatia:
A x B = (C x 10N/2 + D) x (E x 10N/2 + F) = CE x 10N (CF + DE) x 10N/2 + DF
