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. static void Main(string[] args) {
2.   long a, b;
3.   a = Convert.ToInt64(Console.ReadLine());
4.   b = Convert.ToInt64(Console.ReadLine());
5.   Console.WriteLine(a + b);
6.   Console.ReadKey();
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. static 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. static string dodaj(string a, string b, int ab_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 % ab_base] + w;
8.     t /= ab_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. static int pobierzZnak(string a, int i) {
2.   if (i < a.Length)
3.     return znakiCyfry.IndexOf(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. static void Main(string[] args) {
2.   string a, b;
3.   int ab_base;
4.   Console.WriteLine("Podaj liczby oraz system:");
5.   a = Console.ReadLine();
6.   b = Console.ReadLine();
7.   ab_base = Convert.ToInt32(Console.ReadLine());
8.   Console.WriteLine(dodaj(a, b, ab_base));
9.   Console.ReadKey();
10. }

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