Extrem große Zahlen

[prof_maad]

Hallo zusammen!

Ich habe derzeit ein "kleines" Problem:

Ich brauche für mein derzeitiges Programm extrem große Ganzzahlen. Ich muss mit diesen rechnen (Modulo-Operation vor allem).
Wenn jemand ne Ahnung hat, wie man sowas realisieren kann, dann wärs nett, wenn er das hier posten könnte.

Danke im Voraus,
Prof. MAAD

P.S.: Es sind wirklich extrem große Zahlen (werden wohl bis zu nen paar Tausend Stellen und wahrscheinlich noch viel mehr werden)

[Gast]

Runterscrollen!

[Vertexwahn]

du könntest dir ne Klasse schreiben die intern einene String für die Darstellung von "extrem" großen Zahlen verwendet - dürft wohl der naivste Ansatz sein

[prof_maad]

Das mit den Strings hab ich mir auch schon gedacht.
Aber kann man den mit Strings ganz normal wie mit Zahlen rechnen?

[Michael E.]

prof_maad: Wenn dus so implementierst.

[Vertexwahn]

> 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

[prof_maad]

Danke erstmal für den Code. Ich werd den mal durcharbeiten und dann gucken ob es mir was bringt.
Trotzdem erstmal danke!

[sdfgdfgfdgdf]

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?

[0xdeadbeef]

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

[newkid]

schau mal bei codeproject oder codeguru nach, maybe haben die was einfachen+mächtiges

[newkid]

such bei google z.b. nach

bigint c++

da findest dann klassen die mit grossen int's rechnen

[0xdeadbeef]

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

[fifi]

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

[0xdeadbeef]

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