Extrem große Zahlen

prof_maad

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.

Vertexwahn

Ü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

prof_maad

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 verwendet

Wä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.

prof_maad

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

Jester

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

prof_maad

@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.

Jester

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 ();
};

Erhard Henkes

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.