mehr als eine 64bit int

Lord Apophis

CStoll schrieb:

xGhost schrieb:

also ist malloc sowas wie ein bitset?

malloc() ist sowas wie new (genauer: es ist die C-Entsprechung zu new).

Und wenn du Super-Int's selber schreiben willst, solltest du bei einem vector<unsigned char> (oder ähnliches) anfangen und dann beginnen, schriftliche Addition, Multiplikation und Division auf Computer-Niveaus zu übersetzen.

Da sehe ich nur eine Problem: das einzige das mir einfällt um sowas zu proggen ist ASM, oder kann C++ einen über Über- bzw. Unterläufe informiren?

CStoll

Da mußt du halt etwas tricksen, um das hinzubekommen (und intern etwas mehr Platz einkalkulieren für die Zwischenwerte):

pair<char,char> add_pos(char l,char r,char ex=0)
//addieren einer Zahlenstelle (mit Übertrag)
{
  short res=l+r+ex;
  return make_pair(res&0xFF /*Summenstelle*/, res>>8 /*Übertrag für nächste Stelle*/);
}

vector<char> add(const vector<char>& l,const vector<char>& r)
{
  pair<char,char> sval;
  vector<char> res;
  for(int i=0;i<max(l.size(),r.size();++i)
  {
    char ls=(i<l.size())?l[i]:0,
         rs=(i<r.size())?r[i]:0;
    sval=add_pos(ls,rs,sval.second);
    res.push_back(sval.first);
  }
  if(sval.second>0)res.push_back(sval.second);
  return res;
}

(ich bin mir sicher, das kann man noch optimieren, aber das Prinzip sollte klar sein)

Ben04

Kannst auch http://www.dhost.info/voodoocpp/index.php?page=progs/libs probiren. Ist eine Lib die ich vor kurzem selbst zusammen gebaut hab. Besteht aus reinem standard C++ und sollte daher portabel sein. Das Interface ist auch recht einfach zu bedinen:

#include<num/natural.hpp>
#include<iostream>
using namespace Num;

int main(){
  Natural a,b;
  cout<<"a = ";
  cin>>a;
  cout<<"b = ";
  cin>>b;
  cout<<"a + b = "<<(a+b)<<endl;
  cout<<"a * b = "<<(a*b)<<endl;
}

Ausgabe:

a = 999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
b = 9999999999999999999999999999999999999999999999999999999999999999999999999999
99999999999999999999999
a + b = 199999999999999999999999999999999999999999999999999999999999999999999999
9999999999999999999999999998
a * b = 999999999999999999999999999999999999999999999999999999999999999999999999
99999999999999999999999999800000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000001

Desweiteren werden auch noch Ganzzahlen und Brüche unterstützt.

boost::lexical_cast sollte funktionieren da es sich ja der iostreams bedient um die Konvertirung zu machen. Hab es aber noch nicht ausprobiert.

xGhost

Lord Apophis schrieb:

Da sehe ich nur eine Problem: das einzige das mir einfällt um sowas zu proggen ist ASM, oder kann C++ einen über Über- bzw. Unterläufe informiren?

Da gebe ich dir recht. Mit ASM ist es sicherlich schoener zu progen.
Aber mit "nur" C++ ist es auch moeglich.

Ich habe grossen respeckt zu C++. Eine sehr maechtige Sprache.

hab noch ne frage zu:

res&0xFF

0xFF ist hex und steht fuer 2^8 = 256 (?)
Was hat das hier fuer einen effekt?

Gg

BigNeal

xGhost schrieb:

hab noch ne frage zu:
res&0xFF
0xFF ist hex

ja

und steht fuer 2^8 = 256 (?)

nein 2^8-1

CStoll

Nein, 0xFF = 255 - und mit der Anweisung werden alle höherwertigen Bytes des Wertes zurückgesetzt. (alternativ könnte auch "res%256" und "res/256" verwendet werden)

Lord Apophis

xGhost schrieb:

0xFF ist hex und steht fuer 2^8 = 256 (?)
Was hat das hier fuer einen effekt?

Es soll wohl das höherwertige Byte von res 0 setzen, aber wenn "make_pair" nen char als Argument nehmen würde könnte man sich das doch sparen oder?
Oder wird beim typecast nicht einfach der höherwertige Teil abgeschnitten?

mfg

CStoll

Lord Apophis schrieb:

Oder wird beim typecast nicht einfach der höherwertige Teil abgeschnitten?

Ja, wird - aber sicher ist sicher

Ben04

Der beste Weg einen Überlauf zu behandeln ist ihn gar nicht erst statt finden zu lassen. Beispiel:

bool add_one(unisgned&num){
  if(num == std::numeric_limits<unsigned>::max()){
    num = 0;
    return true; // overflow
  }else{
    ++num;
    return false; // no overflow
  }  
}

Herauszufinden ob eine normal Addition überläuft geht gensauso leicht auch wenn die Herleitung ein wenig Mathe erfordert.

bool add_to(unsigned&a, unsigned b){
  unsigned can_add = std::numeric_limits<unsigned>::max() - a;
  if(b <= can_add){ // no overflow
    a += b;
    return false;
  }else{ // overlow
    // a := a + b - (std::numeric_limits<unsigned>::max() + 1)
    // a := b - (std::numeric_limits<unsigned>::max() - a + 1)
    // a := b - (can_add + 1)
    // a := b - can_add - 1
    // will not underflow because b > can_add (== !(b <= can_add)) and 
    // we substract can_add+1 so the minimal possible value is 0.
    a = b - can_add - 1;
    return true;
  }
}

CStoll

So, und jetzt versuch' mal, das selbe für die Multiplikation zweier Zahlenwerte zu realisieren

xGhost

stimmt das 2^8 = 255
0xFF hat sind volle 2 x 4bit

Das mit GMP geht, nur mein linker will -lgmp -lgmpxx nicht schlucken.
muss halt den vollen pfad mitgeben.

Also wenn ich das richig verstanden habe,
werden die zahlen in ein vector<char> abgelegt,
und bei einer adition einfach der "reihe" nach addiert (mit uebertrag).
coole idee.

Bon Mittag,
Gg

BigNeal

xGhost schrieb:

2^8 = 255

falsch

Ben04

CStoll schrieb:

So, und jetzt versuch' mal, das selbe für die Multiplikation zweier Zahlenwerte zu realisieren

Natürlich geht das da nicht aber das liegt nicht daran, dass es schwer ist herauszufinden, dass eine Multiplikation überläuft (was es wahrscheinlich nicht einmal ist) sonder, dass diese Information wertlos ist.

Nehmen wir das Zehnersystem mal Beispiel. Egal welche 2 Zifferen du zusammen ziehst, der Zehner ist entweder 1 oder 0. Dies gilt auch wenn man den Overflow der verherigen Zahlen betrachtest. Bei der Multiplikation bringt dir die Information ob es überläuft gar nichts, da der Zehner mehr als 2 Werte annehmen kann. Desweiteren kann man anders als bei der Addition die Zifferen auch nicht positionsunabhängig behandeln.

xGost schrieb:

Also wenn ich das richig verstanden habe,
werden die zahlen in ein vector<char> abgelegt,

Aus Performangründen ist vector<unsigned long long> oder vector<unsigned long> wahrscheinlicher.

xGhost

BigNeal schrieb:

xGhost schrieb:

2^8 = 255

falsch

0xFF = 2x 2^4 = 2^8 = zahlenstrahl 0 - 255

0x00 = 0000.0000 = 0
0x01 = 0000.0001 = 1
0x02 = 0000.0010 = 2
0x03 = 0000.0011 = 3
0x04 = 0000.0100 = 4
0x05 = 0000.0101 = 5
0x06 = 0000.0110 = 6
0x07 = 0000.0111 = 7
0x08 = 0000.1000 = 8
0x09 = 0000.1001 = 9
0x0A = 0000.1010 = 10
0x0B = 0000.1011 = 11
0x0C = 0000.1100 = 12
0x0D = 0000.1101 = 13
0x0E = 0000.1110 = 14
0x0F = 0000.1111 = 15
....
0xFF = 1111.1111 = 255

So jetzt sollte es stimmen ^^

CStoll

Ben04 schrieb:

CStoll schrieb:

So, und jetzt versuch' mal, das selbe für die Multiplikation zweier Zahlenwerte zu realisieren

Natürlich geht das da nicht aber das liegt nicht daran, dass es schwer ist herauszufinden, dass eine Multiplikation überläuft (was es wahrscheinlich nicht einmal ist) sonder, dass diese Information wertlos ist.

Nehmen wir das Zehnersystem mal Beispiel. Egal welche 2 Zifferen du zusammen ziehst, der Zehner ist entweder 1 oder 0. Dies gilt auch wenn man den Overflow der verherigen Zahlen betrachtest. Bei der Multiplikation bringt dir die Information ob es überläuft gar nichts, da der Zehner mehr als 2 Werte annehmen kann. Desweiteren kann man anders als bei der Addition die Zifferen auch nicht positionsunabhängig behandeln.

Klar, die Multiplikation ist etwas schwieriger, aber lässt sich recht analog zu meiner obigen Addition auch umsetzen.

xGost schrieb:

Also wenn ich das richig verstanden habe,
werden die zahlen in ein vector<char> abgelegt,

Aus Performangründen ist vector<unsigned long long> oder vector<unsigned long> wahrscheinlicher.

Und für die Übertrag-Behandlung bei der Multiplikation ist ein vector<char> oder vector<short> günstiger - ein short hat definitiv genug Platz, um das Produkt zweier char-Werte aufzunehmen, für das Produkt zweier long long Werte kenne ich keinen ausreichend großen Zahlentyp.

xGhost schrieb:

0xFF = 2x 2^4 = 2^8 = zahlenstrahl 0 - 255

Egal wie du es drehst - diese Aussage ist *sorry* Schwachsinn. 0xFF=255. Punkt.

(OK, die darunterstehende Aufzählung stimmt dann)

branleb

wie wärs wenn du dir net klasse für nen komplexen datentyp schreisbt???
also

template <class T> class complex
{
...
...
complex(T, T);
...
...
...
T real, im;
...
};

CStoll

shade37337 schrieb:

wie wärs wenn du dir net klasse für nen komplexen datentyp schreisbt???

Erstens: Was hat diese Klasse mit "große Integer-Werte" zu tun?
Zweitens: Wieso schreiben? Die Klasse gibt es schon (heißt std::complex und lebt im Header <complex>).

Ben04

CStoll schrieb:

Klar, die Multiplikation ist etwas schwieriger, aber lässt sich recht analog zu meiner obigen Addition auch umsetzen.

Da bin ich zwar gespant wie du für die Multiplikation die Information ob es eine Überlauf gibt verwerten kannst.

Meine Klasse macht das folgendermaßen:

Natural mul(const Natural&a, const Natural&b){
  Natural prod(0);
  unsigned ms_bit = b.get_most_significant_bit_set();
  for(unsigned bit = 0; bit < ms_bit; ++bit)
    if(b.is_bit_set(bit))
      prod += (a<<bit)
  return prod;
}

Was der Tafelrechung wie ich sie in der Schule gelernt hab angewant auf binär Zahlen entspricht.

CStoll

Ben04 schrieb:

CStoll schrieb:

Klar, die Multiplikation ist etwas schwieriger, aber lässt sich recht analog zu meiner obigen Addition auch umsetzen.

Da bin ich zwar gespant wie du für die Multiplikation die Information ob es eine Überlauf gibt verwerten kannst.

pair<char,char> mul_pos(char r,char l)
{
  short res=r*l;
  return make_pair(res&0xFF,res>>8);
}

Damit muß ich nur noch in einer doppelten Schleife über alle Zahlenstellen gehen und die Werte mittels add_pos() (von oben) zusammenaddieren.

xGhost

CStoll schrieb:

Und für die Übertrag-Behandlung bei der Multiplikation ist ein vector<char> oder vector<short> günstiger - ein short hat definitiv genug Platz, um das Produkt zweier char-Werte aufzunehmen, für das Produkt zweier long long Werte kenne ich keinen ausreichend großen Zahlentyp.

stimmt, short wuerde ich auch vorziehen.
Short sollte reichen um eine ziffer (0 ... 9) zu speichern.

Sicherleich interessant dazu:
http://de.wikipedia.org/wiki/Dualsystem#Grundrechenarten_im_Dualsystem

Gg