sehr große zahl speichern

[nikolai]

ich habe mich mit mersenne nicht so sehr beschäftigt.
du meinst mit format: 2^1398269-1 ???
das ist ungünstig, da ich wirklich divisionen ausführen muß.

von daher wäre eine möglichkeit einen so großen datentyp anzulegen für mich wahrscheinlich die beste lösung. aber wie? muß ich dann alle rechenoperationen überlagern? das wird bei der division ganzschön haarig

[PoRcUpInE]

das problem wird nicht das überlagern sondern das darstellen im Speicher! (Da fängts schon an) Du musst ja in irgendeiner Weise darstellen wieviel Speicher du willst/brauchst und das bei 10 millionen Stellen! Ich meine damit das du irgendwo in deinem Code eine Konstante stehen hast die den Speicherplatzbedarf für 10mio Ziffern angibt! Und diese Konstante wird der Compiler nicht akzeptieren (geh ich mal davon aus) und genau da fangen die Probleme schon an! Was anderes fällt mir im Moment nämlich auch nicht ein!

Gruß
Mike

[Shade Of Mine]

PoRcUpInE schrieb:

Und eine Implementierung mit den dazugehörigen Funktionen für eine Zahl wirst du wohl in Assembler implementieren müssen um überhaupt ein bissl Performance zu bekommen.

also mein Compiler macht in den meisten Fällen wesentlich effizienteren Code als ich. Meine ASM Kenntnisse sind beschränkt, aber mein Compiler hängt mich da fast immer sehr weit ab.

ASM kann man nur verwenden um eine bestime Stelle schneller zu machen (nachdem der Profiler gezeigt hat, dass es nötig ist)

[nikolai]

könnten wir bitte wieder zum thema kommen "wie speichere ich eine so große zahl?"?
gibt es denn keine möglichkeit "int" zu erweitern?
ich hatte erst an ein array gedacht, aber da ist die frage wie dividiere und multipliziere ich.

[Christoph]

Schau dir mal GNU MP an.

[nikolai]

To build MP, you first have to configure it for your CPU and operating system. You need a C compiler, preferably GCC, but any reasonable compiler should work. And you need a standard Unix `make' program, plus some other standard Unix utility programs.*

ich schreibe mit dem visuell c++ 6.0

ich würde gern bei der sprache c++ bleiben und keinen kuddelmuddel mit unix anfangen.

gnu-mp sieht aber sonster sehr interessant aus.

[Entyl_Sa]

Hallo,

mein Bruder hat mal ein Programm geschrieben was mit so riesigen natürlichen Zahlen rechnen kann, weis jetzt nicht wie performant das ist und da ist auch ein wenig inline Assembler drin, aber es ist mir VC++ geschrieben. Kannst ja mal gucken ob du damit was anfangen kannst:

#include <iostream>
#include <string>
#include <math.h>
using namespace std;

class Ziffer {
public:
  Ziffer ();
  Ziffer (int , Ziffer * ); 
  ~Ziffer () {};
  int z;
  Ziffer * n;
};

class Pool {
public:
	Pool();
	~Pool();

	Ziffer* get (int , Ziffer*);
	void term (Ziffer * &);
	Ziffer p [1000000];
	Ziffer * nextfree;
};

class Iterator {
	friend class Zahl;
public:
	Iterator () ;
	Iterator (Ziffer* a) ;
	void operator++ ();
	bool operator!= (Iterator);
	bool operator== (Iterator);
	int & operator* ();
private:
	void weiter();
	Ziffer* pos;
};

class Zahl {
	friend class Iterator;
public:
	Zahl ();
	Zahl (string);
	Zahl (Zahl &);
	~Zahl () {pool.term(anfang);}
	void ausgabe ();
	Ziffer* start ();
	Zahl & operator= (Zahl &);
	Zahl operator* (Zahl &);
	void operator*= (Zahl &);
	Zahl operator* (int);
	void operator*= (int);
	void operator+= (Zahl &);
	Zahl operator+ (Zahl &);
	Zahl operator- (Zahl &);
	void operator-= (Zahl &);
	Zahl operator/ (Zahl &);
	Zahl operator% (Zahl &);
	void operator%= (Zahl &);
	Zahl operator^ (Zahl &);
	Zahl hochmod (Zahl &, Zahl &);
	void operator++ ();			
	void operator-- ();			
	void mulzwei();
	void divzwei ();
	bool ungerade ();
	bool gerade();
	bool operator == (Zahl &);
	bool operator != (Zahl &);
	bool operator < (Zahl &);
	bool operator > (Zahl &);
	bool operator <= (Zahl &);
	bool operator >= (Zahl &);
private:
	void weiter();
	void weiter(int);
	void ende();

	Ziffer * anfang;
	static Pool pool;
};

inline Iterator::Iterator () : pos(0) {}

inline Iterator::Iterator(Ziffer* a) {pos = a;}

inline void Iterator::operator++ () {
	pos = pos->n;
}

inline int & Iterator::operator* () {
	return pos->z;
}

inline bool Iterator::operator!= (Iterator i) {
	return pos != i.pos;
}

inline bool Iterator::operator== (Iterator i) {
	return pos == i.pos;
}

Pool::~Pool () {}

Ziffer* Pool::get (int i, Ziffer * z) {    
	Ziffer* erg;
	erg = nextfree;
	nextfree = nextfree->n;
	erg->n = z;
	erg->z = i;
	return erg;
}

void Pool::term ( Ziffer* &z) {      
        Ziffer* i;
	for(i = z; i->n != 0;i = i->n);
	i->n = nextfree;
	nextfree = z;
	z = 0;
}

Pool::Pool () {
	for(int i= 0; i<999999;++i)
		p[i].n = &(p[i+1]);
	nextfree = &(p[0]);
	p[999999].n = 0;
}

inline Ziffer::Ziffer () :z(0), n(0) {}

inline Ziffer::Ziffer (int pz, Ziffer * pn) :z(pz), n(pn) {}

inline Ziffer* Zahl::start () {
	return anfang;
}

inline void Iterator::weiter () {
        Ziffer* t;
	for (t = pos; t->n != 0; t = t->n);
	t->n = Zahl.pool.get(0, 0);
}

inline void Zahl::weiter () {
        Ziffer* t;
	for (t = anfang; t->n != 0; t = t->n);
	t->n = pool.get(0, 0);
}

inline void Zahl::weiter (int i) {
        Ziffer* t;
	for (t = anfang; t->n != 0; t = t->n);
	t->n = pool.get(i, 0);
}

void Zahl::ende () {
	if (anfang->n == 0) return;		
	Ziffer* del = anfang;
	Ziffer* t = anfang;
	while (t->n != 0) {
		t = t->n;
		if(t->z != 0) del = t;
	}
	if(del->n) pool.term(del->n);
}

Zahl & Zahl::operator= (Zahl & z) {
	pool.term(anfang);
	Iterator i(z.start());
	anfang =pool.get(*i, 0);
	Ziffer *a = anfang;
	++i;
	while (i.pos) { 
		a->n = pool.get(*i, 0);
		a = a->n;
		++i;
	}
	return *this;
}

Zahl::Zahl (Zahl & z) {

	z.ende();
	Iterator i(z.start());
	anfang = pool.get(*i, 0);
	Ziffer* a= anfang;
	++i;
	while (i.pos) {
		a->n = pool.get(*i, 0);
		a = a->n;
		++i;
	}
}

inline Zahl::Zahl () {
	anfang = pool.get(0, 0);
}

Zahl::Zahl (string a) {
	anfang = 0;
	int pos = a.length() -1;
	int erg = 0;
	for (int i=0; i<9 && pos>= 0;++i){
		erg += ((a.at(pos)-48) * pow(10, i));
		--pos;
	}
	anfang = pool.get(erg,0);
	Ziffer* p = anfang;
	while(pos>=0) {
		erg = 0;
		for (int i=0; i<9 && pos>= 0;++i){
			erg += ((a.at(pos)-48) * pow(10,i));
			--pos;
		}
		p->n = pool.get(erg,0);
		p = p->n;
	}
}

void Zahl::ausgabe () {
	(*this).ende();
	int aus, anzahl = 0;
	Iterator b;
	for (Iterator p = Iterator((*this).start()); p != b; ++p) {
		aus = *p;
		_asm push aus;
		++anzahl;
	}
	_asm pop aus;
	cout<<aus;
	--anzahl;
	for( int i=anzahl; i>0; --i){
		_asm pop aus;
		for(int index = 100000000;aus < index && 1 < index; index /=10) cout<<"0";
		cout<<aus;
	}
	cout<<" ";
}

Zahl Zahl::operator+ (Zahl  &i) {
	Zahl erg;
	Iterator ergebnis(erg.start());
	Iterator erste((*this).start());
	Iterator zweite(i.start());
	bool uebertrag = false;

	while (erste.pos && zweite.pos) {
		ergebnis.weiter();
		*ergebnis = *erste + *zweite;
		if(uebertrag) ++(*ergebnis);
		uebertrag = false;
		if(*ergebnis>= 1000000000) {
			*ergebnis -= 1000000000;
			uebertrag = true;
		}
		++erste; ++zweite; ++ergebnis;
	}
	while (erste.pos) {
		ergebnis.weiter();
		*ergebnis = *erste;
		if (uebertrag) ++(*ergebnis);
		uebertrag = false;
		if(*ergebnis >= 1000000000) {
			*ergebnis -= 1000000000;
			uebertrag = true;
		}
		++erste; ++ergebnis;
	}
	while (zweite.pos) {
		ergebnis.weiter();
		*ergebnis = *zweite;
		if (uebertrag) ++(*ergebnis);
		uebertrag = false;
		if(*ergebnis >= 1000000000) {
			*ergebnis -= 1000000000;
			uebertrag = true;
		}
		++zweite; ++ergebnis;
	}
	if(uebertrag) *ergebnis = 1;

	return erg;
}

void Zahl::operator+= (Zahl  &i) {

	Iterator erste((*this).start());
	Iterator zweite(i.start());
	bool uebertrag = false;

	while (erste.pos && zweite.pos) {
		*erste += *zweite;
		if(uebertrag) ++(*erste);
		uebertrag = false;
		if(*erste>= 1000000000) {
			*erste -= 1000000000;
			uebertrag = true;
		}
		++erste; ++zweite;
	}
	while (erste.pos) {
		if (uebertrag) ++(*erste);
		uebertrag = false;
		if(*erste >= 1000000000) {
			*erste -= 1000000000;
			uebertrag = true;
		}
		++erste;
	}
	if(erste == 0) {
		Iterator ende((*this).start());
		ende.weiter();	
		while (ende.pos->n) ++ende;

		while (zweite.pos) {
			*ende = *zweite;
			if (uebertrag) ++(*ende);
			uebertrag = false;
			if(*ende >= 1000000000) {
				*ende -= 1000000000;
				uebertrag = true;
			}
			ende.weiter();
			++zweite; ++ende;
		}
	}
	if(uebertrag) *erste = 1;

	return;
}

Zahl Zahl::operator- (Zahl &i) {
	Zahl erg;
	if(i > *this) {
		pool.term(erg.anfang);
		return erg;
	}
	Iterator ergebnis(erg.start());
	Iterator erste((*this).start());
	Iterator zweite(i.start());
	bool uebertrag = false;

	while(erste.pos && zweite.pos) {
		ergebnis.weiter();
		*ergebnis = *erste - *zweite;
		if (uebertrag) --(*ergebnis);
		uebertrag = false;
		if (*ergebnis < 0) {
			*ergebnis += 1000000000;
			uebertrag = true;
		}
		++erste; ++zweite; ++ergebnis;
	}

	while (erste.pos) {
		ergebnis.weiter();
		*ergebnis = *erste;
		if (uebertrag) --(*ergebnis);
		uebertrag = false;
		if(*ergebnis < 0) {
			*ergebnis += 1000000000;
			uebertrag = true;
		}
		++erste; ++ergebnis;
	}

	return erg;
}

void Zahl::operator-= (Zahl &i) {
	Zahl erg;
	if(i > *this) {
		pool.term(erg.anfang);
		*this = erg;
		return;
	}
	Iterator erste((*this).start());
	Iterator zweite(i.start());
	bool uebertrag = false;

	while(erste.pos && zweite.pos) {
		*erste -= *zweite;
		if (uebertrag) --(*erste);
		uebertrag = false;
		if (*erste < 0) {
			*erste += 1000000000;
			uebertrag = true;
		}
		++erste; ++zweite;
	}

	while (erste.pos) {
		if (uebertrag) --(*erste);
		uebertrag = false;
		if(*erste < 0) {
			*erste += 1000000000;
			uebertrag = true;
		}
		++erste;
	}
}

bool Zahl::operator == (Zahl & i) {
	(*this).ende();
	i.ende();
	Iterator eins(i.start());
	Iterator zwei((*this).start());

	while(eins.pos && zwei.pos) {
		if(*eins != *zwei) return false;
		++eins; ++zwei;
	}

	if(!(eins.pos) && !(zwei.pos)) return true;
	else return false;
}

inline bool Zahl::operator != (Zahl & i) {
	if(i == (*this)) return false;
	else return true;
}

bool Zahl::operator < (Zahl & i) {
	(*this).ende();
	i.ende();
	Iterator eins(i.start());
	Iterator zwei((*this).start());
	bool erg = false;

	while(eins.pos && zwei.pos) {
		if(*eins < *zwei) erg = false;
		if(*eins > *zwei) erg = true;
		++eins; ++zwei;
	}
	if(eins.pos) erg = true;
	if(zwei.pos) erg = false;
	return erg;
}

inline bool Zahl::operator > (Zahl & i) {
	if(*this < i)return false;
	if(*this == i) return false;
	return true;
}

inline bool Zahl::operator <= (Zahl & i) {
	if(*this > i) return false;
	return true;
}

inline bool Zahl::operator >= (Zahl & i) {
	if(*this < i) return false;
	return true;
}

Zahl Zahl::operator * (int i) {
	Zahl erg;
	if (i == 1) return *this;
	if (i == 0) return erg;
	if (i == 1000000000) {
		erg = *this;
		erg.anfang= pool.get(0, erg.anfang);
		return erg;
	}
	Iterator ergebnis(erg.start());
	Iterator erste((*this).start()); 
	int uebertrag = 0;

	while(erste.pos) {
		ergebnis.weiter();
		int eins = *erste;
		int zwei;
		int drei = i;
		_asm mov eax, eins
		_asm mov edx, drei
		_asm mul edx
		_asm mov ecx, 1000000000
		_asm div ecx
		_asm add edx, uebertrag
		_asm adc eax,0
		_asm mov zwei, edx
		_asm mov uebertrag, eax
		*ergebnis = zwei;
		if (*ergebnis >= 1000000000) {
			uebertrag += *ergebnis / 1000000000;
			*ergebnis %= 1000000000;
		}
		++ergebnis; ++erste;
	}
	if(uebertrag) *ergebnis = uebertrag;
	erg.ende();

	return erg;
}

void Zahl::operator *= (int i) {
	if (i == 1) return;
	Zahl erg;
	if (i == 0) {*this = erg; return;}

	Iterator ergebnis(erg.start());
	Iterator erste((*this).start());
	int uebertrag = 0;

	while(erste.pos) {
		ergebnis.weiter();
		int eins = *erste;
		int zwei;
		int drei = i;
		_asm mov eax, eins
		_asm mov edx, drei
		_asm mul edx
		_asm mov ecx, 1000000000
		_asm div ecx
		_asm add edx, uebertrag
		_asm adc eax,0
		_asm mov zwei, edx
		_asm mov uebertrag, eax
		*ergebnis = zwei;
		if (*ergebnis >= 1000000000) {
			uebertrag += *ergebnis / 1000000000;
			*ergebnis %= 1000000000;
		}
		++ergebnis; ++erste;
	}
	if(uebertrag != 0) *ergebnis = uebertrag;
	erg.ende();

	*this = erg;
}

Zahl Zahl::operator* (Zahl & i) {
	Zahl erg;
	Iterator eins (i.start());
	Zahl zwischen;
	int index = 1;
	while(eins.pos) {
		zwischen = *this * *eins;
		for(int i = index; i >= 2; --i)zwischen.anfang = pool.get(0, zwischen.anfang);
		erg += zwischen;
		++eins; ++index;				
	}
	return erg;
}

void Zahl::operator*= (Zahl & i) {
	Zahl erg;
	Iterator eins (i.start());
	while(eins.pos) {
		erg += (*this) * *eins;
		++eins;
		(*this).anfang = pool.get(0, (*this).anfang);
	}
	*this = erg;
}

Zahl Zahl::operator% (Zahl & i) {
	Zahl enderg;
	if(i > *this) return *this;
	Zahl zwierg;
	Zahl eins("1");
	int mul = 10;
	Zahl div = *this;
	while(div >= i) {
		Zahl sub = i;
		zwierg = eins;
		while(div >= sub) {
			enderg += zwierg;
			div -= sub;
			zwierg *= mul;
			sub *= mul;
		}
	}
	div.ende();
	return div;	
}

void Zahl::operator%= (Zahl & i) {
	Zahl enderg;
	if(i > *this) return;
	Zahl zwierg;
	Zahl eins("1");
	int mul = 10;
	Zahl div = *this;
	while(div >= i) {
		Zahl sub = i;
		zwierg = eins;
		while(div >= sub) {
			enderg += zwierg;
			div -= sub;
			zwierg *= mul;
			sub *= mul;
		}
	}
	div.ende();
	*this = div;	
}

Zahl Zahl::operator/ (Zahl & i) {

	Zahl enderg;
	if(i > *this) return enderg;
	Zahl zwierg;
	string s = "1";
	Zahl eins(s);
	int zehn = 10;
	Zahl div = *this;
	while(div >= i) {
		Zahl sub = i;
		zwierg = eins;
		while(div >= sub) {
			enderg += zwierg;
			div -= sub;
			zwierg *= zehn;
			sub *= zehn;
		}
	}
	return enderg;
}

void Zahl::divzwei () {
	Iterator i((*this).start());
	Iterator next((*this).start());
	if(anfang->n == 0) {(*i) >>=1; return;}
	++next;
	while(next.pos) {
		*i >>=1;
		if(*next & 1) *i += 500000000;
		++next; ++i;
	}
	*i >>=1;
	return;
}

void Zahl::mulzwei() {
	Iterator i((*this).start());
	bool carry = false;
	while(i.pos) {
		*i <<=1;
		if(carry) ++(*i);
		if(*i >= 1000000000) carry = true;
		else carry = false;
		++i;
	}
	if(carry) (*this).weiter(1);
	return;
}

inline bool Zahl::ungerade() {
	return (anfang->z & 1);
}

Zahl Zahl::operator^ (Zahl & i) {

	Zahl enderg;
	Zahl eins ("1");
	if (i == enderg) return eins;
	if (i == eins) return *this;
	Zahl zwierg = *this;
	Zahl null;
	enderg = eins;
	while(i != null) {
		if(i.ungerade()) enderg *= zwierg;
		i.divzwei();
		zwierg *= zwierg;
	}
	return enderg;
}

Zahl Zahl::hochmod (Zahl & i, Zahl & a) {

	Zahl enderg;
	Zahl eins ("1");
	Zahl null ("0");
	*this %= a;
	if (a == null) return null;
	if (i == enderg) return eins;
	if (i == eins) return *this;
	Zahl zwierg = *this;
	enderg = eins;
	while(i != null) {
		if(i.ungerade()){ 
			enderg *= zwierg;
			enderg %= a;
		}
		i.divzwei();
		zwierg *= zwierg;
		zwierg %= a;
	}
	return enderg;
}

inline void Zahl::operator ++ () {
	Zahl eins("1");
	*this += eins;
}

inline void Zahl::operator -- () {
	Zahl eins("1");
	*this -= eins;
}

Pool Zahl::pool;

int main () {
	int i;
	cout<<"Bitte geben Sie die Art der Rechnung an die Sie vornehmen wollen: "<<endl;
	cout<<"multiplikation (1)"<<endl;
	cout<<"division (2)"<<endl;
	cout<<"modulo (3)"<<endl;
	cout<<"subtraktion (4)"<<endl;
	cout<<"addition (5)"<<endl;
	cout<<"potenzieren (6)"<<endl;
	cout<<"a hoch b mod c (7)"<<endl;
	cin>>i;
	string s;
	cout<<"Bitte a eingeben: ";
	cin>>s;
	Zahl a(s);
	cout<<"Bitte b eingeben: ";
	cin>>s;
	Zahl b(s);
	if(i == 7) {cout<<"Bitte c eingeben: "; cin>>s;}
	Zahl c(s);
	cout<<"a = ";
	a.ausgabe();
	cout<<endl<<"b = ";
	b.ausgabe();
	if(i == 7) {cout<<endl<<"c = "; c.ausgabe();}
	cout<<endl;
	if(i<2 || i>7) {cout<<"a = a * b"<<endl; a *= b;}
	if(i == 2) {cout<<"a = a / b"<<endl; a = a / b;}
	if(i == 3) {cout<<"a = a % c"<<endl; a %= b;}
	if(i == 4) {cout<<"a = a - b"<<endl; a -= b;}
	if(i == 5) {cout<<"a = a + b"<<endl; a += b;}
	if(i == 6) {cout<<"a = a ^ b"<<endl; a = a^b;}
	if(i == 7) {cout<<"a = a^b%c"<<endl; a = a.hochmod(b,c);}
	a.ausgabe(); cout<<endl;
	cout<<"zum beenden etwas eingeben"<<endl;
	cin>>s;
	return 0;
}

[nikolai]

habe ein paar ansätze aus dem quelli geklaut.
danke an deinen bruder und dich.
gibt es nicht für solche probleme (wie speichere ich große zahlen) ne extra bibliothek?wie die gnu-mp nur halt für windows?

[nikolai]

nach ewig langem suchen habe ich nun schließlig (gott sei dank) was schönes gefunden:
für jeden den es interessiert und große zahlen zum verschlüsseln oder ähnlichem braucht:
http://www.acid-code.ch/~samuel/BigInt.zip

[japro]

nikolai schrieb:

das verfahren findet sehr schnell (meist bei der dritten oder vierten division)
heraus, ob eine zahl KEINE primzahl ist,
ob eine zahl eine primzahl IST kann man allerdings bei der hälfte der zahl+1 beweisen.

öööh also zum beweisen musst du eeeeeeeeeeeeeeeeextrem viele divisionen durchführen. also angnommen deine zahl hat diese 10mio stellen dann musst du so in etwa
1/2*10^10000000 divisionen durchführen um zu beweisen, dass die zahl prim ist

gehen wir mal von ein hammerrechner aus der eine division in einem takt ausführt und das bei 1 Thz! also 1 billion divisionen pro sekunde also 10^12!
ok also braucht unser monstercomputer 1/2*10^9999988 sekunden das sind scho schätzungsweise öhm 10^9999981 jahre..... dein pc mus ne hammer uptime haben... oder hab ich da irgendwas entscheidendes übersehen?

[Glamdrink]

Als Datentyp könnte amn vielliecht auch std::basic_String<short> nehmen, der kann ja ziemlich viele Zhalen aufnehmen, wird aber ziemlich langsam und ressourcenfressend sein.

mfg
Glamdring

[CPPChris]

Hi!

Also mich würde brennend dein Algo interessieren mit dem du bei max. 4 Divisionen beweisen willst dass eine Zahl keine Primzahl ist.

Genauso dass man eine primzahl beweisen kann mit. Zahl/2 +1

MfG CPP-Chris

[volkard]

das geht doch leicht, indem man durch 2, dann durch 3 und dann durch 5 teilt. damit werden bereits mehr als 73% der natürlichen zahlen als zusammengesetzte zahl erkannt.
echt männer schaffen das sogar mit einer division!
versucht man dann, eisern die teiler 2,3,4,5,6,7... zu nehmen bis Zahl/2+1 und hat bei all den divisionen die zahl nicht als zusammengesetzt erkennen können, muß sie prim sein.
insofern ist doch

das verfahren findet sehr schnell (meist bei der dritten oder vierten division)
heraus, ob eine zahl KEINE primzahl ist,
ob eine zahl eine primzahl IST kann man allerdings bei der hälfte der zahl+1 beweisen.

völlig korrekt.