Uvod
Kada je u pitanju problematika obavljanja operacija sa "velikim" celobrojnim vrednostima na računaru, potrebno je prvo razmotriti šta (zapravo) smatramo velikim brojevima u kontekstu diskusije koja je pred nama.
Recimo, 1000000 je svakako "veliki" broj (sam po sebi), ali - u pitanju je vrednost koja je višestruko manja od smeštajnog kapaciteta standardnih 32-bitnih (a pogotovo 64-bitnih) int registara na računarima.
Sa 32 bita, najveća apsolutna vrednost koju možemo zapisati preko označene promenljive (celobrojna vrednost koja može biti, i pozitivan, i negativan broj), je 2147483647 (231 - 1), dok je najveća neoznačena vrednost 4294967295 (232 - 1), a u slučaju da koristimo 64-bitne celobrojne promenljive - vrednosti su mnogo veće: 9223372036854775807 (263 - 1), odnosno 18446744073709551615 (264 - 1).
Dakle, veliki brojevi (u kontekstu ovog članka), su celobrojne vrednosti koje se ne mogu zapisati preko standardnih celobrojnih promenljivih, pa stoga zahtevaju poseban postupak.
Da bismo mogli da operišemo nad zaista velikim brojevima, koje ne možemo zapisivati neposredno (sa brojevima od 50, 100 ili više cifara) - predstavićemo brojeve kao nizove cifara.
Sabiranje velikih brojeva koji su predstavljeni kao nizovi cifara
Uzmimo za primer brojeve 1594 i 647 (čiji je zbir 2241).
Cifre dva navedena broja ćemo smestiti u dva niza (a i b), i poravnati ih "uz desnu stranu", tako da se u oba slučaja cifra jedinica poklopi sa poslednjim elementom niza.
Kao što znamo, cifra koju pri sabiranju upisujemo "ispod crte", dobija se sabiranjem svih cifara na datoj poziciji (u ovom slučaju, dve cifre), i 'prenosa', iz sabiranja sa prethodne (desne) pozicije - tako da se (iz ukupnog zbira), za upis uzima cifra jedinica, a ostatak prenosi u sledeću (levu) kolonu.
U primeru koji koristimo, prenos je cifra desetica (praktično, "leva cifra").
Ostaje samo pitanje: kako da postupak sabiranja uobličimo algoritamski (tako da se može izvršavati na računaru).
Cifru koju upisujemo ispod crte, lako ćemo dobiti ispitivanjem ostatka pri celobrojnom deljenju sa 10, a cifru koju prenosimo u sledeću kolonu - deljenjem zbira sa 10 - preko sledećih formula:
cifra[i] = (a[i] + b[i] + prenos) % 10;
prenos = (a[i] + b[i] + prenos) / 10;
Ovakvim postupkom - u potpunosti smo izbegli grananja u programu, koja bi nastala ukoliko bismo ispitivali da li je zbir na datoj poziciji veći ili jednak deset!
Za zapis ćemo, pored nizova a i b, koristiti i niz r (rezultat), kao i pomoćnu promenljivu p (prenos):
Pri računanju, krenućemo od poslednjeg mesta.
Kao zbir smo dobili broj 11, pa ćemo cifru jedinica zapisati u niz r, a cifru desetica zapamtiti kao ostatak (prenos).
U sledećem koraku, zbir je 14 (četvorku smeštamo u niz r, a 1 pamtimo kao prenos).
Ponovićemo postupak i u sledećoj koloni, pri čemu kao rezultat dobijamo zbir 12 (što ćemo rasporediti na sledeći način: r[3] = 2; p = 1):
U poslednjem koraku rezultat je 2 (dodela: r[2] = 2; p = 0;):
Putićemo vas da sami "saberete nule" u poslednje dve kolone ....
.... a rezultat koji na kraju dobijamo je niz sa ciframa koje predstavljaju rezultat sabiranja: [0, 0, 2, 2, 4, 1].
Oduzimanje velikih brojeva koji su predstavljeni kao nizovi cifara
U prethodnom odeljku smo istakli da je jedna od najvažnijih odlika opisanog postupka sabiranja, to što smo izbegli odlučivanje (odnosno grananje), čime smo sveli pojedinačne korake na bezuslovno izvršavanje.
Potrebno je da "nešto slično" izvedemo i u postupku oduzimanja.
Rešenje je da sve cifre iz "donjeg niza" oduzmemo od broja 10 (što daje isti rezultat kao da smo cifre iz "gornjeg niza" sabrali sa brojem 10, samo što je preglednije) - i da potom obavimo sabiranje.
Međutim, ovoga puta (s obzirom na svojevrsnu pozajmicu koju smo napravili), prenos će biti 0 - u slučaju da je zbir veći ili jednak 10, a u slučaju da je zbir manji, prenos će biti -1.
Uzećemo ponovo iste brojeve: 1594 i 647 (čija razlika je 947).
Niz koji predstavlja broj 1594 ostaće isti, dok će niz koji predstavlja broj 647, biti formiran tako što ćemo svaku cifru oduzeti od broja 10 (dosledno ćemo to uraditi čak i na pozicijama koje sadrže cifru 0), čime dobijamo sledeću početnu situaciju.
Na poziciji jedinica (počinjemo sa računanjem), sabiranjem cifara dobijamo rezultat 7 - i budući da je data vrednost manja od 10 - prenos je -1.
Sada, kada razumemo da metod funkcioniše, pogledajmo i implementaciju u C-u:
cifra[i] = (a[i] + b[i] + prenos) % 10;
prenos = (a[i] + b[i] + prenos) / 10 - 1;
Za prenos je samo potrebno oduzeti 1 od rezultata koji se dobija istim postupkom kao u slučaju sabiranja, jer sada (da se podsetimo), prenos treba da bude 0 kada je zbir cifara veći ili jednak deset (vrlo jednostavno i elegantno).
Pogledajmo računicu i na ostalim mestima.
U drugom koraku, zbir (14), je veći od 10, te je stoga prenos 0.
U trećem koraku, zbir (19), je manji od 10, a prenos je -1.
U četvrtom koraku, zbir je 10, a prenos 0.
U pretposlednjem koraku, zbir je (ponovo) 10 i prenos je (ponovo) 0 ....
.... kao i u poslednjem koraku.
Dalje računanje se obustavlja, budući da smo došli do početka niza.
Rezultat je niz [0, 0, 0, 9, 4, 7] - baš kao što smo i očekivali.