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]--;
}