Hvordan behandle store tall?

[Zethyr]

Hvordan kan jeg få lagret tall som er veldig store, som f.eks. 2^1000 ? Dette krever så vidt jeg ser en 1000 bits datatype; finnes det noen måte å gjøre dette på?

 

unsigned double er vel den største standarddatatypen så vidt jeg vet?

[prebenl]

Eller du kan lagre det slikt:

 

struct eksponent

{

int n;

int x;

};

 

eksponent a;

a.n = 2;

a.x = 1000;

Endret 1. juli 2005 av Geofrank

[Zethyr]

Eller du kan lagre det slikt:

 

struct eksponent

{

int n;

int x;

};

 

eksponent a;

a.n = 2;

a.x = 1000;

Jeg trenger tilgang til alle sifre i tallet, så da nytter dessverre ikke det

[Herr_Dude]

Du kan jo lagre det i en tabell der første posisjon er det mest signifikante.

 

F.eks:

 

1000 ->

 

array[0] = 1

array[1] = 0

array[2] = 0

array[3] = 0

[Zethyr]

Hummm... den var vrien. Hvordan kan jeg da finne siffer 32-64 av et tall, f.eks.?

[Dead_Rabbit]

Kansje du kunne lagd en klasse, noe alà dette:

template<class T = double>
class LargeNum {

   friend ostream& operator<<(ostream&, LargeNum<T>&);

   public:
       LargeNum();
       LargeNum(const string&);
       LargeNum(const T&);

       T operator=(const T&);
       T operator+(const T&);
       T operator-(const T&);
       //osv.
   private:
       vector<T> vt;
}

ostream& operator<<(ostream&, LargeNum<T>&);

Vet ikke om dette vil funke, men.. Var bare det første og beste jeg kom på

[☀ ❄]

zirener: std::bitset ville kanskje vært bedre egnet til å være den underliggende datastrukturen?

[Legion]

sett på GMP?

http://www.swox.com/gmp/index.orig.html

[Zethyr]

Oi, jeg tror jeg bør lese litt mer før jeg frisker opp kodinga vha praktiske oppgaver \o/

[prebenl]

zirener: std::bitset ville kanskje vært bedre egnet til å være den underliggende datastrukturen?

Hva med å bruke en enum med sifrene 0-9 i en vektor? Hadde ikke det vært enklere å bruke?

[Dead_Rabbit]

Jo, std::bitset er vel kansje bedre å bruke i denne sammenhengen. Men vi kan jo forsåvidt la brukeren ha det siste ordet:

template<class T = double, class U = std::bitset>
class LargeNum {

  friend ostream& operator<<(ostream&, LargeNum<T>&);

  public:
      LargeNum();
      LargeNum(const string&);
      LargeNum(const T&);

      T operator=(const T&);
      T operator+(const T&);
      T operator-(const T&);
      //osv.
  private:
      U<T> vt;
}

ostream& operator<<(ostream&, LargeNum<T>&);

[prebenl]

Ville det ikke gitt mer mening å bruke en bitset<4>, og angi tallene heksadesimalt. Er det mulig å lage et bitset<T>? Tenkte bitset skulle være angitt med et konstant heltall, så man må vel legge det i en container, f.eks. vector.

 

Og ville ikke en vector<dec>, der dec er en enum fra 0-9 vært bedre, for å få bruke titallsystemet?

 

Eventuelt kunne man gjort forskjellige tallsystemer tilgjengelig.

Er jeg helt på jordet nå?

Endret 1. juli 2005 av Geofrank

[☀ ❄]

Ville det ikke gitt mer mening å bruke en bitset<4>, og angi tallene heksadesimalt.

Å ha en tall-type med 15 som høyeste verdi ødelegger vel hensikten med å lage en egen type for høye tall? Eller mener du å ha flere bitset<4>? Uansett, hvorfor dele dem opp?

 

Er det mulig å lage et bitset<T>? Tenkte bitset skulle være angitt med et konstant heltall, så man må vel legge det i en container, f.eks. vector.

std::bitset tar ett template-parameter, og det er antall bit den skal holde. Det betyr at for 1000-bits-verdien det var snakk om kan man lage en type med f.eks. bitset<1024> i bakgrunnen, slik at man kan ha tall med verdier opp til 2^1024-1 (eller

179 769 313 486 231 590 772 930 519 078 902 473 361 797 697 894 230 657 273 430 081 157 732 675 805 500 963 132 708 477 322 407 536 021 120 113 879 871 393 357 658 789 768 814 416 622 492 847 430 639 474 124 377 767 893 424 865 485 276 302 219 601 246 094 119 453 082 952 085 005 768 838 150 682 342 462 881 473 913 110 540 827 237 163 350 510 684 586 298 239 947 245 938 479 716 304 835 356 329 624 224 137 215 om du vil).

 

Og ville ikke en vector<dec>, der dec er en enum fra 0-9 vært bedre, for å få bruke titallsystemet? Eventuelt kunne man gjort forskjellige tallsystemer tilgjengelig.

Husk på at den binære representasjonen abstraheres bort av medlemsfunksjoner og overlastede operatorer. Det betyr at brukeren av klassen fint kan bruke tall i base-10, evt. andre tallsystemer man vil ha støtte for.

[prebenl]

Å ha en tall-type med 15 som høyeste verdi ødelegger vel hensikten med å lage en egen type for høye tall? Eller mener du å ha flere bitset<4>? Uansett, hvorfor dele dem opp?

Som jeg nevnte, hadde jeg tenkt å legge dem i en vektor. Grunnen til at jeg ville dele dem opp er å spare minne dersom tallet "bare" er 512-bits, samt ha mulighet til å lagre 2048-bits tall dersom behovet skulle oppstå. Slik ville klassen blitt mer generell.

 

Husk på at den binære representasjonen abstraheres bort av medlemsfunksjoner og overlastede operatorer. Det betyr at brukeren av klassen fint kan bruke tall i base-10, evt. andre tallsystemer man vil ha støtte for.

Jepp, selvfølgelig.

[knuto]

Ein kan vel berre ta ein pause i programmering og sitje å vente på at eit standardbibliotek skal kome og løyse problemet med store tal Det skjedde jo når det vart vanskeleg med char. Då kom string

[JBlack]

Først må problemstillingen defineres litt bedre.

 

For det første er det forskjell på et talls størrelse og et talls oppløsning og presisjon.

 

For eksempel kan en enkelt byte lagre tall som er vilkårlig store. Det er bare et spørsmål om å definere hva bitene representerer. Men selv om tallet er vilkårlig stort, så er presisjonen bare på 8 bit. Man kan ha en fast presisjon slik at verdien i byte'en ganges med et vilkårlig tall for å gi den verdien den representerer. Eller man kan ha en flytende presisjon slik som i flyttall.

 

Så når man har klarhet i om man mener store tall eller høy presisjon så kan men stille neste spørsmål. Hva skal man med det 'store' tallet? Bare lagre det i en variabel eller struktur, eller skal man benytte den i matematiske oppgaver. I første tilfelle kan man bare opprette en struktur stor nok til å ta vare på den. I andre tilfelle bør man se seg om etter et ferdig bibliotek som håndterer store tall, da det er liten vits i å finne opp hjulet på nytt når det gjelder noe slikt.

[Zethyr]

Jeg trenger 1000 bits presisjon, trenger ikke være flytende. (Er et vanlig heltall). La oss si at jeg gir det følgende oppgave; finn siffer nummer 250 i 2^1000 (siden jeg hadde 2^1000 som eksempel). Om jeg ikke tar feil skulle dette har cirka 300 siffer omgjort til 10-tallssystemet.

[JBlack]

Mitt forslag. Kan muligens gjøres smartere med typedef.

 

Du skrev ikke om du mente siffer nummer 250 binært eller desimalt, så jeg valgte binært.

 

#define RES_BITS 1000
#define LITTLE_ENDIAN
#define TEST
#include <iostream>
using namespace std;

class HighRes{

public:
char * data;

private:
int arraysize;
int res;

private:
HighRes(){
}
public:

HighRes(int nbits){
 res=nbits;
 arraysize=nbits/8+(nbits%8?1:0);
 data = new char[arraysize];
 for (int i=0;i<arraysize;i++) data[i]=0;
 #ifdef TEST
 data[arraysize-2]=0xaa;  //10101010
 data[arraysize-3]=0x55;  //01010101
 #endif
}

int getDigit2(int n){  //get digit N in base 2, begin count at 0
 if (n>res) return 0;
#ifdef LITTLE_ENDIAN
 int b=arraysize-1-n/8;
 return ((data[b] >> (n%8))&1);
#endif
#ifdef BIG_ENDIAN
// Not implemented
#endif

}
};

int main(){
HighRes tall(RES_BITS);
#ifdef TEST
for (int i=3*8-1;i>=0;i--) cout << tall.getDigit2(i);
cout << endl;
#endif
}

[knuto]

Det som ville vore greiast til det trådstarter skal ha, ville vore ein "type" som fungerte _heilt likt_ int, men kunne lagre _mykje større tal_. Liksom slik:

 

#include <iostream>

int main() {
   longint tall = 3948209877403627694057;
   std::cout << "Basokamannen har nå " << tall << " gullmedaljer i samlingen sin." << std::endl;
   return 0;
}//end int main

 

Denne må gå ann å bruke heilt likt som int til f.eks. matematiske oppgåvar lik dette:

 

longint tall = 398704520389470;

longint annetTall = 083740987452423525243524525423521;

longint tredjeTall = tall ^ annetTall; //Legg merke til størrelsen på dette talet!!

Endret 2. juli 2005 av knuto

[Zethyr]

Det som ville vore greiast til det trådstarter skal ha, ville vore ein "type" som fungerte _heilt likt_ int, men kunne lagre _mykje større tal_.

Hadde vært greiest. Nå har det jo kommet meget gode forslag ellers her, så man skal jo ikke klage