Dodawanie bardzo dużych liczb

Cel

Obecnie przekroczenie limitu na zwykłym kalkulatorze w systemie jest bardzo trudne. Rozwój technologii spowodował zwiększenie dostępnych zasobów. Co za tym idzie deweloper może śmiało używać zmiennej long long int, która zajmuje 8 bajtów.

Zmienna tego typu może przechować liczbę z zakresu [-2³², 2³² - 1]. W przypadku wykonywania działań na liczbach naturalnych i usunięciu liczb ujemnych zakres zmienia się na [0, 2⁶⁴ - 1]. Wystarczy taką liczbę wyliczyć i spróbować odczytać, aby zdać sobie sprawę jak ogromny ten zakres jest: 18 446 744 073 709 551 615 (słownie: 18 trylionów 446 biliardów 744 biliony 73 miliardy 709 milionów 551 tysięcy 615). Innymi słowy wystarczy prosty kod, aby użytkownik mógł dodawać "dowolne" liczby:

1. int main() {
2.   long long int a, b;
3.   cin >> a >> b;
4.   cout << ( a + b ) << endl;
5.   system("pause");
6.   return 0;
7. }

Jednak co w przypadku, gdy taki zakres jest nie wystarczający ?

Implementacja

Opis

Jednym z mało efektywnych, ale wystarczających metod, które pozwalają na uzyskanie większego zakresu jest przechowywanie liczby w postaci tekstu. Wtedy pamięć nie jest wykorzystana w 100%, dlatego takiego rozwiązania nie znajdzie się w profesjonalnych rozwiązaniach informatycznych.

Rozpoznawanie cyfr

W celu rozpoznania i-tej cyfry zadeklarowana zostaje zmienna znakiCyfry, która przechowuje wszystkie rozpoznawane cyfry:

1. string znakiCyfry = "0123456789ABCDEFGHIJKLMNOPQRSTUWXYZ";

Cyfra na j-tej pozycji ma wartość j w systemie dziesiętnym.

Dodawanie

W przypadku wykorzystania zmiennej string będzie można przechować 4 294 967 291 znaków czyli tyle samo cyfr. Funkcja dodaj() będzie przyjmowała dwa argumenty a i b - liczby do dodania. Argument base jest opcjonalny i pozwala określić w jakim systemie jest zapisana liczba a i b. Zarówna liczby podane w argumencie jak i zwracana liczba będą przechowywane w zmiennej string.

1. string dodaj(string a, string b, int base = 10){
2.   string w = "";
3.   int i = 0;
4.   int t = 0;
5.   while(i < a.length() || i < b.length()){
6.     t += pobierzZnak(a, i) + pobierzZnak(b, i);
7.     w = znakiCyfry[t % base]+w;
8.     t /= base;
9.     i++;
10.   }
11.   if(t != 0)
12.     w = znakiCyfry[t] + w;
13.   return w;
14. }

(2.) Utwórz zmienną wynikową. Zadeklaruj zmienne pomocnicze (3.) i - będzie kontrolować, która cyfra jest dodawana oraz (4.) t - będzie przechowywać wartość przenoszoną do dalszych cyfr. (5.) Dopóki w chociaż jednej liczbie jest jeszcze cyfra to: (6.) dodaj cyfry do wartości przenoszonej. Następnie (7.) oblicz cyfrę i ją dopisz do wyniku. (8.) Usuń ostatnią cyfrę z wartości przenoszonej i (9.) przejdź do dodawania następnej liczby. (10.) Po dodaniu wszystkich liczb należy się upewnić, że zmienna t ma wartość 0. Jeśli nie to (11.) należy dopisać dodatkową cyfrę, a następnie (12.) zwrócić wynik.

Wybieranie cyfr

W procesie pobierania cyfr wykorzystywana jest funkcja pobierzZnak(). Przyjmuje ona dwa argumenty: a - liczbę zapisaną jako słowo oraz i - indeks cyfry do pobrania od prawej strony.

1. int pobierzZnak(string a, int i){
2.   if(i < a.length())
3.     return znakiCyfry.find( a[a.length() - i - 1] );
4.   return 0;
5. }

(2.) Jeśli i-ta cyfra istnieje to (3.) zwróć jej wartość zgodnie z pozycją w zmiennej znakiCyfry. (4.) Jeśli jednak taka cyfra nie istnieje to należy zwrócić 0. (Przed liczbą w dowolnym systemie można dostawić dowolną ilość zer.)

Testowanie funkcji

W celu przetestowania funkcji dodaj() należy zmienić funkcję main() tak, aby wczytywane liczby były wczytane jako tekst.

1. int main() {
2.   string a, b;
3.   int base;
4.   cout << "Podaj liczby oraz system:\n";
5.   cin >> a >> b >> base;
6.   cout << dodaj(a, b, base) << endl;
7.   system("pause");
8.   return 0;
9. }

Przykład

Przykładowo dodając dwie liczby 34F oraz 623 w systemie szesnastkowym program wypisze na ekran:

1. 972

• Kod źródłowy Implementacja