Create Random Primes

  • C++

Es gibt 25 Antworten in diesem Thema. Der letzte Beitrag () ist von exc-jdbi.

    Create Random Primes

    Hallo Community

    Ich hab mir jetzt einen Create Prime Algorithmus erstellt.

    Mich würde nur interessieren. Findet ihr das schnell?
    Es sind hier nur mal 5 Stück a 19 stellen gezeigt.

    Im Moment ist es noch in C++ geschrieben. Ich werde den Code in den nächsten Tagen noch ins C# und Vb.Net umschreiben, und hier
    reinhängen.


    Der Aufbau ist sehr einfach
    - Random erzeugt Zufallszahlen (bis max 20-stellen)
    - Für die Prüfung brauche ich normale Zahlen aus einer Schleife von 2 weg aufwärts.
    - Mit ggt ein kurzer check ob die aus der Schleife kommende Zahl teilfremd ist
    - Mit Fermat prüfe ich ob es sich um eine Primzahl handelt. (y mod x = 1)

    Der Algo besitzt noch keine parallele Verarbeitung, werde ich jedoch zu einem späteren Zeitpunkt irgendwann noch machen.

    Spoiler anzeigen



    EDIT: Habe zu einem späteren Zeitpunkt nochmals einen Thread erstellt über Primes. siehe hier:
    Power Fast Prime Generator


    Freundliche Grüsse

    exc-jdbi

    Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von „exc-jdbi“ ()

    Naja ich weis nicht in welcher Zeit es die schnellsten Algos schaffen. Außerdem beduetet Zeit garnichts... wenn du das Ganze auf nem i3 laufen lässt wird es langsamer swin wie auf nem i7. Deshalb misst man sowas meines Wissens nach in Instructions. Also wie viele ASM-Befehle dein Algo braucht bis er das Ergebnis hat.

    Lg Mokki
    ​Smartnotr - ein intelligentes Notizprogramm
    ​zum Thread

    Danke für die Antwort mokki

    Es handelt sich um einen i5. Der Rechner ist 10 Jahre alt, hat aber 2 Kerne. Bezüglich den Instructions, weiss ich dazu nicht viel zu sagen. Da kenne ich mich nicht aus. Müsste ich mal nachschauen, was damit gemeint ist. Nur soviel. Hier in C++ sind es 9 Funktionen inklusive Main.

    Ich werde versuchen den Code in Vb.Net und C# genau nach diesem Muster aufzubauen.

    Das sind die Funktionen ca. 140 Zeilen

    Quellcode

    1. - Numeric to Binary
    2. - GCD
    3. - Addition with mod-balance
    4. - Multiplication with mod-balance
    5. - Exponentiate with mod-balance
    6. - Modulo Calculation
    7. - Check if is prime with Fermat
    8. - Begin Calculation
    9. - Main


    Freundliche Grüsse

    exc-jdbi

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „exc-jdbi“ ()

    exc-jdbi schrieb:

    Bezüglich den Instructions, weiss ich dazu nicht viel zu sagen.

    ​Hier der Wikipedia Artikel dazu:
    ​en.wikipedia.org/wiki/Instructions_per_secondund mir ist noch etwas eingefallen. Man kann die Komplexität eines Algorithmuses bestimmen. Ich hab aber nur Mal im Zusammenhang mit Sortieralgorithmen davon gelesen und da mein Mathematik Verständnis noch nicht super groß ist, kann ich dir leider nicht sagen ob es dir weiterhilft...

    Lg Mokki
    ​Smartnotr - ein intelligentes Notizprogramm
    ​zum Thread

    Wie wäre es mal mit richtigem Code? Dann könnte man es auch deutlich besser beurteilen und vergleichen. Auf jeden Fall ist dies eine interessante Optimierungsaufgabe (erinnert mich irgendwie an die Berechnung der Länge von Collatz-Ketten, bei der ich am Schluss auf ca. 1/10 der ursprünglichen Laufzeit des Algorithmus gekommen bin).

    Was mich noch gewundert hat, ist, wie du mit dem Fermatschen Primzahltest Primzahlen mit vollständiger Sicherheit überprüfen willst: Dieser Test ist ja probabilistisch, nicht deterministisch, gibt also keine Garantie, dass es sich um eine Primzahl handelt.

    Hallo nafets

    Du sprichst da sicher die Carmichael-Zahlen an. Nun die Prüfung basiert zwar auf einer PrüfungArt aber nicht auf eine Prüfung mit einer Zahl. Es kann gewählt werden wieviele Prüfungen gemacht werden sollen. Ich denke durch das, dass unterschiedliche natürliche Zahlen verwendet werden, sinkt das Riskiko auf ein Minimum, dass es sich um eine Carmichale zahl handeln könnte.

    Mir sind die probabilistisch Prüfungen bekannt. Ob man die Fermatprüfung wirklich direkt dazuzählen kann denke ich nicht. Es ist von vielen Primzzahlentest einer der wirklich wenigen Tests die echte Primzahlen hervorbringen. Ich müsste das aber nochmals nachschauen. Das werde ich noch machen.

    Edit: Hab gerade gesehn Wikipedia zählt den Fermatscher Primzahltest wie du gesagt hast zu den probabilistisch Prüfungen. Nun gut. Für mich ist das woweit der erste Primzahlentest den ich gemacht habe. Ich werde bestimmt noch ein paar weitere machen, und werde dies dann beachten.

    Freundliche Grüsse

    exc-jdbi

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „exc-jdbi“ ()

    Ich persönlich würde den Miller-Rabin-Test verwenden, da man diesen deterministisch einsetzen kann und die Performance ziemlich gut ist. Zusätzlich lässt sich in deinem Bereich noch die Anzahl der Werte für ​a deutlich reduzieren (es müssen nur 2, 3, 5, 7, 11, 13, 17, 19 und 23 getestet werden). Das sollte sicherlich besser als der Fermatsche Primzahltest, wie du ihn anwendest sein.

    Den Miller-Rabin-Test hab ich schon in betracht gezogen :)

    Ich möchte zuerst den hier richtig umsetzen und nachher mich mit den anderen Tests wie Solovay-Strassen-Test, Miller-Rabin-Test, und vor allem noch die polynominallen Tests für ganz grosse Primzahlen beschäftigen.

    Danke für den Hinweis.


    Quellcode

    1. Solovay-Strassen-Test
    2. + g = ggt(a,p)
    3. + Satz von Euler b = a^((p-1)/2) >> b = 1 oder b = n-1
    4. + Jacobi-Symbol J(a,p) ≡ b mod n (muss gelten, und falsche Zeugen beachten)
    6. Miller-Rabin-Test
    7. + MRT(a,p)
    8. + Irrtumswahrscheinlichkeit ist geringer als Solovay-Strassen-Test
    9. + p >= 5
    10. + Zahl a ∈ {2,3,4,...,n−2}
    11. + siehe WIkipedia
    13. ECPP - Elliptic Curve Primality Proving
    14. + Wiki?
    16. AKS-Primzahltest
    17. + auch Agrawal-Kayal-Saxena-Primzahltest
    18. + Hat dieser Test heuete noch relevanz?


    Freundliche Grüsse

    exc-jdbi

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „exc-jdbi“ ()

    Ich hab mal schnell eine Version mit dem Miller-Rabin-Test implementiert (ist halt C#, sollte aber für Demonstrationszwecke ausreichen). Den MersenneTwister kann ich ggf auch gerne anhängen - der ist aber nur für das reproduzierbare Erzeugen von Zufallszahlen da (ich weiß nicht, ob System.Random bei gleichem Seed überall die gleichen Zufallszahlen generiert).
    Code

    BenchmarkDotNet-Ergebnis (wie bei dir generiert jeder Durchlauf der Methode 5 19-stellige Primzahlen, wenn ich keinen Fehler drin habe):

    Brainfuck-Quellcode

    1. Host Process Environment Information:
    2. BenchmarkDotNet.Core=v0.9.9.0
    3. OS=Microsoft Windows NT 6.2.9200.0
    4. Processor=Intel(R) Core(TM) i7-4770K CPU 3.50GHz, ProcessorCount=8
    5. Frequency=3423908 ticks, Resolution=292.0639 ns, Timer=TSC
    6. CLR=MS.NET 4.0.30319.42000, Arch=64-bit RELEASE [RyuJIT]
    7. GC=Concurrent Workstation
    8. JitModules=clrjit-v4.6.1055.0
    10. Type=Benchmark Mode=Throughput
    12. Method | Median | StdDev |
    13. --------------------- |---------- |---------- |
    14. RandomPrimeGenerator | 1.0428 ms | 0.0254 ms |


    Ich würde mal behaupten, dass das für eine 10min-Implementation ziemlich schnell ist :P

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „nafets“ ()

    Danke nafets

    Ich werd mir den Code anschauen.

    Übrigends habe ich mit meinem Code soeben die hier erwähnten Carmiachel-Zahlen geprüft. Sie werden bei mir nicht als Primzahlen ausgegeben, nicht einmal wenn ich meine Prüfungen auf die Mindestzahl von 3 (Prüfungen mit 3 verschiedenene natürlichen Zahlen) auslege.

    Ich denke das was ich hier gemacht habe, ist brauchbar. Aber ich lass euch dann die Beurteilung machen.

    Freundliche Grüsse

    exc-jdbi

    exc-jdbi schrieb:

    Ich denke das was ich hier gemacht habe, ist brauchbar. Aber ich lass euch dann die Beurteilung machen.

    Brauchbar ist es sicherlich, doch wenn man deine ~850ms mit meiner 1ms-Zeit vergleicht, ist bei dir doch sicher noch ordentlich Verbesserungspotential ^^ (ich will jetzt jedoch nicht behaupten, dein Ansatz sei schlecht - wenn er funktioniert, ist das mMn schonmal ne tolle Leistung)
    Generell finde ich solche Aufgaben immer sehr interessant, da man fast jedes Mal wieder neue Ansätze kennen lernt. Mein Ansatz bspw. ist sicherlich auch noch nicht außerordentlich gut - das wäre doch ne interessante Sache, bei sowas an den Feinheiten zu schrauben, oder? ;)

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „nafets“ ()

    Mit meinem i5, CPU 2.0GHz kann da nie mithalten. Und ja interessant wäre es, den noch zu optimieren, sofern da noch was machbar wäre. Hab deinen Code nur überflogen. :D

    Woher hast du die MersenneTwister-Klasse? Selber gemacht oder aus dem Internet runtergelladen. Oder ist die im >FW4.0 drin?

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „exc-jdbi“ ()

    Ich kann ja ggf. die Projektmappe hier reinstellen, sodass du auf deinem PC mal einen Vergleich zwischen den beiden Versionen in derselben Umgebung machen kannst.

    Interessant fände ich übrigens noch, ob man hier mit SIMD-Optimierungen irgendwas verbessern könnte.

    Ja gerne. Den vergleich würde ich gerne mal machen. Ich schätze das mein Rechner mit deinem Code ca. 10 ms hat, also 10 mal länger als mit deinem Rechner.

    Mit Optimierungen muss ich mich noch ein bisschen zurückhalten, ich kenne da lange nicht die Möglichkeiten.


    Ich habe mal die Projektmappe angehängt. Du musst VS vor dem Starten die NuGet-Pakete wiederherstellen lassen (das geht normalerweise automatisch) und dann RandomPrimes.Test als Startprojekt festlegen. Dann kannst du in die Release-Konfiguration aktivieren & mit Strg + F5 das Programm ohne angehängten Debugger starten (ich beschreibe das mal so ausführlich, damit ggf. auch Andere das reproduzieren können).

    Falls du Interesse & Zeit hast, kannst du gerne mal schauen, ob man bspw. die Prüfung der verschiedenen Basen (a) mit Performancegewinn parallelisieren kann oder ob es eine bessere Alternative für die diskrete Exponentialfunktion, vielleicht auch unter Vernwendung von SIMD (ich verwende der Einfachheit halber BigInteger.ModPow()) gibt. Speziell wäre aber auch interessant, ob irgendein anderer deterministischer Prim-Test-Algorithmus schneller ist (der Miller-Rabin-Algo müsste eigentlich so ziemlich der schnellste Algorithmus sein - er wird ja sicher auch nicht ohne Grund in den meisten Fällen eingesetzt).
    Vielleicht habe ich ja sogar irgendwo einen Fehler drin :D

    Außerdem habe ich noch zusätzlich mal 500k Primzahlen ([1E14, 1E15]) generiert, falls jemand Interesse hätte, die generierten Zahlen etwas genauer zu analysieren (ob es wirklich alles Primzahlen sind & ob die Verteilung wirklich gleichmäßig ist).

    Edit: Ich hatte noch die falsche Variante vom Benchmark (zu kleine Zahlen) hochgeladen - hab gerade schnell die Projektmappe aktualisiert.
    Dateien

    Dieser Beitrag wurde bereits 3 mal editiert, zuletzt von „nafets“ ()

    Werde ich mir morgen noch genauer anschauen. Arbeite immer noch mit FW4.0. Ist aber kein Problem. Bis jetzt habe ichs immer irgendwie zum laufen gebracht. :D

    Danke nochmals.

    Freundliche Grüsse

    exc-jdbi

    Edit:
    Hab kurz reingeschaut. Coole Sache. Musste jedoch das ganze Benchmarkt-Zeugs rauswerfen, da ich es auf meinem nicht eingebunden habe (Arbeite noch mit FW4.0). Es funktioniert jedoch, und mit ein paar kleine Anpassungen, hab ich's dann zum Laufen gebracht.
    Was mir ganz gut gefällt, ist dass du mit dem initialRandom eine Suchrichtung gibst, ab dem dann die nächste Prime gesucht wird. So etwas könnte ich bei mir auch einbauen, dass würde den Algo ungemein schneller machen. Bei mir ist es so das einfach immer eine neue Random generiert wird. Das begründet auch bei mir die hohe Verarbeitungszeit.
    Hier noch ein pic. Die Werte verlaufen bei mir immer um 60 - 75 ms. Den mit 47 ms, habe ich mir gleich abgespeichert.


    Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von „exc-jdbi“ ()

    exc-jdbi schrieb:

    Bei mir ist es so das einfach immer eine neue Random generiert wird. Das begründet auch bei mir die hohe Verarbeitungszeit.

    Dein Ansatz hat zusätzlich noch ein spezielles, weiteres Problem: Im theoretischen schlimmsten Fall wäre die Laufzeit unendlich, da dein Algorithmus theoretisch immer wieder dieselben Nicht-Primzahlen ausspucken kann. Der Ansatz mit dem von einer Stelle aus Weitersuchen ist da etwas besser: Wenn es in der Periode mindestens eine Primzahl gibt, ist die maximale Laufzeit begrenzt, da im allerschlimmsten Fall ein Mal das gesamte Intervall abgesucht wird.

    Ich hatte übrigens noch eine relativ simpel umzusetzende Optimierungsidee: Bevor man den rechnerisch aufwendigen Miller-Rabin-Algo einsetzt, könnte man ja vor ihm einen probabilistischen Test ausführen, welcher die meisten Nicht-Primzahlen schnell aussortiert. Gesagt, getan: Ich habe zu Testzwecken mal 3 Vor-Check-Methoden ausprobiert:
    NameErklärungPre-Check-Degree / Iterationen
    Incremental FermatFermatscher Primzahltest für a = [2 .. i + 2]0, 5, 10, 15, 20, 25, 30
    Random FermatFermatscher Primzahltest für a = [2, n - 2], i mal ausgeführt0, 5, 10, 15, 20, 25, 30
    Prime-FactorPrüfung auf die kleinsten i Primfaktoren0, 2, 4, 6, 8, 10, 12

    Wenn man sich die Ergebnisse als Diagramm ansieht, ist das Ergebnis eigentlich ziemlich klar (die absoluten Zeiten sind zwischen den Benchmarks nicht vergleichbar, da die Anzahl der generierten Primzahlen an deren Größe angepasst ist; Achtung: Die Y-Achse der Diagramme beginnt nicht bei 0):

    Man kann ziemlich leicht erkennen, dass die Vor-Check-Methoden, welche auf dem Fermatschen Primzahltest basieren mit zunehmender Genauigkeit (Pre-Check-Degree) die Laufzeit linear erhöhen - sie sind also kaum für diesen Zweck geeignet. Die Methode mit dem Überprüfen von möglichen kleinen Primfaktoren scheint jedoch sehr gut zu funktionieren - sie verringert die Laufzeit deutlich. Ich werde vielleicht später noch versuchen, den Idealwert für die Anzahl von zu prüfenden Primfaktoren zu ermitteln.
    Auf jeden Fall kann man mit dieser Methode eine Verbesserung von mindestens 1/3 erreichen, was mMn ganz gut ist (für die 5 19-stelligen Primzahlen braucht unter Benchmarkbedingungen es ca. 0,75ms).

    Code mit Vor-Checks



    Dateien

Facebook
Telefonspende