Kleiner fermatscher Satz

DerFrosch

volkard schrieb:

FermatTest sollte schlicht eine funktion sein und gar keine klasse.

Ja, stimmt eigentlich, war ja auch mehr dazu gedacht um mich mit den Konstrukten in C++ vertraut zu machen...

dooooomi

Ein paar Sachen:

1. Wie volkard schon sagte, eine Klasse ist hier eigentlich nicht sinnvoll. Und du willst schließlich lernen, wie man ein Problem "richtig" in C++ angeht, oder?

2. Zu jedem new gehört immer auch ein delete. Du hast Speicherlecks, weil deine auf dem Heap allozierten RossiBigInts niemals freigegeben werden.

3. In C++ schreibt man nicht foo(void), sondern einfach foo().

4. Dein Default-Konstruktor kommt mir eher überflüssig vor (Punkt 1 einmal außer Acht gelassen).

audacia

dooooomi schrieb:

3. In C++ schreibt man nicht foo(void), sondern einfach foo().

Nö.

DerFrosch

dooooomi schrieb:

Ein paar Sachen:

1. Wie volkard schon sagte, eine Klasse ist hier eigentlich nicht sinnvoll. Und du willst schließlich lernen, wie man ein Problem "richtig" in C++ angeht, oder?

Gut, dann ändere ich das mal ab...

dooooomi schrieb:

2. Zu jedem new gehört immer auch ein delete. Du hast Speicherlecks, weil deine auf dem Heap allozierten RossiBigInts niemals freigegeben werden.

Oh, daran habe ich ja überhaupt nich gedacht...

dooooomi schrieb:

3. In C++ schreibt man nicht foo(void), sondern einfach foo().

Das werde ich dann auch mal ändern...

dooooomi schrieb:

4. Dein Default-Konstruktor kommt mir eher überflüssig vor (Punkt 1 einmal außer Acht gelassen).

Der wird dann auch verschwinden...

Danke für die Tipps!!!

DerFrosch

Wenn ich das richtig verstanden habe, dann soll das etwa so aussehen:

#include "bigint.h"

//If TestedNumber is a prime number then
//base^(TestedNumber-1) == 1 (mod TestedNumber)
// for every base < TestedNumber

//Fermats primality test
//The test is not always correct because there are some pseudoprimes like 341 (11 * 31)
//where Fermats primility test says that they are prime.
//To make the method run faster the test uses iterated squaring.
//Complexity: log2(TestedNumber) loops
bool IsPrimeNumber(const string&, const string&);

bool IsPrimeNumber(const string &testnum, const string &base) {
	RossiBigInt TestedNumber(testnum, DEC_DIGIT), Base(base, DEC_DIGIT);
	RossiBigInt ZERO("0", DEC_DIGIT), ONE("1", DEC_DIGIT), TWO = ONE + ONE, exp = TestedNumber, addi = ONE, itsquare = Base;
	if(TestedNumber == TWO) return true; //2 is a Prime Number
	if(TestedNumber == ZERO || TestedNumber == ONE) return false; //by definition 0 and 1 are not prime numbers
	string binary = (--exp).binary_value();
	for(long i=binary.size()-1;i>=0;i--) {
		if(binary[i] == '1')
			addi = (addi * itsquare) % TestedNumber;
		itsquare = (itsquare * itsquare) % TestedNumber;
	}
	return (addi == ONE ? true : false);
}

volkard

DerFrosch schrieb:

Wenn ich das richtig verstanden habe, dann soll das etwa so aussehen:

fein.

return (addi == ONE ? true : false);

ist nur

return addi == ONE;

fein, daß du kein new mehr hast.

bool IsPrimeNumber(const string&, const string&);

der protityp sollte auch variablennamen haben. macht das lesen dann viel toller.
manche (ich auch) meinen, daß string const& viel hübscher als const string& ist.

bool IsPrimeNumber(const string &testnum, const string &base) {
	RossiBigInt TestedNumber(testnum, DEC_DIGIT), Base(base, DEC_DIGIT);
	RossiBigInt ZERO("0", DEC_DIGIT), ONE("1", DEC_DIGIT), TWO = ONE + ONE, exp = TestedNumber, addi = ONE, itsquare = Base;
	if(TestedNumber == TWO) return true; //2 is a Prime Number

der test könnte auch als erste zeile sein. und alle variablen so spät wie möglich anlegen. nicht einfach alle zu beginn der funktion auf vorrat.

string binary = (--exp).binary_value();

sollten zwei zeilen sein. weil zwei dinge geschehen.

for(long i=binary.size()-1;i>=0;i--) {

long? nee, da gabs nen size-typ im string.

volkard

oder gleich nur

if(TestedNumber == RossiBigInt(2)) return true; //2 is a Prime Number

DerFrosch

volkard schrieb:

bool IsPrimeNumber(const string &testnum, const string &base) {
	RossiBigInt TestedNumber(testnum, DEC_DIGIT), Base(base, DEC_DIGIT);
	RossiBigInt ZERO("0", DEC_DIGIT), ONE("1", DEC_DIGIT), TWO = ONE + ONE, exp = TestedNumber, addi = ONE, itsquare = Base;
	if(TestedNumber == TWO) return true; //2 is a Prime Number
der test könnte auch als erste zeile sein. und alle variablen so spät wie möglich anlegen. nicht einfach alle zu beginn der funktion auf vorrat.

Müssen die Variablen denn nicht sowieso beim Aufruf der Funktion angelegt werden???

Ansonsten:

bool IsPrimeNumber(string const& testnum, string const& base);

bool IsPrimeNumber(string const&  testnum, string const& base) {
	if(!testnum.compare("2")) return true; //2 is a Prime Number
	if(!testnum.compare("0") || !testnum.compare("1")) return false; //by definition 0 and 1 are not prime numbers
	RossiBigInt TestedNumber(testnum, DEC_DIGIT), Base(base, DEC_DIGIT);
	RossiBigInt ONE(1), exp = TestedNumber, addi = ONE, itsquare = Base;
	--exp;
	string binary = exp.binary_value();
	for(string::size_type i=binary.size();i>0;i--) {
		if(binary[i - 1] == '1')
			addi = (addi * itsquare) % TestedNumber;
		itsquare = (itsquare * itsquare) % TestedNumber;
	}
	return (addi == ONE);
}

Geht das jetzt so einigermaßen???

volkard

DerFrosch schrieb:

Geht das jetzt so einigermaßen???

die klammern bei return stören mich immer noch.
den rest könnte man wohl als vorbildlich einstufen.
ONE könnte noch const werden.

DerFrosch

volkard schrieb:

DerFrosch schrieb:

Geht das jetzt so einigermaßen???

die klammern bei return stören mich immer noch.
den rest könnte man wohl als vorbildlich einstufen.
ONE könnte noch const werden.

Gut, dann machen wa das mal:

bool IsPrimeNumber(string const& testnum, string const& base);

bool IsPrimeNumber(string const&  testnum, string const& base) {
	if(!testnum.compare("2")) return true; //2 is a Prime Number
	if(!testnum.compare("0") || !testnum.compare("1")) return false; //by definition 0 and 1 are not prime numbers
	RossiBigInt const ONE(1);
	RossiBigInt addi = ONE, TestedNumber(testnum, DEC_DIGIT), Base(base, DEC_DIGIT), exp = TestedNumber, itsquare = Base;
	--exp;
	string binary = exp.binary_value();
	for(string::size_type i=binary.size();i>0;i--) {
		if(binary[i - 1] == '1')
			addi = (addi * itsquare) % TestedNumber;
		itsquare = (itsquare * itsquare) % TestedNumber;
	}
	return addi == ONE;
}
//------------------------------------------------------------------------------

Vielen Dank für die Tipps Volkard...

DerFrosch

Vllt. noch eine winzige Änderung

bool IsPrimeNumber(string const& testnum, string const& base);

bool IsPrimeNumber(string const&  testnum, string const& base) {
	if(!testnum.compare("2")) return true; //2 is a Prime Number
	if(!testnum.compare("0") || !testnum.compare("1")) return false; //by definition 0 and 1 are not prime numbers
	RossiBigInt const ONE(1);
	RossiBigInt addi = ONE, TestedNumber(testnum, DEC_DIGIT), Base(base, DEC_DIGIT), exp = TestedNumber - ONE, itsquare = Base;
	string binary = exp.binary_value();
	for(string::size_type i=binary.size();i>0;i--) {
		if(binary[i - 1] == '1')
			addi = (addi * itsquare) % TestedNumber;
		itsquare = (itsquare * itsquare) % TestedNumber;
	}
	return addi == ONE;
}
//------------------------------------------------------------------------------

volkard

und noch was winziges:

bool IsPrimeNumber(string const& testnum, string const& base);

bool IsPrimeNumber(string const&  testnum, string const& base) {
	if(!testnum.compare("2")) return true; //2 is a Prime Number
	if(!testnum.compare("0") || !testnum.compare("1")) return false; //by definition 0 and 1 are not prime numbers
	RossiBigInt addi = One, TestedNumber(testnum, DEC_DIGIT), Base(base, DEC_DIGIT), exp = TestedNumber - One, itsquare = Base;
	string binary = exp.binary_value();
	for(string::size_type i=binary.size();i>0;i--) {
		if(binary[i - 1] == '1')
			addi = (addi * itsquare) % TestedNumber;
		itsquare = (itsquare * itsquare) % TestedNumber;
	}
	return addi == ONE;
}
//------------------------------------------------------------------------------

ups, doch nicht. der hat ja One global static gemacht. welche ein frevel. wöre so hübsch als puvlic static in der klasse.