Forum · Codah Club

Vidakovic2010-04-21 09:23:37

Moze li mi ko objasniti rad sa velikim brojevima u C++. Interesuju me osnovne operacije sa njima (+,-,*,/).
Mail:vdragan1993@gmail.com

dario-dsa2010-04-21 10:48:58

Misliš zadatak Buka?

Vidakovic2010-04-21 15:28:27

Uopšteno. Buku sam uradio,ali nisam baš jak sa radom iz velikih brojeva.

dario-dsa2010-04-21 15:55:46

Ako ti se netko javi onda pojašnjenje ovdje objavi.

demjan00012010-04-21 18:52:20

Ajde ovde cu objasniti.

Objasnicu operacije +,-,*, jer su lake za kucanje, dok cu operaciju / objasniti samo VelikiBroj / NeVelikiBroj, jer je VelikiBroj / VelikiBroj dosta teza za kucanje i ne mogu sada to da kucam, ako stignem

jednom mogu da otkucam, a morao bi to da kucam jer ne mogu nigde da nadjem svoj kod gde to imam.

=================================================================

Veliki broj gledas kao niz cifara.
Recimo broj 123 mozemo posmatrati kao niz od 3 elementa.
tj. mozemo imati class-u BigNumber koja ce pretstavljati veliki broj


class BigNumber {
  int cif[MaxDig];
  int pCif;
 
  public:
 
  BigNumber() { memset(cif, 0, sizeof(cif)); brCif = 1; }
 
  BigNumber( int p ) {
      memset(cif, 0, sizeof(cif));
      if ( p == 0 ) { brCif = 1; }
      else {
        brCif = 0;
        while ( p > 0 ) {
          cif[ brCif++ ] = p % 10;
          p /= 10;
        }
      }
  }

   ovde cemo dodati jos funkcija ...
   void IzbrisiNule();
   void Oduzmi( BigNumber b );
   void Saberi( BigNumber b );
   void Podeli( int delilac ); //<----- ovo je deljenje velikog broja nevelikim
   void Pomnozi();
   void Ispisi();
}

i onda bi broj 123 mogao biti pretstavljen kao:

pcif = 3
cif[0] = 1
cif[1] = 2
cif[2] = 3

E zbog lakse manipulacije brojevima, bolje je da brojeve drzis unazad, znaci:

cif[0] = 3
cif[1] = 2
cif[2] = 1

=================================================================

e sada krenimo sa operacijama :D

najjednostavinija je + !
kako sabiras brojeve na papiru ?
recimo dva broja 123321 i 54329.
na papiru bi bilo:


// papir
 123321
+ 54329
-------
 177650

tako ?
E pa to isto simuliras i u programu, samo pazis na prenos.
pa kod bi izgledao nekako ovako:


void BigNumber::Saberi( BigNumber b )
{
     //da bi se broj cifara izjednacio, a posto je moguce da smo sa brojem sa manjim brojem cifara radili mnogo operacija, u nizu cif[] posle pcif elemenata mogu da budu neki bezveze brojevi, tako da ih 

stavljamo na 0
     for (int i = pcif; i < b.pcif; i++) cif[i] = 0;                      
     for (int i = b.pcif; i < pcif; i++) b.cif[i] = 0;

     pcif = max( pcif, b.pcif );
     int prenos = 0, p;
     for (int i = 0; i < pcif; i++) {
         cif[i] = ( cif[i] + b.cif[i] + prenos );
         prenos = cif[i] / 10; //<---- samo se mora paziti na prenos !
         cif[i] %= 10;
     }
     if ( prenos > 0 ) { cif[ pcif++ ] = prenos; } // prenos ne moze da sadrzi vise od jednu cifru !
}

=================================================================

sada operacija - ! ( ovde cu uzeti u obzir da uvek oduzimas veci od manjeg, jer necu uvoditi negativne brojeve, ali ako ovo skontas znaces i ono da otkucas )

i ovo ide isto kao na papiru:


// papir
 123321
- 54329
-------
  68992

samo simuliras ...

ovde cemo uvesti funkiju IzbrisiNule() koja ce izbrisati pocetne nule iz broja.


void BigNumber::IzbrisiNule()
{
     while ( pcif > 1 ) { if ( cif[pcif-1] > 0 ) break; pcif--; }
}

void BigNumber::Oduzmi( BigNumber b )
{
   for (int i = 0; i < b.pcif; i++) {
       if ( cif[i] < b.cif[i] ) { cif[i] += 10; cif[i+1]--; }  //<------------ prebaci jedan sa broja veceg nivoa ukoliko je cif[i] < b.cif[i] !!!
       cif[i] -= b.cif[i];
   }
   for (int i = 0; i < pcif-1; i++)
       if ( cif[i] < 0 ) { cif[i] += 10; cif[i+1]--; }   //<------- ovo treba uradi jer np. u slucaju 100 - 1, bi bez ovog dobili cif[0] = 9, cif[1] = -9 !!!, cif[2] = 1, a trebamo dobiti cif[0] = 9, cif[1] 

= 9, cif[2] = 0 !!!
   IzbrisiNule();  //<----------- kako na kraju niza (na pocetku broja) posle oduzimanja mogu da budu nule, treba da ih uklonimo
}

=================================================================

dolazimo do operacija * !
sta mislis kako ide ?
simuliras mnozenje ko na papiru (ovo je malo slozenije)


// papir
          123321 * 54329
----------------
         1109889   
         246642
        369963
       493284
    + 616605
----------------
      6699906609

pa evo i kod:


void BigNumber::Pomnozi( BigNumber b )
{

     BigNumber ret;
     BigNumber tr;
     int pr;
     for (int i = 0; i < pCif; i++) {
 
        tr = BigNumber(0);   //<----- rezultat kada cifru[i] drugog broja mnozimo sa celim prvim brojem
        pr = 0;
        tr.pCif = b.pCif+i;  //<----- pomeramo broj na levo jednu cifru, tj. mnozimo ga sa 10, kao na papiru
 
        for (int j = 0; j < b.pCif; j++) {
            tr.cif[i+j] = ( cif[i] * b.cif[j] + pr ) % 10;
            pr = ( cif[i] * b.cif[j] + pr ) / 10;
        }
        if ( pr > 0 ) {
            tr.cif[ tr.brCif++ ] = pr;
        }
 
        ret.Saberi( tr );
 
     }
     
     // prebaci sve iz ret u trenutni
     pcif = ret.pcif;
     for (int i = 0; i < pcif; i++)
        cif[i] = ret.cif[i];

}

To je to od mnozenja !!!

=================================================================

deljenje velikog broja nevelikim

Zamisli i ovde to radis kao na papiru!!! :D

Radi boljeg objasnjenja necu uzeti iste brojeve, kao na prethodnim primerima.


// papir
 123321 / 15 = 8221  (6)
-120
-----------
   33
  -30
  ---------
    32
   -30
  -----------
     21
    -15
  -----------
      6

pa evo koda za ovo:


void BigNumber::Podeli( int delilac )
{
     int pre = 0,k;
     for (int i = pcif-1; i >= 0; i--) {
         pre *= 10;
         k = ( pre + cif[i] ) % delilac;
         cif[i] = ( pre + cif[i] ) / delilac;
         pre = k;
     }
     IzbrisiNule();
}

E sad nisam mogao da nadjem nigde gde sam otkucao velikiBroj / velikiBroj, ali tu ide tako sto pogadjas koji broj je najbolji da udje u kolicnik, (znaci ides od 0..9 pa mnozis sa deliocem i vidis kojom

najvecom cifrom mozes da pomnozis delioc tako da ne prekoraci vrednost sa leve strane koju si spustio dole.

=================================================================

E sada ovo gore sto sam napisao nisam ni kompajlirao, tako da mozda ima neka greska (ali bi trebao da shvatis ideju), pa ti otkucaj svoje.

Evo nasao sam i moj kod za velike brojeve (koji radi, nema ni deljenje ni oduzimanje, nije mi trebalo za taj zadatak), ali nisam siguran koliko se dobro koristis operatorima, tako da sam gore napisao drugi

kod koji ne koristi operatore.


#define MaxCif 105

class BigNumber {
 
  int cif[MaxDig];
  int brCif;
 
  public:
 
  BigNumber() { memset(cif, 0, sizeof(cif)); brCif = 1; }
 
  BigNumber( int p ) {
      memset(cif, 0, sizeof(cif));
      if ( p == 0 ) { brCif = 1; }
      else {
        brCif = 0;
        while ( p > 0 ) {
          cif[ brCif++ ] = p % 10;
          p /= 10;
        }
      }
  }
 
  BigNumber( const BigNumber& b ) {
     brCif = b.brCif;
     for (int i = 0; i < brCif; i++)
       cif[i] = b.cif[i];
  }
 
  BigNumber operator + ( const BigNumber& b ) {
     BigNumber ret;
     int pr = 0;
     int br = max( brCif, b.brCif );
     ret.brCif = br;
     for (int i = 0; i < br; i++) {
         ret.cif[i] = ( cif[i] + b.cif[i] + pr ) % 10;
         pr = ( cif[i] + b.cif[i] + pr ) / 10;
     }
     if ( pr > 0 ) {
        ret.cif[ ret.brCif++ ] = pr;
     }
     return ret;
  }
 
  BigNumber operator * ( const BigNumber& b ) {
     BigNumber ret;
     BigNumber tr;
     int pr;
     for (int i = 0; i < brCif; i++) {
 
        tr = BigNumber(0);
        pr = 0;
        tr.brCif = b.brCif+i;
 
        for (int j = 0; j < b.brCif; j++) {
            tr.cif[i+j] = ( cif[i] * b.cif[j] + pr ) % 10;
            pr = ( cif[i] * b.cif[j] + pr ) / 10;
        }
        if ( pr > 0 ) {
            tr.cif[ tr.brCif++ ] = pr;
        }
 
        ret = ret + tr;
 
     }
     return ret;
  }
 
  void operator *= ( const BigNumber& b ) {
     (*this) = (*this) * b;
  }
 
  void operator += ( const BigNumber& b ) {
     (*this) = (*this) + b;
  }
 
  void Ispisi() {
      for (int i = brCif-1; i >= 0; i--)
        printf("%d",cif[i]);
      printf("\n");
  }
};

=================================================================

ovo sa operatorima mozes da koristis npr.
BigNumber a,b,c;

a = BigNumber( 123321 );
b = BigNumber( 54329 );
c = a + a * b * b;
c = c * a * b;
c.Ispisi();

dok onaj gore napisan algoritam moras da koristis ovako da bi dobio isto kao ovo malo pre opisano:
BigNumber a,b,c;

a = BigNumber( 123321 );
b = BigNumber( 54329 );
c = a;
c.Pomnozi(b);
c.Pomnozi(b);
c.Saberi(a);
c.Pomnozi(a);
c.Pomnozi(b);
c.Ispisi();

=================================================================

Zbog optimizacije mozes umesto u bazi 10 da gledas nekoj vecoj bazi, sto ce ti dosta ubrzati algoritam, tj. umesto da gledas po jednu cifru ti uzmes da u jednom polju cif[i] gledas po recimo 5 cifara, i svugde u algoritmu umesto da modujes i delis i mnozis sa 10 ti radis sa tom bazom odnosno ako ces sa 5 cifara sa 100000.

Nadam se da sam pomogao ! :D

MilosRadic2010-05-31 17:55:39

a na ovaj nacin se i u programskim jezicima sabiraju mnoze brojevi?

picsel2010-06-01 12:28:56

Naravno da ne

MilosRadic2010-06-01 12:48:21

kako se npr mnoze onda?:D

picsel2010-06-01 19:33:15

Kod se pretvara u masinski i operacije se izvrsavaju nad binarnim brojevima.
Primer mnozenja binarnih brojeva je Butov algoritam
http://en.wikipedia.org/wiki/Booth's_multiplication_algorithm

MilosRadic2010-06-02 12:41:06

znaci brze je mnozenje binarnih brojeva?el je moguce da se prevede i neki big num u binarni pa da se tako mnozi

Al3kSaNdaR2010-06-02 12:55:46

Pa naravno, samo napravis Bignum u binarnom sistemu . Delis sa 2 i pises ostatak i na kraju samo okrenes broj .

MilosRadic2010-06-02 14:52:21

e hvala sad cu malo da proguglam o tim big numovima:D

demjan00012010-06-02 15:37:11

Ne znam za to mnozenje binarnih brojeva, ali ne isplati ti se to da kucas.
Mnogo je brze i jednostavnije da se iskuca ovo gore navedeno, samo uzmes bazu recimo 10 000, mozes i vise i radice dovoljno brzo.

MilosRadic2010-06-02 16:53:52

pa sta je brze taj rad sa osnovom 10 ili ovo sa binarnom?

Al3kSaNdaR2010-06-02 17:08:22

Ne znam za binarno ali znam da sto vecu osnovu stavis da ti je brzi kod, tako da koristim 10 ^ 4 ili 10 ^ 5 ako hoces bas brz kod ...

picsel2010-06-02 17:26:09

Binarna osnova je brza za same operacije u procesoru zato sto je to "prirodna" osnova za racunare. Ali za ovakav rad sa velikim brojevima ti nemas direktnu podrsku procesora i zato je naravno, kao sto je receno, efikasnija veca osnova za ove algoritme!

MilosRadic2010-06-02 17:56:45

ok hvala:D

Vidakovic2011-02-20 10:44:31

Ako nije problem,mogu li dobiti kod gdje su samo operacije sabiranja i oduzimanja sa velikim brojevima, ali da radi ? :)

matteo1232011-02-20 12:09:22

Pa oni gore kodovi ti rade!!!

demjan00012011-02-21 18:39:28

@Vidakovic:
ja sam napisao ovaj mini tutorial da bi oni koji procitaju posle mogli sami da iskucaju
znaci procitaj to sto sam napisao, pa onda pokusaj sam da otkucas
na takmicenju neces moci da kopiras neciji kod

a inace rade svi gore navedeni kodovi, ako se ne varam ...i

boba55512011-03-01 05:28:42

Jedan relativno jednostavan algoritam za razumeti i implementirati, a zgodan je za brzo množenje velikih brojeva je http://en.wikipedia.org/wiki/Karatsuba_algorithm

Vidakovic2011-03-24 13:19:22

@demjan0001

Puno hvala na iscrpnom objašnjenju. Skontao sam "caku" i otkucao sam svoje operacije s velikim brojevima preko stringova!