mehr als eine 64bit int

xGhost

Moin,

Ist es moeglich einen groesseren Datentype als long long zu generieren?

Ich muesste mit:
999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
Rechnen.... also max. 100 Ziffern

*hust* ist das moeglich?

Bei google hab ich was von malloc() gelesen.
Koennte man es mit malloc() loesen?

Boost hat ein dynamische integer loesung, die geht aber auch nicht weiter wie
2^32

Hat jemand sowas schon mal versucht?

Gg

Lord Apophis

Eine Bibliothek die du hier findest könnte helfen:

http://www.trumphurst.com/cpplibs3.html#Libraries_available_via_FTP__D_L_ Die heißt "HugeCalc - Arbitrary accuracy large integer calculations", ich weiß net wie gut die ist, hab sie nur dort gefunden.

Mit malloc() forderst du Speicher auf dem Heap an, das hilft dir aber nicht beim Rechnen.

mfg
Apophis

xGhost

gut danke ist mal ein anfang.

Ich hab leider eine OpenBSD (Unix) mit GCC 3.3.5
und kein Borland.

also ist malloc sowas wie ein bitset?

Edit:

http://www.c-plusplus.net/forum/viewtopic-var-p-is-300796.html
Auch noch interessant.
Leider geht ein link nicht mehr...

bluecode

malloc ist eine Funktion welche einen Speicherbereich auf dem Heap alloziert... nicht mehr nicht weniger. Was du mit dem Speicherbereich machst ist dann deine Sache. Zu ner Bibliothek, die mehr als 2^64 (also long long) haben will, gehört halt mehr als malloc

xGhost

Jo sehe ich ein.

Ich nehme mal GMP. Sieht noch ortentlich aus.
Ich hoffe mal, ich kann ihn mit boost::lexical_caststd::string(gmp_class)
casten. mal sehen.

Wenn ich naechste woche entlich wieder mal zeit habe,
und frei vom(n?) (lehrn) Projekt bin. werde ich mir mal
anschauen wie man mit hilfe von malloc ne int bastelt.

Wenn jemand einen interessanten link hat, zu:
- GMP
- int selber basteln (fuer spaeter, wenn wieder zeit habe)
Bitte posten.

Danke fuer die Hilfe um spaete stunde ^^

Gg

Edit
Deutsche sprache, schwere sprache um 02:33

GPC

Hallo,

erst kürzlich gab es auch einen Thread zu gmp bzw. großen Zahlen allgemein.

Wenn jemand einen interessanten link hat, zu:
- GMP

Das offizielle Handbuch ist sehr gut. Das deckt alles ab

MfG

GPC

CStoll

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.

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.