Ovo je prvi u seriji tutoriala iz programiranja čiji cilj nije da u potpunosti i bez greške obrade neku tematiku, već da programera uvedu u određen način razmišljanja koji je potreban za rešavanje dotičnog problema. Osnovno poznavanje programskog jezika se podrazumeva. Ostale tutoriale možete naći pretragom po odgovarajućem tagu.
U najrasprostranjenijim programskim jezicima rad sa celim brojevima je ograničen kako arhitekturom računara, tako i samim jezikom. Jedan od najčešćih problema sa ovim jeste maksimalna vrednost koju možemo sačuvati u memoriji kada radimo sa celim brojevima. Uzevši u obzir rasprostranjenost 64-bitnih arhitektura, može se slobodno reći da je raspon koji ceo broj može da pokrije od 9.223.372.036.854.775.808 do 9.223.372.036.854.775.807 kada se radi sa negativnim brojevima, odnosno od 0 do 18.446.744.073.709.551.615 kada se radi samo sa pozitivnim – tačnije, 264 različitih brojeva.
Korišćenjem floating-point brojeva mogu se zapisati i veće vrednosti, ali ovaj format, zbog načina čuvanja u memoriji, ne pokriva ravnomerno skup brojeva, pa se neke vrednosti ni ne mogu zapisati, a u svakom slučaju ne mogu da se predstave apsolutno svi celi brojevi. Iz tog razloga ovo nećemo razmatrati kao rešenje.
U većini slučajeva, 264 vrednosti je sasvim dovoljno, ali čim se dođe do nekih ozbiljnijih primena i operacija nad velikim podacima, svi osnovni tipovi podataka su neupotrebljivi. Međutim, ono što se može uraditi jeste čuvati brojeve kao niz (decimalnih) cifara – najjednostavnije, ali i čoveku najprirodnije rešenje. Oni koji programiraju u Javi sigurno znaju da ovaj jezik već ima klasu BigInteger za rad sa velikim brojevima, a na Internetu postoji mnogo klasa i za druge jezike koje su sigurno bolje od ove. Međutim, kao što sam naveo na početku teksta, ja vas samo uvodim u problem i pružam osnovnu ideju. Na vama je da je posle bolje istražite, razradite i usavršite. S obzirom da se ne smatram stručnjakom svi predlozi za unapređenje kôda su dobrodošli.
Tekst će se sastojati iz nekoliko delova, ali ne poređanih po kompleksnosti, već na osnovu celina koje svaki od njih formira.
Klasa: promenljive i funkcije
Prvi deo ovog tutoriala će se baviti najosnovnijim aspektima klase – konstruktorima, sabiranjem, oduzimanjem i množenjem. Deljenje ostavljamo za kasnije, pošto rezultat ne mora da bude ceo broj.
Za početak, potrebno je da odlučimo kako ćemo čuvati broj u memoriji. Pošto ne možemo da znamo koliko će broj imati cifara, koristićemo vector, i to sa sledećim osobinana:
- svaki element vektora će predstavljati jednu cifru broja
- prvi element vektora će biti cifra najmanje težine, odnosno cifra jedinice
- svaku cifru ćemo čuvati kao char, ali posmatrati kao broj, jer char zauzima najmanje memorije
- dužina vektora će biti broj cifara broja, osim u slučaju broja nula, kada vektor neće biti prazan, već se sadržati jednu cifru
Pored (apsolutne) vrednosti broja, potreban nam je i njegov znak, što ćemo čuvati u promenljivoj tipa bool – true za pozitivan broj, a false za negativan. Nulu ćemo tretirati kao pozitivan broj. Osim funkcija za konstruktore i osnovne aritmetičke operacije, obezbedićemo i još neke da bismo olakšali rad.
Trenutno naša klasa izgleda ovako, i takva će ostati u prvom delu tutoriala:
#include <iostream>
#include <vector>
#include <string>
using namespace std;
class VelikiBroj
{
private:
vector<char> _cifre;
bool _znak;
void postaviNaNulu(); // Resetovanje vrednosti broja na 0
void ukloniVodeceNule(); // Brisanje nula sa pocetka broja
public:
VelikiBroj(); // Default konstruktor koji broj postavlja na nulu
VelikiBroj(int); // Konstruktor na osnovu broja
VelikiBroj(const string); // Konstruktor na osnovu stringa
void izIntegera(int); // Funkcija za formiranje broja iz integera
void izStringa(string); // Funkcija za formiranje broja iz stringa
string uString() const; // Funkcija koja vraca broj kao string
VelikiBroj saberi(const VelikiBroj&) const;
VelikiBroj oduzmi(const VelikiBroj&) const;
VelikiBroj pomnozi(const VelikiBroj&) const;
};
Konstruktori
Pošto smo uveli pomoćne funkcije, konstruktori su dosta jednostavni:
VelikiBroj::VelikiBroj()
{
this->postaviNaNulu();
}
VelikiBroj::VelikiBroj(int broj)
{
this->izIntegera(broj);
}
VelikiBroj::VelikiBroj(const string broj)
{
this->izStringa(broj);
}
Pomoćne funkcije
Funkcije koje slede se koriste u konstruktorima klase, ali i u funkcijama za aritmetičke operacije, koje će biti objašnjene kasnije.
postaviNaNulu()
Ova funkcija postavlja vrednost broja na nulu, nezavisno od njegovog prethodnog sadržaja, pa se time gubi ta prethodna vrednost. Koristi se kod default konstruktora.
void VelikiBroj::postaviNaNulu()
{
this->_cifre.clear();
this->_cifre.push_back(0);
this->_znak = true;
}
izIntegera( int )
Ova funkcija formira veliki broj na osnovu običnog integera. Ona u petlji računa ostatak pri deljenju sa 10, što je krajnja desna cifra, i dodaje je u vektor.
void VelikiBroj::izIntegera(int broj)
{
char cifra;
// Odredjujemo znak broja
if (broj < 0)
{
this->_znak = false;
broj = -broj;
}
else
{
this->_znak = true;
}
this->_cifre.clear(); // Brisemo sve cifre
while (broj != 0)
{
cifra = broj % 10; // Uzimamo krajnu desnu cifru broja
this->_cifre.push_back(cifra); // Ubacujemo je u nas vektor
broj /= 10;
}
}
izStringa( string )
Funkcija za formiranje broja iz zadatog stringa. Ukoliko string nije odgovarajućeg oblika, broj se postavlja na nulu. (Odgovarajući oblik: opcionalan znak nakon kog sledi barem jedna cifra).
void VelikiBroj::izStringa(string broj)
{
this->_cifre.clear();
this->_znak = true;
int pocetakBroja = 0;
int krajBroja = broj.length() - 1;
if (krajBroja < 0) // Ako je string prazan
{
this->postaviNaNulu();
return;
}
if (broj[0] == '+') // Ako je pozitivan broj
pocetakBroja++;
if (broj[0] == '-')
{
this->_znak = false;
pocetakBroja++;
}
if (krajBroja < pocetakBroja) // Ako nema nijedne cifre
{
this->postaviNaNulu();
return;
}
// Ubacujemo cifre pocevsi od krajnje desne
for (int i = krajBroja; i >= pocetakBroja; i--)
{
if (broj[i] > '9' || broj[i] < '0') // Ako nije cifra
{
this->postaviNaNulu();
return;
}
this->_cifre.push_back(broj[i] - '0');
}
// Ako je korisnik uneo vodece nule
this->ukloniVodeceNule();
}
ukloniVodeceNule()
Kao posledica nekih aritmetičkih operacija, može se dogoditi da broj sačuvan u memoriji bude “0000015167”, a mi želimo da on bude “15167”. Pošto je u vektoru broj zapisan unazad, kroz njega prolazimo sa desna na levo, smanjujući dužinu sve dok nailazimo samo na nule. Prvi uslov u while petlji je tu da bismo ostavili bar jednu cifru u slučaju da je vrednost broja nula. Ova funkcija se poziva na kraju “problematičnih” aritmetičkih operacija.
void VelikiBroj::ukloniVodeceNule()
{
int brCifara = this->_cifre.size();
while (brCifara > 1 && this->_cifre[brCifara-1] == 0)
brCifara--;
this->_cifre.resize(brCifara);
// Ako smo dosli do -0, moramo da promenimo znak
if (this->_cifre.size() == 1 && this->_cifre[0] == 0)
this->_znak = true;
}
uString()
Funkcija koja vraća broj kao string, da bi mogao da se ispiše.
string VelikiBroj::uString() const
{
string s;
if (!this->_znak) s += '-'; // Dodajemo minus ako je potrebno
int i = this->_cifre.size();
while (i > 0)
{
i--;
s += (char)(this->_cifre[i] + '0');
}
return s;
}
Aritmetičke operacije
Sabiranje
Iako najosnovnija operacija, sabiranje je zapravo najteže realizovati. Da klasa radi samo sa pozitivnim celim brojevima, mogli bismo da ih sabiramo kao na papiru (ako se pored računara danas iko toga seća), ali zbog postojanja i negativnih brojeva, ovaj jednostavan metod ne funkcioniše. Naravno, i za to postoji rešenje.
Ako su brojevi istog znaka, sabiraćemo ih kao na papiru. Ako nisu, postavićemo ih tako da pozitivan broj bude prvi, a negativan broj drugi sabirak, i onda ćemo ih sabrati, odnosno oduzeti njihove apsolutne vrednosti kao na papiru. Ako je prvi broj veći ili jednak drugom, rešenje će biti pozitivno, i tu se završava funkcija. Međutim, ako je prvi manji od drugog, rešenje će biti negativno, pa će se na kraju oduzimanja javiti prenos, koji će nam staviti do znanja da treba da “obrnemo” (ako broj ima N cifara, oduzimamo ga od 104) rezultat da bismo dobili odgovarajući negativan broj.
VelikiBroj VelikiBroj::saberi(const VelikiBroj& broj) const
{
VelikiBroj rezultat;
// Ako su brojevi istog znaka, mozemo raditi kao na papiru
if (this->_znak == broj._znak)
{
rezultat._znak = this->_znak;
int aVelicina = this->_cifre.size();
int bVelicina = broj._cifre.size();
int velicina = max(aVelicina, bVelicina);
rezultat._cifre.resize(velicina);
char prenos = 0; // X pisem, PRENOS pamtim
char zbir;
for (int i = 0; i < velicina; i++)
{
// Moramo da pazimo ako je jedan broj duzi od drugog
zbir = ( (i < aVelicina) ? this->_cifre[i] : 0 )
+ ( (i < bVelicina) ? broj._cifre[i] : 0 )
+ prenos;
rezultat._cifre[i] = zbir % 10;
prenos = zbir / 10;
}
if (prenos > 0)
rezultat._cifre.push_back(prenos);
rezultat._znak = this->_znak;
}
else // A ako nisu, radimo komplementiranjem
{
rezultat._znak = true;
const VelikiBroj *prvi, *drugi;
// Pozitivan broj mora da bude prvi sabirak
if (this->_znak)
{
prvi = this;
drugi = &broj;
}
else
{
prvi = &broj;
drugi = this;
}
int aVelicina = prvi->_cifre.size();
int bVelicina = drugi->_cifre.size();
int velicina = max(aVelicina, bVelicina);
rezultat._cifre.resize(velicina);
char prenos = 0;
char razlika;
for (int i = 0; i < velicina; i++)
{
razlika = ( (i < aVelicina) ? prvi->_cifre[i] : 0 )
- ( (i < bVelicina) ? drugi->_cifre[i] : 0 )
+ prenos;
razlika += 10;
rezultat._cifre[i] = razlika % 10;
prenos = razlika / 10 - 1;
}
if (prenos < 0) // Obrcemo broj
{
prenos = 0;
for (int i = 0; i < velicina; i++)
{
razlika = 0 - rezultat._cifre[i] + prenos;
razlika += 10;
rezultat._cifre[i] = razlika % 10;
prenos = razlika / 10 - 1;
}
rezultat._znak = false;
}
}
rezultat.ukloniVodeceNule();
return rezultat;
}
Oduzimanje
Oduzimanje možemo posmatrati kao sabiranje, samo drugom broju promenimo znak.
VelikiBroj VelikiBroj::oduzmi(const VelikiBroj& broj) const
{
VelikiBroj pomocni = broj; // Konstruktor kopije
pomocni._znak = !pomocni._znak; // Menjamo znak
return this->saberi(pomocni);
}
Množenje
Množenje je prilično jednostavno: prvo alociramo maksimalan potreban broj cifara, i onda za cifru I prvog činioca i cifru J drugog činioca odredimo koju cifru u rezultatu oni fomiraju, pazeći na prenos.
VelikiBroj VelikiBroj::pomnozi(const VelikiBroj& broj) const
{
VelikiBroj rezultat;
// Odredjujemo znak
// + ako su oba cinioca istog znaka
rezultat._znak = (this->_znak == broj._znak);
// Odredjujemo koliko cifara moze da ima rezultat
int aVelicina = this->_cifre.size();
int bVelicina = broj._cifre.size();
rezultat._cifre.resize(aVelicina + bVelicina);
// Racunamo rezultat
char temp;
for (int i = 0; i < aVelicina; i++)
for (int j = 0; j < bVelicina; j++)
{
temp = rezultat._cifre[i+j]
+ this->_cifre[i] * broj._cifre[j];
rezultat._cifre[i+j] = temp % 10;
rezultat._cifre[i+j+1] += temp / 10;
}
// Uklanjamo vodece nule
rezultat.ukloniVodeceNule();
// Vracamo rezultat
return rezultat;
}
Finalni kôd
Sa svim ovim funkcijama, osnovna verzija klase je završena, a već ima sve bitne operacije, osim deljenja. Ceo kôd prve verzije klase možete skinuti ovde, a test program možete videti ovde. Ukoliko, pak, naiđete na neki bag, ostavite komentar da bih ga ispravio.
Sledeći tekst vezan za klasu VelikiBroj će se baviti se bavi deljenjem, kao i još nekim aritmetičkim operacijama.