Extrem große Zahlen
-
> Aber kann man den mit Strings ganz normal wie mit Zahlen rechnen?
natürlich! wenn du es entsprechen Programmierst:
heir ein Beispiel in Java (hab nichts in C++ da):
/* * Klasse "BigInt" repraesentiert vorzeichenlose, ganze Zahlen. Die * Klasse ist nicht durch den Wertebereich primitiver Typen begrenzt, * sondern speichert einen String mit der Dezimaldarstellung einer Zahl. */ // Sinnvolle Verbesserung: nicht wie Grundschulkind addieren, // sondern kompletten Wertebereich von int ausnuetzen class BigInt { private String text; // speichert die Dezimaldarstellung einer Zahl ///////////////////////// Konstruktoren /////////////////////////////// BigInt(BigInt orginal) // Copy Konstruktor { this(orginal.toString()); } BigInt(int i) { this(Integer.toString(i)); // Umwandlung von int nach String - unboxing } BigInt(String d) // Hauptkonstruktor - die anderen Konstruktoren stuetzen // sich auf diesen { text = new String(d); // text speichert die Dezimaldarstellung einer Zahl ///////////////////////////////////////////////////////////// /// Handelt es sich bei dem String um eine Dezimal Zahl? int lenght=text.length(); // Laenge von text feststellen for (int i=0;i<lenght;i++) // Jedes Zeichen einzeln pruefen ob es sich um // um eine Zahl handelt { if(Character.isDigit(text.charAt(i))==false) { System.out.println("Der Uebergebene Parameter (" + text + ") ist keine Zahl!"); text = "0"; } } //////////////////////////////////////////////////////////////// /// Führende Nullen vorne entfernen - der String "0" soll nicht /// ersetzt werden StringBuilder tmp = new StringBuilder(text); while(tmp.length()>1) { if(tmp.charAt(0)=='0') // Gibt es fuehrende Nullen { tmp.deleteCharAt(0); // Null entfernen } else { text = new String(tmp); break; // Alle fuehrenden Nullen entfernt } } } ////////////////////// Default-Methoden /////////////////////////////// public String toString() { return new String(text); } //////////////////// Weitere Methoden //////////////////////////////// // Gibt Wert von BigInt als Integer aus void print() { System.out.println(toString()); } /* * Liefert die Zahl in der angegebenen Zeichenkette text * an der Stelle index als Integerwert zurueck. Falls der * Index nicht existiert wird eine 0 zurueckgegeben * andernfalls die entsprechende Zahl - wenn es sich * nicht um eine Zahl (0, 1, 2, 3, 4, 5, 6, 7, 8, 9) * handelt wird auch 0 zurückgegeben. * * als Index ist der Logische Index gemeint * * Beispiel: * Array Index : 210 * Zahl : 512 * Logischer Index: 012 * * Funktion die aus Logischen Index einen Array Index macht * f(x) = length - (x + 1) * length := Anzahl der Elemente im Array */ private int getLogicIndex(String text, int index) { index = text.length() - (index + 1); int length = text.length(); if(index >= length || index < 0) return 0; char character = text.charAt(index); // mache aus Char einen Integer... return Character.getNumericValue(character); } // Addiert zwei BigInt und gibt als Ergebniss einen // BigInt zurueck BigInt add(BigInt b) { if(b==null) return null; int x = 0, y = 0; String zahl1 = new String(toString()); // Zahl1 als String String zahl2 = b.toString(); // Zahl2 als String // Groeßte Lange int length = zahl1.length() > zahl2.length() ? zahl1.length() : zahl2.length(); int carry = 0; // Stellenuebertrag StringBuilder ergebnis = new StringBuilder(); for(int i = 0; i<length; i++) { x = getLogicIndex(zahl1, i); y = getLogicIndex(zahl2, i); // Werte addieren int add = x+y+carry; // Uebertrag merken carry = add / 10; // Zahl "hinschreiben" ergebnis.insert(0, add%10); } if(carry > 0) ergebnis.insert(0, carry); return new BigInt(new String(ergebnis)); } // Berechnet eine beliebige Fibonaccizahl static BigInt Fibonacci(int i) { if(i < 1) { return new BigInt(0); } // Erste Fibonaccizahl if(i == 1) return new BigInt(0); // Zweite Fibonaccizahl if(i == 2) return new BigInt(1); BigInt a = new BigInt(0); // Erste Fibonaccizahl BigInt b = new BigInt(1); // Zweite Fibonaccizahl BigInt c = new BigInt(a); // Erste Fibonaccizahl for(int counter = 2; counter < i; counter++) { // Die neue Zahl berechnet sich aus den zwei // vorhergehenden Werten (a, b) c = a.add(b); // Fuer den naechsten Durchlauf der Schleife // werden die zwei vorhergenden Werte neu berechent // b_neu = c // a_neu = b BigInt new_b = new BigInt(c); a = new BigInt(b); b = new_b; } return c; } }vielleicht kannst du dir ja ein paar Ideen aus den Java Code abschauen
-
Danke erstmal für den Code. Ich werd den mal durcharbeiten und dann gucken ob es mir was bringt.
Trotzdem erstmal danke!
-
prof_maad schrieb:
Danke erstmal für den Code. Ich werd den mal durcharbeiten und dann gucken ob es mir was bringt.
Willst du, dass es nur effektiv funktioniert oder auch effizient?
-
Ich verlinke an dieser Stelle immer die GMP. Die kann da so ziemlich alles.
-
Über das Thema große Zahlen kann man ganze Bücher lesen - für die 100te Fibonacci war mein Code ausreichend
> Willst du, dass es nur effektiv funktioniert oder auch effizient?
ich glaub gegen etwas effizienteren Code mit Erklärung hätte er nichts
-
schau mal bei codeproject oder codeguru nach, maybe haben die was einfachen+mächtiges
-
such bei google z.b. nach
bigint c++
da findest dann klassen die mit grossen int's rechnen
-
Ein Beispiel für GMP-Code:
#include <gmpxx.h> #include <iostream> int main() { mpz_class x("123456789012345"), y("37144"); std::cout << x % y << std::endl; }mpz_class ist ne Klasse, die einen signed integer emuliert. Die gängigen Operatoren sind überladen, also ist der Kram wirklich einfach zu benutzen. Für genauere Doku: http://swox.com/gmp/manual/ - insbesondere http://swox.com/gmp/manual/C---Class-Interface.html#C++ Class Interface
-
Ich hab mir die ganzen Beiträge jetzt mal durchgelesen und die angesprochenen Techniken ausprobiert.
Bis jetzt habe ich jedoch noch nichts davon zum laufen bekommen. Kann mir vieleicht mal zeigen, wie man das nun anstellt.
Sprich:
- Wo müssen die Dateien von GMP hin
- Was muss ich includieren
- Vieleicht ein bissl Beispielcode für ne main(), die das System verwendetWäre echt super nett, wenn das gehen würde.
Danke im Voraus:
Prof. MAAD
-
http://sourceforge.net/projects/cpp-bigint/
Einfach bigint.h / bigint.cpp ins Projekt einbinden:
Beispiel:
#include "bigint.h" using namespace std; int main() { const string str1 = "1111111111111111111111111111111111111111111111111111"; const string str2 = "7777777777777777777777777777777777777777777777777777"; RossiBigInt a (str1,DEC_DIGIT); RossiBigInt b (str2,DEC_DIGIT); cout << a + b << endl << endl; cout << a * b << endl; }
-
Um die GMP unter Windows zu benutzen, gibts zwei Wege. Entweder, du installierst cygwin samt autoconf, automake und libtool, oder du schaust dir mal das hier an: http://fp.gladman.plus.com/computing/gmp4win.htm - da hat jemand ein paar Dateien der GMP so verändert, dass es mit MSVC läuft.
-
So, ich habe jetzt das mit Cpp-BigInt von Sourceforge hinbekommen.
Wenn ich ein kleines Beispielprogramm (dass von fifi) kompilieren will (Dev-C++ 4.9.9.1), so bekomme ich lauter "Linker error"'s, die folgendermaßen aussehen:[Linker error] undefined reference to `RossiBigInt::RossiBigInt(std::string const&, unsigned long)' [Linker error] undefined reference to `RossiBigInt::RossiBigInt(std::string const&, unsigned long)' [Linker error] undefined reference to `RossiBigInt::operator+(RossiBigInt const&)' [Linker error] undefined reference to `operator<<(std::ostream&, RossiBigInt const&)' [Linker error] undefined reference to `BaseBigInt::~BaseBigInt()' [Linker error] undefined reference to `BaseBigInt::~BaseBigInt()'Kann mir jemand erklären, was das schiefläuft.
Danke im Voraus:
Prof. MAAD
-
Was willst Du mit den großen Zahlen genau machen? Bzw. woher kommen die?
Daß bei solchen Themen hier immer nur auf GMP verlinkt wird ist sehr schade. Oftmals gibt es (gerade bei modulo) sehr viel effizientere Verfahren.
MfG Jester
-
@Jester:
Ich hab nen Programm, dass ohne nen speziellen Algorithmus Primzahlen berechnet. Es fängt mit 2 und 3 an und geht dann immer eine Zahl weiter. Diese versucht er nun durch alle schon errechneten Primzahlen zu teilen. Ist dies möglich, ist die Zahl nicht prim und die nächste wird genommen. Und so weiter.Nun soll das Programm bei mir auf nem Dauerlaufrechner ne ganze Weile (mindestens nen Jahr!) laufen. Irgendwann werd ich dann bei ziemlich großen Zahlen ankommen. Und dafür brauch ich so große Dateitypen.
-
Jo, dann brauchste die großen Zahlen wirklich. Nur wenn sie nur als Zwischenergebnis auftreten kann man sie oft sparen.
Aber wenn Du wirklich was über die Zahl wissen willst, dann mußte sie wohl auch benutzen. Es gibt allerdings einige deutlich bessere Verfahren um auf Primalität zu testen. Im Mathe-Forum gab es neulich einen Thread dazu.
MfG Jester
-
@Jester: Welche Verfahren? Meines Wissens ist die GMP eine der schnellsten Libs auf ihren Gebiet. Naja - mal abgesehen von ganz speziellen Sonderfällen wie modulo 2 oder modulo 10 oder so.
@prof_maad: Ich würd an deiner Stelle 2 als Sonderfall bezeichnen und ab 3 immer zwei Zahlen weitergehen - nach 2 gibts keine gerade Primzahl mehr. Außerdem musst du nur die Primzahlen testen, deren Quadrat nicht größer als die zu testende Zahl ist. Im Endeffekt also:
#include <iostream> #include <list> std::list<unsigned> primes; bool is_prime_cumulative(unsigned x) { for(std::list<unsigned>::iterator i = primes.begin(); *i * *i <= x; ++i) if(x % *i == 0) return false; return true; } int main() { primes.push_back(2); std::cout << '2' << std::endl; for(unsigned i = 3; i < 10000U; i += 2) if(is_prime_cumulative(i)) { primes.push_back(i); std::cout << i << std::endl; } }Naja. Ich kenn diese bigint-Geschichte, die hier neuerdings so modern ist, jetzt nicht, aber mit GMP wäre der einzige Unterschied zum bisherigen Code, dass du statt unsigned mpz_class schreibst und am Anfang ein #include <gmpxx.h> einfügst. Oh, und in deinem Fall wahrscheinlich, dass die Abbruchbedingung in der for-Schleife wegfällt und du dafür nen signal handler für SIGTERM oder SIGINT oder so einbauen willst.
-
Oh, und so ganz nebenbei - kuck, dass du ne Meeeenge RAM auf dem Rechner hast, auf dem du das machen willst. Das werden nachher ne ganze Menge ziemlich langer Primzahlen, die du dir merken willst.
-
Wer bigint nicht zum Laufen bekommt, sollte von GMP die Finger lassen.
Binde bigint.h, bigint.cpp und deine(!) main in ein neues Projekt ein und compiliere alles komplett neu. Dann läuft das auch.
-
BigInt ist echt easy, hier der Header (leicht gekürzt):
#include <cassert> #include <string> #include <sstream> #include <vector> #include <map> #include <iostream> #include <iomanip> #include <algorithm> using namespace std; // ======= // DEFINES // ======= #define ASSERTION(x) assert(x) #define DEC_DIGIT 10 #define HEX_DIGIT 16 #define MAX_VAL(x,y) ((x) > (y) ? (x) : (y)) #define MIN_VAL(x,y) ((x) < (y) ? (x) : (y)) #define CERR cerr << "[ " << __FILE__ << ", " << setw(3) << std::right << __LINE__ << " ] " #define FATAL_ERROR(t) cerr << endl; CERR << "FATAL ERROR : " << t << endl // ======== // TYPEDEFS // ======== typedef unsigned long ulong; /////////////// // DECLARATIONS /////////////// class BaseBigInt; class VinBigInt; class RossiBigInt; void ShowVersion(); // ============== class BaseBigInt // ============== { protected : vector<ulong> units_; static map<char, ulong> hex_to_dec_digits_convertor_s; ulong get_units_size () const; virtual ~BaseBigInt () = 0; public : bool is_empty () const; }; // ============== class VinBigInt : public BaseBigInt // ============== { friend ostream& operator<< (ostream& os, const VinBigInt& ins_i); private : bool init_via_string (const string& arg_i, ulong digit_base_i); public : // --- Constructors --- explicit VinBigInt (); explicit VinBigInt (ulong unit_i); explicit VinBigInt (const string& arg_i, ulong digit_base_i); explicit VinBigInt (const RossiBigInt& arg_i); // --- Aux methods --- ulong get_pure_ulong () const; // --- General purpose mathematical methods --- VinBigInt operator+ (const VinBigInt& arg_i) const; VinBigInt operator* (ulong arg_i) const; // --- Comparison operators --- bool operator== (const VinBigInt& arg_i) const; bool operator!= (const VinBigInt& arg_i) const; bool operator< (const VinBigInt& arg_i) const; bool operator> (const VinBigInt& arg_i) const; bool operator<= (const VinBigInt& arg_i) const; bool operator>= (const VinBigInt& arg_i) const; // --- Test functions --- static void All_Tests (); static void Test100_Operator_Add_Bigint (); static void Test300_Operator_Multiplication_Ulong (); }; // ============== class RossiBigInt : public BaseBigInt // ============== { friend ostream& operator<< (ostream& os, const RossiBigInt& ins_i); private : // --- Aux methods --- void resize_units (ulong size_i); void truncate_units (); bool units_not_front_back_is_null () const; bool init_via_string (const string& arg_i, ulong digit_base_i); public : // --- Constructors --- explicit RossiBigInt (); explicit RossiBigInt (ulong unit_i); explicit RossiBigInt (const string& arg_i, ulong digit_base_i); explicit RossiBigInt (const VinBigInt& arg_i); // --- Aux methods --- ulong get_pure_ulong () const; // --- General purpose mathematical methods --- RossiBigInt operator+ (const RossiBigInt& arg_i); RossiBigInt operator+ (ulong arg_i); RossiBigInt operator* (RossiBigInt arg_i) const; RossiBigInt operator* (ulong arg_i) const; // RossiBigInt& RossiBigInt::operator*= (RossiBigInt arg_i); RossiBigInt operator/ (const RossiBigInt& arg_i) const; RossiBigInt operator% (const RossiBigInt& arg_i) const; RossiBigInt Divide(const RossiBigInt& dividend_i, const RossiBigInt& divisor_i, RossiBigInt* remainder_o) const; RossiBigInt& operator+= (const RossiBigInt& arg_i); RossiBigInt& operator++ (int); // Post increment operator RossiBigInt& operator++ (); // Pre increment operator RossiBigInt operator- (const RossiBigInt& arg_i); RossiBigInt operator- (); RossiBigInt& operator-- (int); // Post decrement operator RossiBigInt& operator-- (); // Pre decrement operator RossiBigInt& operator-= (const RossiBigInt& arg_i); RossiBigInt sqrt(); // --- Bitwise boolean operators --- RossiBigInt operator& (const RossiBigInt& arg_i); RossiBigInt operator| (const RossiBigInt& arg_i); RossiBigInt operator^ (const RossiBigInt& arg_i); RossiBigInt& operator&= (const RossiBigInt& arg_i); RossiBigInt& operator|= (const RossiBigInt& arg_i); RossiBigInt& operator^= (const RossiBigInt& arg_i); RossiBigInt operator~ (); RossiBigInt operator>> (ulong shift_i); RossiBigInt operator<< (ulong shift_i); RossiBigInt& operator>>= (ulong shift_i); RossiBigInt& operator<<= (ulong shift_i); // --- Comparison operators --- bool operator== (const RossiBigInt& arg_i) const; bool operator!= (const RossiBigInt& arg_i) const; bool operator< (const RossiBigInt& arg_i) const; bool operator> (const RossiBigInt& arg_i) const; bool operator<= (const RossiBigInt& arg_i) const; bool operator>= (const RossiBigInt& arg_i) const; // --- Show functions --- string getstr_pure_hex_value () const; string getstr_hex_value () const; // --- Test functions --- void dbg_show () const; static void All_Tests (); static void Test100_Operator_Add_Bigint (); static void Test200_Operator_Subtraction_Bigint (); static void Test300_Operator_Multiplication_Bigint (); static void Test400_Operator_Division_Bigint (); static void Test500_Operator_Reminder_Bigint (); static void Test600_Operator_Less (); };
-
Etwas umständlich ist bei BigInt die Tatsache, dass man alles in RossiBigInt umwandeln muss. Es gibt auch kein
big /= zwei;sondern nur
big = big / zwei;Hier ein Beispiel für die Suche nach Verstößen gegen die noch unbewiesene Collatz-Folge:
// Berechnung der "3n+1"-Folge (Collatz-Folge) #include "bigint.h" int main() { /*********************************************************** Eingabebereich ****************************/ const RossiBigInt element_limit (1000000) ; // Maximum H(n) const RossiBigInt element_print_limit( 940) ; // Ausgabe nur, wenn H(n) > element_print_limit const RossiBigInt start( "20000000000000000000000000000000",DEC_DIGIT) ; // Beginn der Berechnung bei start const RossiBigInt end ( "21000000000000000000000000000000",DEC_DIGIT) ; // Ende der Berechnung bei end /*********************************************************** Eingabebereich ****************************/ RossiBigInt null (0) ; RossiBigInt eins (1) ; RossiBigInt zwei (2) ; RossiBigInt drei (3) ; for( RossiBigInt j = start; j < end; j++ ) { RossiBigInt zahl (j) ; RossiBigInt i (1) ; while( ( zahl != eins ) && ( i <= element_limit ) ) { if( zahl % zwei == null ) zahl = zahl / zwei ; else zahl = drei * zahl + eins ; i++ ; } if( zahl == eins ) { if( i > element_print_limit ) { cout << "Startzahl: " << j; cout << "\tAnzahl: " << i << endl; } } else { cout << "Startzahl: " << j; cout << "kein Resultat (Anzahl-Limit erhoehen)" << endl; } if( i > element_limit ) cerr << "Anzahl zu hoch" << endl; } }Das Problem besteht vor allem darin, dass das Ganze extrem langsam abläuft. Keine Effizienz.