Primzahl-Check: Javascript > Delphi

[negaH]

@Zecke:

schau dir wirklich mal den Link den ich dir gegeben habe an. Der von euch verwendetet Algorithmus ist in seiner Komplexität viel zu schlecht. Es geht also viel schneller, besonders bei großen Zahlen wird das deutlich. Probiere doch mal $FFFFFFFB aus.

Gruß Hagen

[alzaimar]

Zitat von negaH:

@Zecke:
schau dir wirklich mal den Link den ich dir gegeben habe an. Der von euch verwendetet Algorithmus ist in seiner Komplexität viel zu schlecht.

Also, ich find' Dein ASM-Gewurschtle ehrlich gesagt, viel viel komplexer, aber Du meinst bestimmt 'Big Oh', bzw. den Zeitaufwand. Wenn ich bei 32 bit Zahlen gar nicht warten muss, reicht das doch. edit: Nicht das Du das missverstehst, dein Code ist wirklich marginal schneller: Nur etwas über 100 mal, das ist doch ... pah... ernüchternd

Welche Regeln verwendet denn der Algo? Das wäre imho interessant. Du scheinst da wirklich ein Experte zu sein.

[negaH]

Der Algo. basierst auf einem SPP = Strong Pseudo Prime Test zu festen Basen. Auf http://primes.utm.edu/prove/prove2_3.html kannst du das nachlesen.

Zitat:

If n < 9,080,191 is a both 31 and 73-SPRP, then n is prime.
If n < 4,759,123,141 is a 2, 7 and 61-SPRP, then n is prime.

besonders diese Passage ist interessant da sie bei meinem Algorithmus angewendet wird.

Zusätzlich wird aber ein schnellerer Test vorgschaltet der den Kandidaten zu den ersten 32 Primzahlen bis 137 testet. Es ist also eine einfache Trial Division falls der Kandidat < 137 * 137 ist.

Bei beiden Tests werden extensiv modulare Divisionen benötigt. Die CPU Laufzeit der Divisionen ist aber wesentlich schlechter als die der Multiplikation. Ergo: wird der erste schnelle Test nicht per Divisionen durchgeführt sondern per Multiplikationen, man "dividiert modular" indem man mit dem modualeren Inversen der kleinen Primzahlen zu 2^32 den Kandidaten testet.

Eine ähnliche "Ersetzung" der langsammen Divisonen habe ich auch im nachfolgendem SPP Test angewendet. Statt aber mit dem modularem Inversen zu arbeitet arbeitet der SPP Test, bzw. genauergesagt dessen modulare Exponentation in der sogenannten Montgomery Domain. Montgomery war ein Mathematiker der verschiede Tricks entdeckt hat, ua. eben auch seinen am meist bekannten "Montgomer Trick". Mit diesem ist es möglich eben eine modulare Exponentation so umzubauen das statt der vielen modularen Divisionen nur Multiplikationen benötigt werden.

Die obige Unit ist dabei eine Weiterentwicklung meines ursprünglichen Sources, in einem Contest im FastCode Projekt. Mein ursprünglicher Source nutzte zb. eben nicht die Trialdivision zu den ersten 32 Primzahlen. Allereine schon dieser Test eliminiert eine sehr große Anzahl von zusammengesetzten Zahlen.

Bei beiden Tests lässt sich nun Assembler leider nicht vermeiden. D.h. eine reine PASCAL Imlpementation wäre eventuell zwar möglich würde aber einen enormen und unnötigen Overhead im erzeugten Compilat bedingen. Das ich also Assembler gewählt habe liegt im Grunde nur daran das nur damit bestimmte Operationen möglich waren. Zb. wird ein Überlauf bei mathem. Operationen durch die Auswertung der Prozessorflags als notwendiges Feature des Algorithmus durchgeführt. In reinem PASCAL hat man aber diese Möglichkeit nicht. Das der Code in Assembler ist liegt also nicht daran das er primär auf Performance entwicklet wurde, sondern nur daran das so die Möglichkeiten der CPU ausgenutzt werden konnten.

Zitat:

Du meinst bestimmt 'Big Oh'

Ja, eben die Komplexität des Verfahrens die als Big O angegeben wird.

Hagen schrieb:

Zitat:

Der von euch verwendetet Algorithmus ist in seiner Komplexität viel zu schlecht.

Gruß Hagen

[alzaimar]

Ich wollte schon den Fermat-Test vorschalten, aber scheiterte eben an diesem a^n mod (n-1)... Da hat Montogomery wohl einen Trick gefunden, sehe ich das richtig? Ich finde das wirklich sehr spannend und würde liebend gern meine Zeit mit solchen Geschichten verbringen, aber was mach ich? Projekte durchziehen, Beratung, etc... Man kann nicht Alles haben.

Auf jeden Fall danke für die Info.

Ach, O(Sqrt(N)) ist doch aber nicht zuuuu schlecht, oder? Der eine oder andere Algo wäre froh, wenn er so komplex wäre...

[negaH]

Erst die schlechte Nachricht, obiger Source ist ein Cut aus meiner Contributation zum FastCode Projekt, und wie üblich: er ist fehlerhaft. Anbei also die korregierte Version. Denn ich bon stutzig geworden als du schriebst das der Test "nur" 100 mal schneller als euer sein sollte. Er sollte nämlich bei weitem schenller laufen. Am besten mal alle ungeraden Zahlen von 1 bis 2^32-1 in einer Schleife durchlaufen lassen und die gemessene Zeit dann durch 2^31 teilen. Das ergibt dann den korrekten Zeitbedarf beider Verfahren.

Zitat:

Fermat-Test vorschalten, aber scheiterte eben an diesem a^n mod (n-1)...

Dieser Test ist veraltet und stellt die Basis des Rabin-Miller Verfahrens dar. Besser ist ein Strong Probable Pseudo Prime Test zu festen Basen.

Statt also a^n mod (n-1) wird folgenes benutzt:

N-1 = 2^s * d -> also s ist die Anzahl der trailing Null Bits in N. Man wird also N-1 solange rechts shiften wir das unterste Bit 0 ist. Dabei zählt man S in jedem Schritt +1 höher.

Nun folgt mit diesem zu ermitteltem d die modulare Exponentation bis

a^d == 1 mod n

oder

(a^d)^2^r == -1 mod n

ist, r wird dabei von 0 bis s iteriert. Die Kongruenz von == -1 mod N wird in positiven modularen Ringen vereinfacht dadurch das -1 mod N == (N -1) ist.

Gruß hagen

[negaH]

Zitat:

Da hat Montogomery wohl einen Trick gefunden, sehe ich das richtig?

Nicht für die Exponentation ansich. Im obigen Link zum Fastcode Projekt findest du verschiedene Verfahren. In meiner Unit wurde diese Exponentation einerseits mit normalen Division, also in der Normal Domain, und andererseits in der Montgomery Domain implementiert.

Man kann also die modulare Exponentation durchaus mit normalen Zahlen umsetzen und benötigt dazu nicht zwangsweise den Montgomery Trick. Der Trick ansich ändert nur die Zahlendarstellung auf eine Art & Weise das die wiederholt nötigen modularen Redukationen nach den modularen Multiplikationen eben nicht per Divisionen sondern mit Multiplkationen durchgeführt werden können. Da nun Multiplikationen auf Intel CPU's weitaus schneller sind ist diese Vorgehensweise sinnvoll.

Essentiell benutze ich zb. den Montgomery Trick in meiner Large Integer Library mit Integern bis zu 2^4096. Alles was darüber ist ist dann mit der schnellen Karatsuba Division nach Burnikel&Ziegler wieder wesentlich Performanter.

Mein erster Source den ich vor ca. 10 Jahren schrieb nutzt eben nicht die Montgomery Domain. Erst vor 2 Jahren, in der FastCode Competition, habe ich meinen IsPrime() Algo. auf Montgomery umgesetellt. Dies wurde sozusagen nötig da meine Competior meinen ursprüglichen Code durch Detailverbesserungen immer schneller machten. Eine weitere Beschleinigung des Verfahrens war also nur noch möglich indem ich neben dem Montgomery Trick die Trial Division ins Rennen warf und später diese Trial Division mit den modularen Inversen + Multiplikationen ausbaute

Sogesehen: der obige Source konnte nur entstehen weil sich verschiedene Leute in der FastCode Competition gegenseitig motivierten.

Gruß Hagen

[KLS]

Zitat von zecke:

Ja mag sein ^^ aber ich habe jetz die erste so schön eingebaut und wie soll ich sagen... nun ich gehöre zu den gemütlichen Menschen

Ich änders mal in die zweite um :> - danke dir

edit: hab sie eingebaut:

Zitat:

Nach Test eins ist 2147483647 eine Primzahl
Das herauszufinden dauerte 26562ms
Nach Test zwei ist 2147483647 eine Primzahl
Das herauszufinden dauerte 13875ms

beide zusammen dauert aber verdammt lange deswegen benutze ich nur die zweite.

(mal aus dem urschleim hervorkram)

Also meine funktion (drei) topt das bei weitem...

Nach Test eins ist 2147483647 eine Primzahl
Das herauszufinden dauerte 22148.4769255396ms
Nach Test zwei ist 2147483647 eine Primzahl
Das herauszufinden dauerte 10020.2887859163ms
Nach Test drei ist 2147483647 eine Primzahl
Das herauszufinden dauerte 0.411961755996052ms

die funktion von hagen hab ich mir noch nicht angeschaut.

[alzaimar]

Zitat von KLS:

Nach Test drei ist 2147483647 eine Primzahl
Das herauszufinden dauerte 0.411961755996052ms

die funktion von hagen hab ich mir noch nicht angeschaut.

Das würde ich aber mal tun, den Deine ist sogar langsamer als meine primitive Funktion ('IsPrime'). Vorausgesetzt, man ersetzt Int64 durch Cardinal.

[KLS]

wahnsinn.

Nach Test vier ist 2147483647 eine Primzahl
Das herauszufinden dauerte 0.00393678467571966ms

Da muss ich doch jetzt echt überlegen, was ich an meiner funktion noch optimieren könnte. aber so spontan fällt mir da nix ein.

[alzaimar]

Na, das Verfahren. Was sonst. Oder wie rechnest du das aus?