Gibt es einen schnellen, funktionsfähigen Primgenerator?
Angenommen, ich habe eine natürliche Zahl n und möchte eine Liste (oder was auch immer) von allen Primzahlen bis zu n .
Der klassische prime-Sievealgorithmus läuft in O(n log n) time und O(n) space - für inperative Sprachen ist das in Ordnung, erfordert aber eine direkte Änderung der Listen und des wahlfreien Zugriffs auf grundlegende Weise.
Es gibt eine funktionale Version mit Prioritätswarteschlangen, die ziemlich glatt ist - Sie können es sich ansehen hier . Dies hat eine bessere Raumkomplexität bei ungefähr O(n / log(n)) (asymptotisch besser, aber im praktischen Maßstab umstritten). Leider ist die Zeitanalyse unangenehm, aber es ist fast O(n^2) (tatsächlich denke ich, dass es ungefähr O(n log(n) Li(n)) ist, aber log(n) Li(n) ist ungefähr n ).
Asymptotisch gesehen wäre es eigentlich besser, einfach die Primzahl jeder Zahl zu überprüfen, wenn Sie sie generieren, indem Sie eine sukzessive Testteilung verwenden, da dies nur O(1) space und O(n^{3/2}) time benötigen würde. Gibt es einen besseren Weg?
Bearbeiten: Es stellt sich heraus, dass meine Berechnungen einfach falsch waren. Der Algorithmus im Artikel ist O(n (log n) (log log n)) , was die Artikel erklären und beweisen (und die Antwort unten sehen), nicht das komplizierte Chaos, das ich oben angeführt habe. Ich würde immer noch gerne einen bona-fide O(n log log n) pure Algorithmus sehen, wenn es einen gibt.
3 Antworten
Hier ist eine Haskell-Implementierung von Melissa O'Neills Algorithmus (aus dem verlinkten Artikel). Im Gegensatz zu der Implementierung, mit der Gassa verbunden ist, habe ich Faulheit nur minimal ausgenutzt, so dass die Performance-Analyse klar ist - O (n log n log log n) , dh linear in n log log n, die Anzahl der Schreibvorgänge, die vom Imperativ Sieve von Eratosthenes gemacht wurden.
Die Heap-Implementierung ist nur ein Turnierbaum. Die Ausgleichslogik ist in push ; Indem wir die Kinder jedes Mal austauschen, stellen wir sicher, dass für jeden Zweig der linke Teilbaum die gleiche oder eine größere Größe hat als der rechte Teilbaum, wodurch die Tiefe O (log n) gewährleistet wird.
Hier ist es, wenn (Haskell's) reine Arrays als rein zählen (sie sollten, IMO). Die Komplexität ist offensichtlich O (n log (log n)) , vorausgesetzt accumArray gibt tatsächlich O (1) Zeit für jeden gegebenen Index aus, wie es sollte:
Berechnet Primzahlen nach Segmenten zwischen aufeinanderfolgenden Quadraten von Primzahlen (das map (^2) -Bit) und erzeugt die Komposite durch Aufzählen der Vielfachen von wachsenden Präfixen von Primzahlen (das inits -Bit), genauso wie jedes geeignete Sieb von Eratosthenes, wiederholt Ergänzungen.
Also werden die Primzahlen {2,3} verwendet, um ein Segment von 10 nach 24 zu filtern; {2,3,5} von 26 bis 48 ; und so weiter. Siehe auch .
Auch ein Python Generator-basierte Sieb könnte auch als funktional angesehen werden. Pythons dict s sind extrem gut, empirisch , obwohl ich mir über die genauen Kosten nicht sicher bin das mehrfache Überproduktionsschema, das dort verwendet wird, um doppelte Zusammensetzungen zu vermeiden.
update: testet es produziert tatsächlich wie erwartet gute Ergebnisse:
%Vor% mit empirischen Wachstumsordnungen berechnet für die Erzeugung von n Primzahlen, wobei O (n log log n) wird üblicherweise als n 1.05 ... 1.10 und O (n log n log log n)
Die "geschachtelte-feed" Variante implementiert die Verschiebung Technik (wie auch in der oben verlinkten Python answer ), die eine quadratische Reduktion der Heap-Größe erreicht, die offensichtlich einen spürbaren Einfluss auf die empirische Komplexität hat, auch wenn sie das noch nicht ganz erreicht Ergebnisse für den Array-basierten Code dieser Antwort, mit dem 10 Millionen Primzahlen in weniger als 10 Sekunden auf ideone.com produziert werden können (mit insgesamt Wachstumsrate von nur n <1,09 im getesteten Bereich).
( "Original-Heap" ist natürlich der Code von die andere Antwort hier).
Ich habe vor einer Weile eine Primzahl erzeugende Funktion (erzeugt alle Primzahlen in der Reihenfolge) abgeleitet. Erstellt einen 6-seitigen Beweis dafür. Ich denke, es ist die erste hauptgenerierende Funktion in der Geschichte (zumindest konnte ich keine anderen Beispiele finden).
Hier ist es:
(-1)^((4*gamma(x)+4)/x)-1
Nicht sicher, wie schnell es berechnet werden kann. Es gibt 0 für alle Primzahlen zurück (oder vielleicht war es 1, kann mich nicht erinnern). Die Gammafunktion ist im Wesentlichen faktoriell, so dass sie früh schnell sein kann. Das Erhöhen von negativem 1 zu einem gebrochenen Exponenten ist ein ganz anderes Biest, obwohl ich glaube, dass es Integrale in der Basis oder mögliche trigonometrische Funktionen verwendet; kann mich nicht erinnern.
Ich kenne LaTeX nicht, also wenn jemand meinen Beitrag bearbeiten und eine LaTeX-Version hinzufügen möchte, wäre das erstaunlich!
Tags und Links algorithm functional-programming primes