Extrem große Zahlen
-
@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.