Cześć, w dzisiejszym artykule zajmiemy się problemem, który na pierwszy rzut oka wydaje się oczywisty. Chodzi o dodawanie liczb. Nie będzie to jednak zwykłe dodawanie, lecz dodawanie wielkich liczb!

Pisząc wielkich, mam tu na myśli takie, które nie mieszczą się w standardowych typach bibliotek języka, z którym pracujemy. Problem ten poruszę w języku C#, ponieważ aktualnie jest on jednym z dwóch, które używam w codziennej pracy.

W tym wpisie odpowiem na następujące pytania:

  • Jakie typy liczbowe integralne i zmiennoprzecinkowe posiada język C#?
  • W jaki sposób dodać bardzo duże liczby?
  • Jak wygląda implementacja algorytmu dodawania wielkich liczb?

Już nie mogę się doczekać, więc zaczynajmy!

Wprowadzenie

Matematyka bazuje w głównej mierze na czterech podstawowych działaniach matematycznych — dodawanie, odejmowanie, mnożenie oraz dzielenie. Wydawać by się mogło, że dzisiejsze komputery, języki programowania i ich biblioteki rozwiązują problemy tych operacji w sposób kompletny. Nie we wszystkich językach tak jest. Chociaż z drugiej strony obstawiam, że w niektórych z nich znajdą się specjalistyczne biblioteki, które operują na gigantycznych zmiennych — jeżeli tak jest, to podziel się nazwą biblioteki w komentarzu!

Z tego też tytułu postanowiłem na czynniki pierwsze rozłożyć pierwszą z operacji, a mianowicie dodawanie wielkich liczb. 

Ale zacznijmy od początku.

Typy liczbowe

Na sam początek warto porozmawiać chwilę o typach liczbowych.

Patrząc na osiągnięcia technologiczne, mogłoby się wydawać, że dzisiejsze komputery poradzą sobie z dowolnie długim ciągiem liczb w operacjach matematycznych za pomocą standardowych typów liczbowych. Jest to jednak mylne myślenie.

W programowaniu możemy wyróżnić kilka typów liczbowych. Skupię się jednak na dwóch podstawowych:

  • całkowity – typ reprezentujący liczbę całkowitą z jakiegoś zakresu zależnego od języka, a nawet konkretnej implementacji. Przedstawiany jako int lub integer.
  • zmiennoprzecinkowy – typ reprezentujący przybliżoną wartość liczby rzeczywistej. Przedstawiany jako double lub real.

I wydaje mi się, że do ponad 99% operacji matematycznych typy te są wystarczające. Mnie jednak zaciekawił ten brakujący 1%, dlatego wpadłem na pomysł rozwinięcia tego tematu. Zerknijmy do języka C# i zobaczmy, jakie mamy możliwości.

C# i jego typy

Jako język popularny, C# jest dobrze zaopatrzony w biblioteki standardowe. One oprócz typów całkowitych i zmiennoprzecinkowych obsługują również, chociażby liczby zespolone. Temat liczb zespolonych zostawię jednak na inną okazję.

Liczby całkowite w C# może przechować aż 8 podstawowych typów (od byte po long). Mogą one przechować liczby zarówno dodatnie, jak i ujemne z odpowiedniego zakresu.

Typy liczbowe integralne w języku C#.
Rysunek 1. Typy liczbowe integralne w języku C#.

Z liczbami zmiennoprzecinkowymi, przynajmniej w teorii jest dużo prościej. Jest ich raptem trzy, różnią się zakresem, dokładnością i rozmiarem. 

Typy liczbowe zmiennoprzecinkowe w języku C#.
Rysunek 2. Typy liczbowe zmiennoprzecinkowe w języku C#.

Jak widać, można przechować w zmiennych o opisanych wyżej typach naprawdę wielką liczbę. Co jednak w przypadku, gdy liczby te nie będą wystarczające?

Wtedy musimy cofnąć się do szkoły podstawowej i rozpocząć tak zwane „dodawanie pod kreskę”. 

Dodawanie wielkich liczb pod kreskę

W szkole za dzieciaka bardzo często tego sposobu używaliśmy. Gdy ja byłem w wieku szkolnym, nie było jeszcze tak wszechobecne posiadanie telefonów czy innych urządzeń, które mógłby wspomagać proces dodawania.

Do tego, by dodać dwie liczby, brało się kartkę i ołówek, a następnie po zapisaniu liczb jedna pod drugą zaczynało się dodawać od prawej strony do lewej.

Taki sam proces musimy odtworzyć w naszym dzisiejszym algorytmie.

Zastanówmy się, jak całość operacji wyglądała. Ustaliliśmy, że bierzemy dwie cyfry najbardziej wysunięte na prawą stronę, następnie dodajemy je do siebie. W przypadku gdy liczba, która wyjdzie w wyniku sumowania, jest dwucyfrowa, to liczbę jednostek przepisujemy pod spód, a liczbę 1 przenosimy do kolejnej kolumny, włączając ją do sumowania kolejnej pary liczb.

Obstawiam, że każdy z czytelników bloga zna ten rodzaj sumowania liczb, więc ograniczę się tylko do opisu, rysunek jest zbędny.

Implementacja

Program tego typu standardowo napiszemy jako aplikację konsolową podzieloną na kilka prywatnych metod. Poza metodą Main stworzyłem jeszcze metody pomocnicze SetLen oraz Reverse. Główną metodą całego programu jest metoda SumValue.

Zacznijmy od omówienia metod pomocniczych. SetLen utworzyłem, by zwrócić długość dłuższego numeru, która to długość będzie dalej używana w pętli do sumowania. Zostawiłem Ci tu furtkę do refaktoryzacji, bo celowo rozszerzyłem funkcjonalność tej funkcji o jeszcze jeden aspekt. W liczbie, która jest krótsza, dopełniam z lewej strony zerami, tak by liczby miały tę samą długość.

Druga z metod pomocniczych jest funkcją, która pozwala na odwrócenie napisu. Posłuży między innymi do tego, by wartość końcową przed zaprezentowaniem na ekranie odwrócić.

Czas na metodę Main. Jej zadanie jest standardowe, jak to bywa w tego typu roboczym kodzie. Pobieramy od użytkownika pierwszą i drugą liczbę. Następnie odpisujemy ją do zmiennej, uruchamiamy główną metodę SumValue i na koniec prezentujemy wynik na ekranie konsoli. 

Czas na gościa programu. Metoda SumValue przyjmuje na wejście dwie wprowadzone liczby. Na początku następuje deklaracja dwóch zmiennych intlen oraz transmission, w której przechowamy informację, czy przenosimy jedynkę o jedną pozycję w lewo.

Dalej uzupełniam zmienną len za pomocą opisanej wyżej metody SetLen. Kolejnym i zarazem najważniejszym krokiem jest pętla, która iteruje od prawej strony i sumuje cyfry, które są w tej samej kolumnie (znajdują się pod tym samym indeksem w tablicy). Gdy suma cyfr będzie wartością większą od 9, to przepisuje cyfrę jedności, a jedynkę przenoszę do kolejnej iteracji. Do przenoszenia między iteracjami jedynki służy właśnie zmienna transmission, która jest dosumowana do sumy dwóch cyfr, a następnie ustawiana na zero.

Podsumowanie kodu

Jak widzisz, kod poniżej wcale nie jest skomplikowany. Celowo pisałem go w formie możliwej do refaktoryzacji, więc jako zadanie domowe zrób zmiany w kodzie, tak by był mniejszy, szybszy i bardziej elegancki!

using System;
using System.Linq;

namespace DodawanieWielkichLiczb
{
    class Program
    {
        static string retVal, firstNum, secondNum;

        static void Main(string[] args)
        {
            Console.WriteLine("Podaj pierwszą liczbę:");
            firstNum = Console.ReadLine();

            Console.WriteLine("Podaj drugą liczbę:");
            secondNum = Console.ReadLine();

            retVal = SumValue(firstNum, secondNum);
            
            Console.WriteLine("Wynik sumowania równa się " + Reverse(retVal));

            Console.ReadLine();
        }

        private static string SumValue(string firstNum, string secondNum)
        {
            int len = 0, transmission = 0;

            len = SetLen(ref firstNum, ref secondNum, firstNum.Length);

            for (int i = len - 1; i >= 0; i--)
            {
                int sum = int.Parse(firstNum[i].ToString()) + int.Parse(secondNum[i].ToString()) + transmission;
                transmission = 0;

                if (sum > 9 && i != 0)
                {
                    retVal += sum.ToString().Last();
                    transmission++;
                }
                else
                    retVal += Reverse(sum.ToString());
            }

            return retVal;
        }

        private static int SetLen(ref string firstNum, ref string secondNum, int len)
        {
            if (firstNum.Length < secondNum.Length)
            {
                firstNum = firstNum.PadLeft((secondNum.Length - firstNum.Length) + firstNum.Length, '0');
                len = secondNum.Length;
            }
            else
                secondNum = secondNum.PadLeft((firstNum.Length - secondNum.Length + secondNum.Length), '0');
            return len;
        }

        private static string Reverse(string s)
        {
            char[] charArray = s.ToCharArray();
            Array.Reverse(charArray);
            return new string(charArray);
        }
    }
}

Podsumowanie

Nawet z tak prostej operacji arytmetycznej, jak dodawanie możemy stworzyć fajny algorytm i poeksperymentować na tablicach. Oczywiście to nie jest jedyny i optymalny sposób na pracę z dużymi liczbami.

Mamy przecież jeszcze odejmowanie, mnożenie czy dzielenie. Mam w planach każdy z algorytmów opisać w osobnych artykułach. Zwłaszcza mnożenie i dzielenie potrafią zaskakiwać i są na serio trudne w implementacji.

Samo dodawanie przedstawione powyżej jest bardziej w formie zabawy i pokazania możliwości rozwiązania problemu, jednak kod raczej wymagałby dużej ilości optymalizacji, by wdrożyć go we własnej bibliotece. Działania na tablicach i stringach nie są zbyt wydajne przy wielkich zbiorach danych. Może warto byłoby do tematu wrócić w przyszłości i spróbować operacji na bitach? Napisz w komentarzu, co myślisz o rozszerzeniu dzisiejszego artykułu!

Ja teraz uciekam przygotować scenariusz do kolejnego odcinka na kanale. Jak jeszcze Cię tam nie było, to zapraszam.

Na koniec mam dla Ciebie ciekawe książki z dziedziny matematyki!

PS. Będę wdzięczny za komentarze pod tym postem!

PS2. Czeka też na Ciebie prezent. Wystarczy, że zapiszesz się na Newsletter poniżej!

PS3. Dołącz do naszej grupy na Facebook!


Subskrybuj

Zapisz się na Newsletter, odbierz NAGRODĘ w postaci e-booka z 10 omówionymi algorytmami pojawiającymi się w pytaniach podczas REKRUTACJI..

Dodatkowo otrzymuj co niedzielę informacje na temat nowych wpisów, wiadomości ze świata IT i matematyki oraz ciekawych wydarzeniach. Nie przegap i dołącz już dziś do 942 osób!.

Źródła

https://docs.python.org/3/library/stdtypes.html 
http://users.uj.edu.pl/~ufkapano/algorytmy/lekcja02/liczby.html 
https://docs.microsoft.com/pl-pl/dotnet/csharp/language-reference/builtin-types/integral-numeric-types 
http://www-users.mat.uni.torun.pl/~philip/warsztaty2005/teoria.php
https://eduinf.waw.pl/inf/utils/010_2010/1010.php  
Autor

👨‍💻 .NET and Python programming passionate 🏦 Digtial Banking Solutions 🎓 Student 📊 Psychology 📚 Bookworm 🏠 Warsaw

2 komentarze

  1. Rozumiem że te wielkie liczby trzeba zapisać jako dane typu String, ponieważ nie mamy takich typów danych które by pasowały do tak dużych liczb.

    Fajnie mi się czytało ten artykuł. Język C# znam tylko z Unity i kiepsko się w nim orientuje, jednak jest on trochę podobny do Javy więc implementacje byłem w stanie przeczytać.

    Życzę powodzenia z pisaniem o mnożeniu oraz dzieleniu. Bardzo chętnie przeczytam jak się te artykuły ukażą.

    Pozdrawiam.

    • Cześć Mateusz!

      Tak, wielkie liczby można zapisać między innymi do zmiennej typu String i zrobić na nich operacje arytmetyczne. Zasadniczo zmienna typu String w C# jest tablicą Char i w prosty sposób można na tej tablicy przeprowadzać operacje.

      Pozdrawiam.

Napisz komentarz

Witryna wykorzystuje Akismet, aby ograniczyć spam. Dowiedz się więcej jak przetwarzane są dane komentarzy.