Aritmetika velikih brojeva

Zašto ne koristimo promenljive?

Na ovoj stranici bavićemo se problematikom obavljanja računskih opracija nad velikim brojevima - na računaru. Pre svega, moramo biti jasni po pitanju toga šta ovde smatramo velikim brojevima. Recimo, 1000000 je velik broj, ali, s obzirom na to da su standardne celobrojne promenljive na današnjim računarima 32-bitne, ovakav broj lako se može zapisati na taj način. Da pojasnimo: 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 (2 ^ 31 - 1), dok je najveća neoznačena vrednost 4294967295 (2 ^ 32 - 1), a u slučaju da koristimo 64-bitne celobrojne promenljive, vrednosti su mnogo veće: 9223372036854775807 (2 ^ 63 - 1), odnosno 18446744073709551615 (2 ^ 64 - 1). Jasno je da 1000000 možemo zapisati preko ovakve promenljive i da takvu vrednost ne smatramo velikim brojem u smislu toga da zahteva posebne postupke računanja. Veliki brojevi (u smislu toga da zahtevaju posebne postupke za obavljanje aritmetičkih operacija) su dakle brojevi koje ne možemo zapisati korišćenjem standardnih promenljivih (najveća vrednost koju možemo zapisati preko 64-bitne celobrojne promenljive ima 20 cifara - 18446744073709551615; ukoliko pokušamo da zapišemo vrednost koja je - pa makar bilo i samo za jedan - veća od navedene, dolazi do greške prekoračenja).

Kako onda moramo postupiti ukoliko želimo da radimo sa brojevima koji su zaista ogromni (recimo, 50, 100 ili više cifara)? Moramo ih predstaviti kao nizove cifara.

Opis operacija množenja i deljenja prevazilazi okvire ovakvog teksta, ali ćemo se operacijama sabiranja i oduzimanja pozabaviti detaljno (pri čemu ćemo, radi preglednosti, ipak koristiti primere sa malim brojem cifara, ali, ne sumnjamo da će mladi programeri koji čitaju ove stranice lako zaključiti da izloženi principi važe i slučaju nizova od 50, 100 ili više elemenata).

Sabiranje velikih brojeva koji su dati kao nizovi cifara

Uzmimo za primer brojeve 1594 i 647 (njihov zbir je 2231). Cifre ova dva broja ćemo smestiti u dva niza (a i b) i poravnaćemo ih uz desnu stranu, tako da su u oba slučaja cifre jedinica poravnate sa poslednjim elementom niza.

Kao što odavno znamo, cifra koju upisujemo "ispod crte" se dobija tako što se sve (u ovom slučaju dve cifre i prenos) gornje cifre saberu, pa se iz zbira uzima desna cifra. Ono što prenosimo u sledeću kolonu je leva cifra (zadržaćemo se na sabiranju dva broja, u kom slučaju će zbir dve cifre na datoj poziciji uvek biti jednocifren, ili dvocifren).

Postavlja se samo pitanje, kako da uobličimo ovaj postupak algoritamski, tako da ga računar može izvršavati. Ove dve cifre lako ćemo dobiti deljenjem zbira sa 10, odnosno ispitivanjem ostatka pri celobrojnom deljenju sa 10. Formule koje ćemo koristiti su sledeće:

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!

Sabiranje velikih brojeva - Priprema
Slika 1. - Brojevi 1594 i 647 predstavljeni kao nizovi cifara.

Za zapis cifara koristićemo niz r (rezultat) i krenućemo od poslednjeg mesta.

Sabiranje velikih brojeva - Korak 1
Slika 2. - Veliki brojevi predstavljeni kao nizovi cifara - sabiranje - korak 1.

Kao zbir smo dobili broj 11. Cifru jedinica ćemo zapisati u niz r, a cifru desetica zapamtiti kao ostatak.

Sabiranje velikih brojeva - Korak 2
Slika 3. - Veliki brojevi predstavljeni kao nizovi cifara - sabiranje - korak 2.

Zbir je 14 (četvorku smeštamo u niz r, a 1 pamtimo kao prenos). Ponovićemo postupak i u sledećoj koloni ....

Sabiranje velikih brojeva - Korak 3
Slika 4. - Veliki brojevi predstavljeni kao nizovi cifara - sabiranje - korak 3.

.... gde dobijamo zbir 12 (r[3] = 2; p = 1). I na kraju ....

Sabiranje velikih brojeva - Korak 4
Slika 5. - Veliki brojevi predstavljeni kao nizovi cifara - sabiranje - korak 4.

.... dobijamo niz sa ciframa koje predstavljaju rezultat sabiranja [0, 0, 2, 2, 4, 1].

Sabiranje velikih brojeva - Korak 5
Slika 6. - Veliki brojevi predstavljeni kao nizovi cifara - sabiranje - konačan rezultat.

Oduzimanje velikih brojeva koji su dati kao nizovi cifara

Istakli smo u prethodnom odeljku da je jedna od najvažnijih odlika opisanog postpka sabiranja to što smo izbegli odlučivanje, odnosno grananje i sveli pojedinačne korake na bezuslovno izvršavanje. Potrebno je da nešto slično uradimo i u postupku sabiranja.

Rešenje je da sve donje cifre oduzmemo od broja 10 (što daje isti rezultat kao da smo gornje cifre sabrali sa brojem 10, samo što je preglednije) i da obavimo sabiranje, ali, ovoga puta, s obzirom na svojevrsnu pozajmicu koju smo napravili, prenos će biti nula u slučaju da je zbir veći ili jednak 10! U slučaju da je zbir manji, prenos će biti -1.

Uzećemo ponovo iste brojeve: 1594 i 647. Njihova razlika je broj 947. Niz koji predstavlja broj 1594 ostaće isti, dok će se niz koji predstalja broj 647 formirati tako što ćemo svaku cifru oduzeti od broja 10 (dosledno ćemo to uraditi čak i u slučaju cifre 0), čime dobijamo sledeću početnu situaciju.

Oduzimanje velikih brojeva - Priprema
Slika 7. - Veliki brojevi predstavljeni kao nizovi cifara - oduzimanje - Početna situacija: da bismo operaciju oduzimanja sveli na operaciju sabiranja (koja je jednostavnija), cifre broja 647 zamenićemo njihovim komplementima, ciframa 4, 6 i 3. Takođe, vodeće nule moramo komplementirati desetkama.

Sabiranjem cifara, dobijamo rezultat 7 i, budući da je data vrednost manja od 10, prenos je -1. Ne dajte se zbuniti, računica je jednostavna. Oduzimanje donje cifre od deset daje isti rezultat kao da smo gornju cifru sabrali sa 10 i računali: 14 - 7 = 7, pri čemu bismo preneli -1 u sledeću kolonu, da vratimo "pozajmicu".

Ili, možemo to izraziti još jednostavnije: (10 + 4) - 7 daje isti rezultat kao 4 + (10 - 7)!

Oduzimanje velikih brojeva - Korak 1
Slika 8. - Veliki brojevi predstavljeni kao nizovi cifara - oduzimanje - korak 1.

Sada kada razumemo da naš metod funkcioniše, pogledajmo artitmetiku koja stoji iza njega:

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, podsetimo se, prenos treba da bude 0 kada je zbir cifara veći ili jednak deset. Savršena ravnoteža i jednostavnost. :)

Pogledajmo računicu i na ostalim mestima. Zbir je veći od 10, te je stoga prenos 0.

Oduzimanje velikih brojeva - Korak 2
Slika 9. - Veliki brojevi predstavljeni kao nizovi cifara - oduzimanje - korak 2.

Zbir je manji od 10, te je stoga prenos -1.

Oduzimanje velikih brojeva - Korak 3
Slika 10. - Veliki brojevi predstavljeni kao nizovi cifara - oduzimanje - korak 3.

Zbir je jednak 10, te je stoga prenos 0.

Oduzimanje velikih brojeva - Korak 4
Slika 11. - Veliki brojevi predstavljeni kao nizovi cifara - oduzimanje - korak 4.

Zbir je ponovo jednak 10, te je prenos (ponovo) jednak 0 ....

Oduzimanje velikih brojeva - Korak 5
Slika 12. - Veliki brojevi predstavljeni kao nizovi cifara - oduzimanje - korak 5.

.... kao i u poslednjem koraku.

Oduzimanje velikih brojeva - Korak 6
Slika 13. - Veliki brojevi predstavljeni kao nizovi cifara - oduzimanje - korak 6.

Dalje računanje se obustavlja, budući da smo došli do početka niza.

Oduzimanje velikih brojeva - Korak 7
Slika 14. - Veliki brojevi predstavljeni kao nizovi cifara - oduzimanje - konačan rezultat.

Rezultat je niz [0, 0, 0, 9, 4, 7] - baš kao što smo i očekivali.

Napomena: Tekstovi i slike na sajtu www.skola-programiranja.rs (osim u slučajevima pojedinih fotografija, gde je drugačije navedeno) predstavljaju intelektualnu svojinu autora sajta www.skola-programiranja.rs i zabranjeno je njihovo korišćenje na drugim sajtovima i štampanim medijima, kao i bilo kakvo korišćenje u komercijalne svrhe, bez eksplicitnog odobrenja autora i Računarskog centra SystemPro. ©SystemPro d.o.o. novembar 2019.
Autor članka Nikola Vukićević Za web portal www.skola-programiranja.rs Preuzeto sa sajta www.codeblog.rs uz odobrenje autora
Podelite sa prijateljima: