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 trbuie sa efectuam si operatii aritmetice cu aceste numere. Iata un exemplu:

Se dau doua numere naturale cu n<=1000 decifre. Se cere sa se calculeze urmatoarele operatii:

- initializarea celor doua numere;

- compararea celor doua numere;

- adunarea numerelor;

- scaderea numerelor;

- inmultirea si impartirea cu puteri ale lui 10;

- inmultirea cu un scalar;

- inmultirea celor doua numere;

- impartirea unui numar cu un scalar;

- impartirea celor doua numere.

Problema este cat se poate de simpla din punct de vedere matematic; dificultatea apare la implementare, atat datorita structurilor de date necesare, cat mai ales datorita complexitatii cerute.Despre lucrul cu numere intrgi (chiar si longint) nici nu poate fi vorba, iar la lucrul cu numere reale apar erori de calcul.

Structura de date propusa pentru abordarea acestui gen de probleme este urmatoarea: numerele vor fi reprezentate printr-un vector de cifre zecimale.

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 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.

La initializarea cu un scalar nenul, trebuie sa asezam fiecare cifra pe o pozitie 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.

In sfarsit, initializarea unui vector cu altul se face printr-o simpla copiere (se poate folosi cu succes rutina de lucru cu memoria, cum ar fi fillchar in Pascal sau memove in C). Pentru eleganta, poate fi folosita si atribuirea cifra cu cifra.

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). Acestea 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 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.

Adunarea celor doua numere

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 dintr A si B, sau cu 1 mai mult daca apare transport de la cifra semnificativa. Procedura de mai jos adauga numarul B la numarul A.

operatii cu numere mari