unerklärlicher fehler bei nichtprimzahl-test

[Lindworm]

hi, ich habe den code aus chackotays beispiel für eine nicht-primzahl-prüfung verwendet und bekomme jetzt bei der benutzung einen für mich unerklärlichen fehler:

"[Fehler] Unit1.pas(63): E2015 Operator ist auf diesen Operandentyp nicht anwendbar
[Warnung] Unit1.pas(63): W1023 Vorzeichenbehaftete und -lose Typen werden verglichen - beide Operanden werden erweitert"

Zeile 63 und umgebende sehen so aus:

Code:

58 implementation
59 {$R *.dfm}

61 function IsNotPrime(const a, n: longint): boolean;
62 begin
63   Result := (Power(a, n-1) mod n) <> 1;
64 end;
65 procedure TForm1.createnewClick(Sender: TObject);

wenn mehr quelltext benötigt wird, kann ich gerne noch mehr rausrücken
vielen dank schonmal für eure bemühungen, bene

[ichbins]

Power gibt immer einen real-typ zurück. mod ist für Integer-Typen gedacht.

Mach 'n round um das power rum.

[Union]

Zitat von ichbins:

Power gibt immer einen real-typ zurück. mod ist für Integer-Typen gedacht.

Mach 'n round um das power rum.

Wohl eher trunc

[Lindworm]

also ich hab jetz beides getestet, funktinieren tun beide lösungen, ich werde mich jetzt mal über den unterschied informieren
edit: also ich hab mir jetzt beides angesehen und ich denke es sollte egal sein, was ich verwende, da ja eigentlich sowiso nur ganzzahlige ergebnisse erhalten sollte

[alzaimar]

Sonderlich grosse Primzahlen kannst du mit dem Test aber nicht testen, oder? Da gibt es doch wunderschöne Optimierungen, die ganz ohne Power auskommen. Suche mal hier in der DP, negaH hat einen sehr sehr schnellen Primzahltester auf der Basis geschrieben.

[Lindworm]

das programm ist auch nur ein rechentrainer für kinder, da werden die zahlen nicht wirklcih gross, trotzdem danke für den tipp, werde mir das mal ansehen

[negaH]

Result := (Power(a, n-1) mod n) <> 1; Also das kann garnicht funktionieren.

Der Fermat-Test ist so definiert

A ^ (N-1) mod N |= 1 mod N

dies bedeutet das wir in modularen Ringen arbeiten.
Angenommen A = 3 und N = 1000 dann würde Power(A, N-1) == 3^999 werden. Diese riesige Zahl kann aber in einem Fließkommadatentyp nicht mehr EXAKT gespeichert werden. Ergo: mit Fließkommazahlen wird der Wert 3^999 gerundet/abgeschnitten gespeichert. Die nachfolgende modulare Division mit N wird also je nach Rundungsfehler in den Fliekommazahlen ein nicht mehr mathematisch aussagekräftiges Resulat liefern.

Der obige Code ist also programmtechnisch eine falsche Umsetzung der nötigen Mathematik. Du solltest dir an solchen Beispielen kein Beispiel nehmen.

Der richtige Weg wäre die Implementation einer eigenen modularen Exponentation die mit Ganzzahlen arbeitet. Beim Fermat Test MUSS jedes einzelne Zahlenbit absolut exakt berechnet werden, Fließkommazahlen haben darin nichts zu suchen.

Es ist besser hier in Forum nach meinem schnellen Primzahltest zu suchen.
Anbei mein Code zum schnellen Test einer Zahl < 2^32 auf Primzahleigenschaft.
Der normale Fermat Test wie oben gezeigt würde nämlich auch Zusammengesetzte Zahlen als Primzahlen ausweisen die garkeine Primzahlen sind. Ich weis nicht was deine Kids davon halten sollen wenn sie durch dummen Zufall eine sogenannte Carmichael Zahl eingeben und dein Program sagt ads es eine Primzahl wäre, obwohl ads natürlich bei Carmichaelzahlen falsch ist.


Gruß Hagen

[Lindworm]

gibts die überhaupt unter 100?
naja egal, vielen danke für dein script, werde mich bemühen das ordentlich einzubinden, denn ich habe mit dem jetzigen eh einige probs.
PS: chacko hatte mir das empfohlen unter der vorraussetzung, dass ich nur herausfinden muss, ob es keine primzahl ist.

[negaH]

Der Ansatz ist ja auch richtig. Nur muß man eben bedenken das einfache Primzahltests, und Fermat ist wohl einer der einfacheren, bei ganz bestimmten zusammengesetzten Zahlen scheitern. Diese Zahlen sind zb. die Carmichaelzahlen.

Auch mein Primzahltest basiert auf einem abgewandelten Fermat Verfahren. Auch dieser sogenannte SPP, strong Pseudo Primality Test, kann an den Carmichaelzahlen scheitern. ABER! mein Test benutzt eine Kombination aus mehreren SPPs zu festen Basen die mit allen Zahlen bis < 4759123141 = $11BAA74C5 schon duch andere Mathematiker ausgetestet worden sind. Es ist also garantiert das bei diesem Test mit Cardinals < 2^32 die Rückgabe der Funktion eindeutig eine Primzahl von einer zusammengesetzte Zahl unterscheidet.

Einbinden tuest du diese Unit ganz einfach. In der Uses Klausel deines Programmes "IsPrimeHRUnit" hinzufügen und in deinem Code dann IsPrime(Zahl) aufrufen, das wars.

Das meine Unit nun in Assembler gecodet ist und teilweise sehr aufwendige Verfahren benutzt liegt einzigst daran das sie auf einem Programierer Contest entstanden ist. Dabei ging es eben darum so schnell wie auf heitigen CPUs möglich zu ermitteln ob einen Zahl 2^32 eine Primzahl ist. Falls du weitergehendes Interesse daran hast dann schau mal hier rein http://dennishomepage.gugs-cats.dk/IsPrimeChallenge.htm

Gruß Hagen

[CalganX]

Hi Hagen,

Zitat von negaH:

Der Fermat-Test ist so definiert

A ^ (N-1) mod N |= 1 mod N

Oh... hm, ich habe mein Gedächtnis anhand des Wikipedia-Eintrages (Klick!) aufgefrischt, bevor ich das zusammen gebaut habe. Dort steht zwar ähnliches, allerdings ist dort eine Gleichung angegeben und keine Kongruenz, die wohl eigentlich gemeint ist.
Allerdings kommt es doch im Endeffekt auf's Gleiche raus, da 1 mod N grundsätzlich 1 ist, oder nicht (sofern N > 0, was allerdings eine Vorraussetzung ist)?

Zitat:

dies bedeutet das wir in modularen Ringen arbeiten.

Klar, aber ändert das etwas Grundlegendes jetzt?

Zitat:

Angenommen A = 3 und N = 1000 dann würde Power(A, N-1) == 3^999 werden. Diese riesige Zahl kann aber in einem Fließkommadatentyp nicht mehr EXAKT gespeichert werden. Ergo: mit Fließkommazahlen wird der Wert 3^999 gerundet/abgeschnitten gespeichert. Die nachfolgende modulare Division mit N wird also je nach Rundungsfehler in den Fliekommazahlen ein nicht mehr mathematisch aussagekräftiges Resulat liefern.

Gut. Aber das ist wenn dann ein Problem des Fermat-Tests (er ließe sich durch eine schnellere Power-Methode ein wenig optimieren, aber ich denke nicht, dass es dadurch extreme Vorteile geben würde) und nicht des Codes. Abgesehen davon handelt es sich hier - wie gesagt - um ein kleines Übungsprogramm. Solche große Zahlen kommen hier wohl nicht vor.
Natürlich kannst du Recht haben, dass dies kein optimaler Test ist und die Umsetzung vielleicht nicht zur Befriedung eines höheren Mathematikers ist, allerdings habe ich mit dem Mathe-Studium noch nicht angefangen und Assembler kann ich zu meiner Schande auch nicht. Hilft also nichts, bleibt mir nur die einfache, oben gepostete Lösung übrig.
Was ich damit sagen will ist nur, dass ich bisher nicht die Möglichkeit hatte grundlegend daran was zu ändern. Er Ersetzung der Power-Methode ist natürlich ratsam, aber eine schnelle ließe sich wohl nur mit Assembler programmieren, jedoch hat bisher niemand diesen konstruktiven Vorschlag gemacht.

Zitat:

Der obige Code ist also programmtechnisch eine falsche Umsetzung der nötigen Mathematik. Du solltest dir an solchen Beispielen kein Beispiel nehmen.

"programmtechnisch eine falsche Umsetzung"? Unvollständig, suboptimal oder nicht gelungene ist vielleicht besser angebracht. Falsch ist das oben m.E.n. nicht. Lasse mich gerne aber eines besseren belehren.

Zitat:

Der richtige Weg wäre die Implementation einer eigenen modularen Exponentation die mit Ganzzahlen arbeitet. Beim Fermat Test MUSS jedes einzelne Zahlenbit absolut exakt berechnet werden, Fließkommazahlen haben darin nichts zu suchen.

Bei kleinen Zahlen nicht falsch, sondern eher suboptimal. Ich muss aber sagen, dass ich bei meinem Ursprungs-Posting nicht an die Fließkomma-Verwendung gedacht habe. Wobei ich beim Lesen gerade merke, dass es natürlich noch eine andere Möglichkeit gibt, als Assembler. Nicht dran gedacht.
Allerdings hättest du auch deine Kritik ein wenig früher üben können, als die Funktion auf diese Art und Weise zu zerreißen.

Zitat:

Es ist besser hier in Forum nach meinem schnellen Primzahltest zu suchen.
Anbei mein Code zum schnellen Test einer Zahl < 2^32 auf Primzahleigenschaft.
Der normale Fermat Test wie oben gezeigt würde nämlich auch Zusammengesetzte Zahlen als Primzahlen ausweisen die garkeine Primzahlen sind. Ich weis nicht was deine Kids davon halten sollen wenn sie durch dummen Zufall eine sogenannte Carmichael Zahl eingeben und dein Program sagt ads es eine Primzahl wäre, obwohl ads natürlich bei Carmichaelzahlen falsch ist.

Schlauerweise steht ja auch unter dem Source - sofern du weitergelesen hast - dass es sich hier um einen NICHT-Primzahltest handelt. Carmichael-Zahlen sind natürlich auch problematisch, aber ich vertraue jetzt in diesem Fall auf die Wikipedia:

Zitat von Wikipedia:

Wenn man nur auf die Basis 2 testet, dann kann man nur bis 340 sicher sein, dass man zu 100% ein korrektes Ergebnis bekommt.

Bei den Kids sollte das wohl nicht das Problem werden. Allerdings kannst du mir nicht vorwerfen, dass mein Code keinen Primzahltest darstellt. Das soll es ja auch gar nicht.
Und wenn es dich wirklich stört, dass darin keine hoch-mathematischen Optimierung drinstecken: ich habe es bisher nicht geschafft Mathevorlesungen zu besuchen - dummerweise gibt es für mich noch sowas wie Schule. Für mich zumindest hat es gereicht, dass ich bereits mehrmals mit dem Fermattest zutun hatte und ich denke nicht, dass man mich dafür zerreißen kann, weil ich es nicht zu 100% perfekt umgesetzt habe - zumal sich beim Posting als Vorschlag kein Feedback bekommen habe, obwohl der Thread monatelang für Kritik freigegeben war.


Ich weiß nicht genau, aber dein zweiter Post widerspricht sich ein wenig zum ersten ("Der Ansatz ist ja auch richtig."), aber ich hab jetzt nur mal versucht mich ein wenig zu rechtfertigen...

Chris