Kleiner fermatscher Satz

DerFrosch

Hallo Zusammen,

ich beschäftige mich seit kurzem ein wenig mit C++ (in der Schule hatte ich mehr mit C zu tun). Heute habe ich mal ein kleines Programm geschrieben das mit Fermats kleinem Satz(http://de.wikipedia.org/wiki/Kleiner_fermatscher_Satz) prüft, ob eine Zahl eine Primzahl ist. Natürlich lässt sich darüber streiten ob man soetwas überhaupt in C++ schreiben muss, war aber wie gesagt nur zur Übung. Mich würde jetzt interessieren, was ich generell anders machen sollte / müsste oder was kompletter Blödsinn ist. Da ich mich eigentlich für ziemlich kritikfähig halte, könnt ihr ruhig eure ganze Wut an mir auslassen ;). In dem Programm verwende ich eine BigInt Klasse von sourceforge,bei der ich eine kleine Methode(binary_value() ->Zahl binär darstellen) eingebaut habe. Wenn sich einer für alle Dateien interessiert, dann kann er die hier herunterladen: http://www.turboupload.com/files/get/5qM8JrISN2/prim.zip

Ansonsten:
fermat.h:

#include "bigint.h"

//If TestedNumber is a prime number then
//base^(TestedNumber-1) = 1 (mod TestedNumber)
// for every base < TestedNumber
class FermatTest {
	private:
		RossiBigInt* TestedNumber;
		RossiBigInt* Base;

	public:
		FermatTest(void);
		FermatTest(const string&, const string&);
		FermatTest(const string&);
		bool IsPrimeNumber(void);
};

fermat.cpp:

#include "fermat.h"

//Default Constructor
FermatTest::FermatTest(void) {
	Base = new RossiBigInt("2", DEC_DIGIT);
	TestedNumber = new RossiBigInt("2", DEC_DIGIT);
}
//------------------------------------------------------------------------------

//Parameter List Constructor
//Parameter: The Number that is tested as string
FermatTest::FermatTest(const string &testnumber) {
	Base = new RossiBigInt("2", DEC_DIGIT);
	TestedNumber = new RossiBigInt(testnumber, DEC_DIGIT);
}
//------------------------------------------------------------------------------

//Parameter List Constructor
//Parameters: testnumber: The Number that is tested as string
//            base: the base that shall be used for the calculation
FermatTest::FermatTest(const string& testnumber, const string& base) {
	RossiBigInt ZERO("0", DEC_DIGIT), TWO("2", DEC_DIGIT);
	Base = new RossiBigInt(base, DEC_DIGIT);
	TestedNumber = new RossiBigInt(testnumber, DEC_DIGIT);
	if(*Base >= *TestedNumber || *Base <= ZERO) //The base has to be smaller than the tested Number and > 0
		*Base = TWO;;
}
//------------------------------------------------------------------------------

//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 FermatTest::IsPrimeNumber(void) {
	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);
}
//------------------------------------------------------------------------------

Achso Nochwas: Die englischen Kommentare bitte nicht auf Grammatik und Rechtschreibung prüfen...

volkard

FermatTest sollte schlicht eine funktion sein und gar keine klasse.

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.