Keskustelu: Ohjelmointikysymykset: C++: 128-bittinen kokonaisluku

Osaisiko kukaan kertoa, kuinka voisin tehdä 128-bittisen etumerkittömän kokonaislukumuuttujan, joka kykenee suorittamaan peruslaskutoimituksia?
Kuinka voisin tähän muuttujaan muuten lukea std:n cinillä arvon?
Onko tavoite todella haastava vai onko se vain muutaman kymmenen koodirivin päässä?

Ei se kohtuuttoman haastava ole... Riippuu siitä, mitä odotat noilta luvuiltasi. Perustoimitukset menevät vielä ihan helposti. Heitänpä nyt tähän pikaisen esimerkin:

class TLuku
{
public:
  unsigned long A, B, C, D; /* D = Merkitsevin, A = vähiten merkitsevä */
  void Lisaa(TLuku *X);
  void Vahenna(TLuku *X);

  void Aseta(unsigned long _D, unsigned long _C, unsigned long _B, unsigned long _A)
    {A = _A; B = _B; C = _C; D = _D;};

  TLuku() {A=B=C=D=0;};
  ~Luku(){};
};

TLuku::Lisaa(TLuku *X)
{
  unsigned long Apu1, Apu2;

  Apu1 = A;
  A += X->A;
  Apu2 = B;
  B += X->B + (A < Apu1 ? 1 : 0); /* Jos Apu < A, on tapahtunut "kymmenylitys" */
  Apu1 = C;
  C += X->C + (B < Apu2 ? 1 : 0);
  Apu2 = D;
  D += X->D + (C < Apu1 ? 1 : 0);

  if (D < Apu2) cout << "Ei mahtunut!\n";
}

TLuku::Vahenna(TLuku *X)
{
  unsigned long Apu1, Apu2, Apu3, Apu4;

  Apu4 = D;
  D -= X->D;

  Apu3 = C;
  C -= X->C;
  if (Apu3 < C) D--; /* Lainaus merkitsevämmistä numeroista */

  Apu2 = B;
  B -= X->B;
  if (Apu2 < B) C--;
  if (Apu3 < C) D--;

  Apu1 = A;
  A -= X->A;
  if (Apu1 < A) B--;
  if (Apu2 < B) C--;
  if (Apu3 < C) D--;

  if (Apu4 < D) cout << "Negatiivinen!\n";
  /* Tämän voisi tarkistaa joka välissä */
}

Tuolta pohjalta voisit osata tehdä kerto- ja jakolaskutkin. Lukeminen cin-oliosta toimii niin, että luet tavalla tai toisella luvut "unsigned long" -olioihin ja siirrät niistä. Ei mikään helppo juttu välttämättä, koska pitää huomioida heksa- ja kymmenjärjestelmien ero:
4294967295 mahtuu yhteen unsigned long-muuttujaan.
4294967296 ei mahdu.
Kirjoitan tuon tapaisen muuttujan jossakin vaiheessa ihan kunnolla, mutta nyt en oikein jaksa, onhan kello sentään 1:20.

On se niin vaikeaa kirjoittaa koodia suoraan tuohon viestinkirjoitusruutuun... Sitä voisi suurentaa vähän. Toivottavasti ei tullut virheitä.

Oletan nyt koko ajan, että unsigned long on 32-bittinen, kuten se toistaiseksi tavallisella kotikoneella on. Kenenkään on siis turha tulla halkomaan hiuksia sen koosta, vaikka se jollakin arkkitehtuurilla olisikin 64-bittinen tai jotakin muuta.

Kiitos. Tuosta osaankin jo soveltaa.

Gnu Multiple Precision Arithmetic library on avoimen lähdekoodin projekti, jossa on valmiina nopeat isojen kokonaislukujen käsittelyyn tarvittavat funktiot. http://www.swox.com/gmp/

Tuo onkin erittäin hyödyllinen kirjasto!
Vaikutti erittäin laadukkaalta.

Tämä nyt on kyllä ihan turha viesti, mutta ihmettä sinä 128-bittisellä luvulla teet? Siihenhän mahtuu ainakin luvut 0-miljardi(en tiedä kuinka paljon siihen mahtuu, mutta se kuvastaa sen suuruutta. Siis olettaen että siinä ei ole etumerkkiä.

Ja eikös muuttujat yleensä määritellä privateiksi? Näin ainakin minä teen ja eikös se ole hyvän ohjelmointi tavan mukaista? Tai näin ainakin minä olen ymmärtänyt. Eli koodi menisi:

class TLuku
{
private:
  unsigned long A, B, C, D; /* D = Merkitsevin, A = vähiten merkitsevä */
public:
  void Lisaa(TLuku *X);
  void Vahenna(TLuku *X);

  void Aseta(unsigned long _D, unsigned long _C, unsigned long _B, unsigned long _A)
    {A = _A; B = _B; C = _C; D = _D;};

  TLuku() {A=B=C=D=0;};
  ~Luku(){};
};

//ohjelma koodi...

TLuku::Lisaa(TLuku *X)
{
  unsigned long Apu1, Apu2;

  Apu1 = A;
  A += X->A;
  Apu2 = B;
  B += X->B + (A < Apu1 ? 1 : 0); /* Jos Apu < A, on tapahtunut "kymmenylitys" */
  Apu1 = C;
  C += X->C + (B < Apu2 ? 1 : 0);
  Apu2 = D;
  D += X->D + (C < Apu1 ? 1 : 0);

  if (D < Apu2) cout << "Ei mahtunut!\n";
}

TLuku::Vahenna(TLuku *X)
{
  unsigned long Apu1, Apu2, Apu3, Apu4;

  Apu4 = D;
  D -= X->D;

  Apu3 = C;
  C -= X->C;
  if (Apu3 < C) D--; /* Lainaus merkitsevämmistä numeroista */

  Apu2 = B;
  B -= X->B;
  if (Apu2 < B) C--;
  if (Apu3 < C) D--;

  Apu1 = A;
  A -= X->A;
  if (Apu1 < A) B--;
  if (Apu2 < B) C--;
  if (Apu3 < C) D--;

  if (Apu4 < D) cout << "Negatiivinen!\n";
  /* Tämän voisi tarkistaa joka välissä */
}

Koipio-ohjelma kirjoitti:

Siihenhän mahtuu ainakin luvut 0-miljardi(en tiedä kuinka paljon siihen mahtuu, mutta se kuvastaa sen suuruutta. Siis olettaen että siinä ei ole etumerkkiä.

Kaks potenssiin 128, eli luku, joka alkaa 34 ja jatkuu 37:llä muulla numerolla :)

Edit: siis noin 34 miljoonaa kvintiljoonaa :)
(Lähde: http://koti.mbnet.fi/henrihe/tiede/suuretluvut.html)

Joo noin on. Laskeminen on sinänsä mukavaa, mutta ei noin isojen lukujen, joten en viittinyt laskea sitä. Ja se arvaus meni hieman alakanttiin, mutta se tekee vielä yhden kysymyksen: Mitä tuollaisella luvulla tekee? En minä ainakaan keksi mitään sovellusta joka tuollaisia lukuja tarttee, paitsi ehkä joku älyttömän monimutkainen fysiikka moottori tai jokin...

Kopioi-ohjelma kirjoitti:

Ja eikös muuttujat yleensä määritellä privateiksi? Näin ainakin minä teen ja eikös se ole hyvän ohjelmointi tavan mukaista? Tai näin ainakin minä olen ymmärtänyt. Eli koodi menisi: ...

Yleensähän ne tosiaan on tapana määritellä privateksi (minulla ei, koska ei siitä julkisuudesta haittaakaan ole), mutta jos ne tuossa määriteltäisiin privateiksi, niitä ei voitaisi noissa Lisaa- ja Vahenna-funktioissa lukea toisesta luvusta (TLuku *X), ja uskoisin, että koodi toimii noin nopeammin kuin jos kukin jäsen haettaisiin jäsenfunktiolla:
unsigned int GetA() {return A;};
jne.

Kryptografiassa tarvitaan suuria kokonaislukuja. Ainakin RSA:ssa. Samoin kuin lukuteoriassa.

Metabolix kirjoitti:

Yleensähän ne tosiaan on tapana määritellä privateksi (minulla ei, koska ei siitä julkisuudesta haittaakaan ole), mutta jos ne tuossa määriteltäisiin privateiksi, niitä ei voitaisi noissa Lisaa- ja Vahenna-funktioissa lukea toisesta luvusta (TLuku *X), ja uskoisin, että koodi toimii noin nopeammin kuin jos kukin jäsen haettaisiin jäsenfunktiolla.

Niinhän minäkin ennen luulin, kunnes karu totuus selvisi. Todellisuudessa privaattius on luokkakohtaista eikä oliokohtaista, ja luokan metodit/funktiot pääsevät käsiksi parametrina välitetyn saman luokan olion tietoihin aivan kuin ne olisivat julkisia. Näin asia on C++:n lisäksi myös ainakin Javassa.

Kyseistä lukua aion soveltaa juuri salauksessa, lukuteoriassa, sekä ennen kaikkea eräässä ensimmäisistä c-ohjelmistani. Kyseinen yksinkertainen ohjelma tutkii, onko luku alkuluku. Haluaisin nyt kuitenkin pitkän ajan jälkeen laajentaa ohjelmaa tukemaan myös huomattavasti suurempia lukuja.