Ukoliko do ovog teksta niste došli sa prvog dela tutoriala, verujem da bi najsmislenije bilo prvo njega pročitati.

U prvom tekstu koji se bavi velikim brojevima odrađeni su najosnovniji elementi klase, konstruktori, ali i tri aritmetičke operacije – sabiranje, oduzimanje i množenje. Međutim, deljenje je izostavljeno, zbog svoje specifičnosti, pa ga obrađujem tek u ovom delu tutoriala.

Kako naša klasa radi isključivo sa celim brojevima, deljenje će funkcionisati isto kao i deljenje dva integera – tačnije, rezultat će takođe biti ceo broj, pa će ovo biti celobrojno deljenje. Ukoliko rezultat operacije deljenja nije ceo broj, naša klasa će posmatrati samo deo broja pre decimalnog zareza, odnosno zaokružiće vrednost broja ka nuli.

Za slučaj da nije jasno, sledi nekoliko primera:

  • 6 / 3 = 2
  • 7 / 3 = 2
  • -10 / 3 = -3
  • -15 / -6 = 2
  • 24 / 0 = greška – deljenje nulom nije dozvoljeno

Ali prvo, da bismo olakšali proces deljenja, uvedimo dve funkcije za poređenje velikih brojeva.

Poređenje brojeva

Iako je poređenje dva velika broja moguće bez problema realizovati uz pomoć samo jedne funkcije, ja ću nju razbiti na dva dela, odnosno dve funkcije, od kojih će jedna da nam znači pri deljenju.

uporediApsolutne()

Kao osnovu za poređenje dva broja, prvo ćemo napisati funkciju koja poredi dva broja po njihovoj apsolutnoj vrednosti, odnosno ne posmatra znak. Pošto nas ne zanima da li je broj negativan ili ne, lako možemo na osnovu broja cifara odrediti koji je veći:

  • ukoliko prvi (onaj za koji pozivamo funkciju) ima više cifara, on je veći
  • ukoliko drugi ima više cifara, on je veći
  • ukoliko imaju isti broj cifara, posmatramo brojeve počevši od krajnje leve cifre sve dok ne naiđemo na cifru koja se razlikuje, i na osnovu nje određujemo koji je veći, odnosno da li su jednaki

Povratni tip funkcije je integer, i to sa sledećim vrednostima:

  • -1 ako je prvi broj manji
  • +1 ako je prvi veći manji
  • 0 ako su brojevi jednaki

Ja to volim da posmatram kao smer u kome “pokazuje” znak nejednakosti – levo je -1, a desno je +1.

int VelikiBroj::uporediApsolutne(const VelikiBroj& b) const
{
    int brCifA = this->_cifre.size();
    int brCifB = b._cifre.size();

    // Ako jedan ima vise cifara, ocigledno je veci

    if (brCifA < brCifB) return -1;
    if (brCifA > brCifB) return 1;

    // Imaju isti broj cifara, pa ih redom poredimo

    for (int i = brCifA-1; i >= 0; i--)
        if (this->_cifre[i] != b._cifre[i])
            return (this->_cifre[i] < b._cifre[i]) ? -1 : 1;

    // Ukoliko su im sve cifre jednake

    return 0;
}

uporedi()

Sada kad imamo funkciju za poređenje apsolutnih vrednosti broja, lako je implementirati i funkciju za poređenje označenih brojeva.

int VelikiBroj::uporedi(const VelikiBroj& b) const
{
    // Ako nisu istog znaka, lako je odrediti

    if (this->_znak != b._znak)
        return (this->_znak) ? 1 : -1;

    // Ako su istog znaka, poredimo apsolutne vrednosti
    // i u zavisnosti od znaka vrsimo negaciju rezultata

    int poredjenje = this->uporediApsolutne(b);

    if (!this->_znak) poredjenje = -poredjenje;

    return poredjenje;
}

Deljenje

Kao prvo, jedno upozorenje. Sledeći algoritam je veoma neefikasan. Ali veoma neefikasan. Zašto ga onda pišem? Zato što predstavlja najosnovniju implementaciju algoritma za deljenje velikih brojeva. Kada se budem bavio optimizacijom svih ovih funkcija, na red će doći i deljenje, ali ovo je dovoljno za početak.

Koji je to neefikasan algoritam? Postepeno oduzimanje delioca od deljenika, sve dok je prvi veći od drugog po apsolutnoj vrednosti – i tu na scenu stupa prva funkcija iz ovog teksta. Kompjuteri danas jesu brzi, ali niko ne želi da deljenje dva broja traje više sekundi. Osim nas. Jedina optimizacija koju ćemo izvršiti jeste množenje delioca sa stepenom broja deset da bismo mu dodali nule na kraj i što više ga “približili” deljeniku.

Algoritam će prvo proveriti da li je rezulat nula ili jedan, odrediti znak, i tek onda se baciti na računanje. Pritom ćemo vraćati izuzetak ukoliko je delilac nula.

VelikiBroj VelikiBroj::podeli(const VelikiBroj& broj) const
{
	VelikiBroj rezultat;

	// Ukoliko je delilac nula, to nije dozvoljeno
	// pa izbacujemo izuzetak

	if (broj.uporedi(rezultat) == 0)
		throw "Deljenje nulom";

	// Proveravamo da li je deljenik manji ili jednak
	// deliocu po apsolutoj vrednosti

	int poredjenje = this->uporediApsolutne(broj);

	// Ukoliko je manji, vracamo nulu

	if (poredjenje == -1) return rezultat;

	// Ukoliko su jednaki, vracamo jedinicu sa
	// odgovarajucim znakom

	if (poredjenje == 0)
	{
		if (this->_znak == broj._znak)
			rezultat.izIntegera(1);
		else
			rezultat.izIntegera(-1);

		return rezultat;
	}

	// Deljenik je veci, pa moramo da oduzimamo

	VelikiBroj pomocni;
	VelikiBroj jedan(1);

	rezultat._znak = (this->_znak == broj._znak);
	jedan._znak = rezultat._znak;

	int brCifA = this->_cifre.size();
	int brCifB = broj._cifre.size();

	// Ukoliko deljenik ima dve ili vise cifre

	if (brCifA - brCifB > 1)
	{
		for (int i = brCifA - brCifB; i > 2; i--)
			rezultat._cifre.push_back(0);

		rezultat._cifre.push_back(1);

		pomocni = rezultat.pomnozi(broj);
	}

	// Vrsimo oduzimanje

	while (true)
	{
		if (this->_znak == broj._znak)
			pomocni = pomocni.saberi(broj);
		else
			pomocni = pomocni.oduzmi(broj);

		if (pomocni.uporediApsolutne(*this) <= 0)
			rezultat = rezultat.saberi(jedan);
		else
			break;
	}

	return rezultat;
}

Testiranje

Kao i prošli put, obavio sam i kratko testiranje novih mogućnosti klase.

Originalni test primeri su sadržali deljenje broja 10000000000000000000 brojem 123, ali se ispostavilo da je to previše naporan posao za naše jednostavno deljenje. Dakle, kao što sam rekao, veoma neefikasno.

Dopunjenu verziju klase možete skinuti ovde. Sledeći tekst će se baviti se bavi implementacijom operatora.