Primzahlen finden - Zeit optimieren

[Hag2bard]

Ein Kollege von mir und ich, sind auf der Suche danach, wie man eine Primzahlenberechnung noch zeiteffizienter gestalten könnte.

Meine Methode hierzu:

[CODE lang="java" title="Primzahl Methode"] private boolean isPrim(int number) {
for (int i = 2; i < number - 1; i++) {
if (number % i == 0) {
return false;
}
}
return true;
}[/CODE]

Wenn er Primzahlen bis 1.000.000 sucht, braucht er dazu etwa 95000ms, je nachdem wie mein Computer gerade so drauf ist.

Jetzt fragen wir uns, wie kann man diese Methode optimieren, dass es schneller geht.

Kann man die Methode auf mehrere Threads aufteilen?
Ist eine andere Schleife schneller?
Gibt es sonst noch etwas was das ganze beschleunigen könnte?

 

[LimDul]

* Anstelle bis number-1 zu testen, reicht es bis zur Wurzel(number) zu testen.
* Anstelle alle Zahlen als teiler zu testen, reicht es die 2, sowie alle ungeraden Zahlen zu testen.

Wenn du nicht nur testen willst, ob eine Zahl X eine Primzahl ist, sondern alle Primzahlen bis X bekommen, ist das Sieb des Eratosthenes ein geeignetes Verfahren.

 

[kneitzel]

Du kannst direkt die Grenze verändern. Statt bis number-1 musst Du nur bis zur Wurzel aus number gehen.

 

[httpdigest]

Wenn du die effizientesten Prime-Sieve Implementierungen (in irgendeiner Programmiersprache) suchst:

GitHub - PlummersSoftwareLLC/Primes: Prime Number Projects in C#/C++/Python

Prime Number Projects in C#/C++/Python. Contribute to PlummersSoftwareLLC/Primes development by creating an account on GitHub.

github.com

 

[LouCyphre]

Kann man die Methode auf mehrere Threads aufteilen?
Ist eine andere Schleife schneller?
Gibt es sonst noch etwas was das ganze beschleunigen könnte?

Du kannst auf mehrere Threads aufteilen.
Wenn du den 1. Thread von 1 - 250.000, den 2. Thread von 250.001 - 500.000 usw. aufteilst, kannst du sicher ein Bisschen was rausholen.
Wenn du den Intervall so festlegst, gibt es auch keine run condition oder so.

 

[mihe7]

1. Sonderfall 2 behandeln (EDIT: damit sind die 2 und gerade Zahlen gemeint).
2. In der Schleife ab i=3 zählen und nur die ungeraden Zahlen (i+=2) berücksichtigen.
3. Schleife nur bis sqrt(n) zählen lassen.

Wenn du den Intervall so festlegst, gibt es auch keine run condition oder so.

Eine race condition gäbe es hier sowieso nicht, da nichts geschrieben wird. Man kann also höchstens Zeit verplempern. Inwiefern und ab wann sich hier Multithreading lohnt, müsste man messen und die Implementierung ist nicht zu unterschätzen, schließlich macht es keinen Sinn, die Threads weiterlaufen zu lassen, wenn in einem Thread festgestellt wurde, dass es sich um keine Primzahl handelt.

 

[kneitzel]

Wenn du dich schon etwas mit Streams beschäftigt haben solltest, dann wäre ein einfacher Weg, es per parallel Stream zu machen.

Das wäre aus meiner Sicht eine einfache Möglichkeit, es zu parallelisieren. (Und das noch relativ optimal, denn es wird eine relativ gute Anzahl paralleler Threads gewählt)

 

[temi]

3. Schleife nur bis sqrt(n) zählen lassen.

final int limit = (int)Math.sqrt(number);
for(int i = 3; i < limit; i += 2 ) {
   
}

// ODER

for(int i = 3; i < Math.sqrt(number); i += 2 ) {
   
}

Gibt es da einen Unterschied oder wird das sowieso optimiert?

 

[kneitzel]

Ersteres wäre besser, da die Wurzel sonst regelmäßig berechnet würde. Eine Optimierung ist nicht möglich aus meiner Sicht, denn woher soll der Compiler wissen, dass die Methode bei einem Wert immer das gleiche Ergebnis bringt? Math könnte ja auch einen statischen Zustand haben der sich verändert....

Edit: wird evtl. deutlich, wenn man statt Math.sqrt Math.random aufruft... ohne die Methode zu kennen, ist eine Optimierung nicht möglich.

 

[httpdigest]

Eine Optimierung ist nicht möglich aus meiner Sicht, denn woher soll der Compiler wissen, dass die Methode bei einem Wert immer das gleiche Ergebnis bringt? Math könnte ja auch einen statischen Zustand haben der sich verändert....

Im Falle von Math.sqrt() wird der Compiler dies als intrinsische Funktion betrachten und aus der Schleife herausziehen, da er weiss, dass Math.sqrt() eine pure Funktion ist, also von keinem Zustand abhängig ist.

Das ist auch in vielen anderen Fällen möglich, wenn die Methode nicht riesengross ist und irgendwann sowieso ge-inline-d wird.

Fazit: Es wird keinen Performanceunterschied machen.

 

[kneitzel]

Im Falle von Math.sqrt() wird der Compiler dies als intrinsische Funktion betrachten und aus der Schleife herausziehen, da er weiss, dass Math.sqrt() eine pure Funktion ist, also von keinem Zustand abhängig ist.

Das ist auch in vielen anderen Fällen möglich, wenn die Methode nicht riesengross ist und irgendwann sowieso ge-inline-d wird.

Fazit: Es wird keinen Performanceunterschied machen.

Da würde mich interessieren: Woran erkennt der Compiler dies?

 

[httpdigest]

Kurz zur Klarstellung: Mit "Compiler" meine ich hier den JIT Compiler, also HotSpot.
HotSpot weiss (hart einprogrammiert) um das Verhalten von bestimmten intrinsischen Funktionen (ganz viele aus Math.sqrt() + aus anderen Klassen). Basically überall wo die Annotation @HotspotIntrisicsCandidate (oder so) dransteht. Diese werden auch gleich sofort (ich glaube schon bei C1) durch ihren Maschinencode beim Aufrufer ersetzt.
Falls eine Methode keine (Hotspot)-intrinsische Methode ist, wird spätestens der C2 Compiler bei entsprechend häufigen Aufrufen der Methode aggressive Optimierungen durchführen. Dazu gehören zuallererst einmal das aggressive Inlinen von Methodenaufrufen (also das Ersetzen der Methodenaufrufe durch seinen Body an der Aufrufstelle). Das passiert solange rekursiv, bis ein Budget/Limit an Bytecode-Länge erreicht ist. Das ist für heisse/häufige-aufgerufene Methoden irgenwas um die 600 oder 700 Bytes (nicht Instruktionen!).
Spätestens dann sieht der Compiler in diesem "Inlining-Frame" alle Instruktionen, und da sich irgendwann jede Methode auf nur die Primitive Speicherzugriff und Arithmetik bzw. logische Operationen reduzieren lassen, kann sich der Compiler einfach den Datenfluss der Operationen angucken. Wenn er sieht, dass Math.sqrt() (bzw. jede andere stattdessen aufgerufene Methode) keine lesenden oder schreibenden Speicherzugriffe (auf z.B. Instanzvariablen oder statische Variablen) durchführt, weiss er, dass er diese Methode aus der Schleife herausziehen kann.
Also mit Data Flow Analyse.

 

[kneitzel]

Ok, habe dazu selbst noch etwas gefunden:

Introduction to JVM Intrinsics | Baeldung

A quick and practical overview of intrinsics and how they work in Java.

www.baeldung.com

Danach kann man sich nicht darauf verlassen und es kann von System zu System unterschiedlich sein. Und bei der Hotspot JVM hat die JVM selbst eine spezielle Implementierung für viele Methoden aus Math.

Und hier abgebrochen - danke für die Erläuterung @httpdiggest

 

[httpdigest]

Ja, bei z.B. der Dalvik VM oder wie heutzutage die Android VM heisst, kann das wiederum gaaaanz anders aussehen. Die kann fast gar keine Optimierungen von alleine machen. Da würde sich das manuelle Herausziehen wahrscheinlich schon eher lohnen.

 

[kneitzel]

Das ist ein Punkt, den ich so noch nicht betrachtet habe - um so interessanter ist es gerade. Und daher werde ich mir das auch noch einmal im Detail ansehen:
a) @HotspotIntrisicsCandidate
b) Ich versuche, zu ein paar Tests zu kommen: Hotspot, J9 und GraalVM würde ich gerne testen / vergleichen. Und Android ist auch ein interessanter Punkt - den werde ich auch mit aufnehmen.

Aber aus meiner Sicht ist das "nice to know", aber im Augenblick sehe ich nicht die Auswirkungen, die es auf meinen Code haben wird. Der Artikel bei Baeldung klingt halt definitiv so, dass man sich nicht darauf verlassen sollte.

There is, unfortunately, no guaranteed way to identify methods that might be replaced with intrinsic versions. This is because different JVMs or even the same JVM on different platforms will do this for different methods.

We can't write our programs to rely on the presence of intrinsics because there's no way to know if they'll be available or not on the runtime JVM.

(Quelle: https://www.baeldung.com/jvm-intrinsics)

Da werde ich dann - bei Gelegenheit - auf jeden Fall noch mehr recherchieren und mal schauen, was ich da noch alles an guten Quellen finden werde. Ist auf jeden Fall ein interessanter Punkt, den ich bisher nicht im Fokus hatte.

Oder in anderen Worten: "Puhh, Schwein gehabt, war meine Antwort in #9 zumindest kein reiner Bockmist!" 😂 😂 😂 😂 😂

 

[mihe7]

Gibt es da einen Unterschied oder wird das sowieso optimiert?

Ich würde auch die erste Variante bevorzugen, diesen Compiler-Optimierungen traue ich nicht recht

 

[temi]

Ich würde auch die erste Variante bevorzugen, diesen Compiler-Optimierungen traue ich nicht recht

Kurze Antwort ist also: Macht man es selbst, dann kann man sicher sein, dass es so ist. Andernfalls kann es sein, aber auch nicht.

 

[temi]

Und daher werde ich mir das auch noch einmal im Detail ansehen

https://jeeconf.com/program/hotspot-intrinsics/

 

[kneitzel]

Ich habe mal einen ganz einfachen Test gemacht.

Test-Sourcen eigentlich schon das aus dem Thread;

public class IntrinsicTest {
    public static int number = Integer.MAX_VALUE;

    public static void main(final String[] args) {
        long start1 = System.nanoTime();
        test1();
        long stop1 = System.nanoTime();
        System.out.println("Test 1 Time: " + (stop1 - start1));

        long start2 = System.nanoTime();
        test2();
        long stop2 = System.nanoTime();
        System.out.println("Test 2 Time: " + (stop2 - start2));
    }

    public static void test1() {
        final int limit = (int)Math.sqrt(number);
        for(int i = 3; i < limit; i += 2 ) {

        }
    }


    public static void test2() {
        for(int i = 3; i < (int)Math.sqrt(number); i += 2 ) {

        }
    }
}

Ich habe daraus jetzt keine Raketenwissenschaft gemacht - um irgendwelche Seiteneffekte durch Caching und Co zu sehen, habe ich test1 / test2 einfach mal umbenannt, so dass die Reihenfolge anders herum war.

Mein Testsystem war jetzt ein ZBook 15 G2 mit openSUSE Tumbleweed.

Tests mit GraalVM 21.2 für Java 16
konrad@linux:~/media/Extern/Projects/Test> javac IntrinsicTest.java
konrad@linux:~/media/Extern/Projects/Test> java IntrinsicTest
Test 1 Time: 188491
Test 2 Time: 398382
konrad@linux:~/media/Extern/Projects/Test> native-image IntrinsicTest
[intrinsictest:7098] classlist: 999.08 ms, 0.96 GB
[intrinsictest:7098] (cap): 566.62 ms, 0.96 GB
[intrinsictest:7098] setup: 2,187.36 ms, 0.96 GB
[intrinsictest:7098] (clinit): 183.76 ms, 1.75 GB
[intrinsictest:7098] (typeflow): 3,867.31 ms, 1.75 GB
[intrinsictest:7098] (objects): 3,788.91 ms, 1.75 GB
[intrinsictest:7098] (features): 469.95 ms, 1.75 GB
[intrinsictest:7098] analysis: 8,554.74 ms, 1.75 GB
[intrinsictest:7098] universe: 688.28 ms, 1.75 GB
[intrinsictest:7098] (parse): 776.90 ms, 1.77 GB
[intrinsictest:7098] (inline): 1,242.97 ms, 2.33 GB
[intrinsictest:7098] (compile): 8,499.97 ms, 2.39 GB
[intrinsictest:7098] compile: 11,079.60 ms, 2.39 GB
[intrinsictest:7098] image: 1,449.04 ms, 2.39 GB
[intrinsictest:7098] write: 255.98 ms, 2.39 GB
[intrinsictest:7098] [total]: 25,425.24 ms, 2.39 GB
# Printing build artifacts to: /run/media/konrad/Extern/Projects/Test/intrinsictest.build_artifacts.txt
konrad@linux:~/media/Extern/Projects/Test> ./IntrinsicTest.
bash: ./IntrinsicTest.: Datei oder Verzeichnis nicht gefunden
konrad@linux:~/media/Extern/Projects/Test> ls
intrinsictest intrinsictest.build_artifacts.txt IntrinsicTest.class IntrinsicTest.java
konrad@linux:~/media/Extern/Projects/Test> ./intrinsictest
Test 1 Time: 9821
Test 2 Time: 11767
konrad@linux:~/media/Extern/Projects/Test>

Mit AdoptOpenJDK 16 (HotSpot):
konrad@linux:~/media/Extern/Projects/Test> java IntrinsicTest
Test 1 Time: 193178
Test 2 Time: 393637
konrad@linux:~/media/Extern/Projects/Test>

Den WIndows Rechner werde ich erst am Montag prüfen können. Aber die Linux JVMs haben hier scheinbar diese Optimierung nicht durchgeführt.

 

[kneitzel]

Wenn du dich schon etwas mit Streams beschäftigt haben solltest, dann wäre ein einfacher Weg, es per parallel Stream zu machen.

Das wäre aus meiner Sicht eine einfache Möglichkeit, es zu parallelisieren. (Und das noch relativ optimal, denn es wird eine relativ gute Anzahl paralleler Threads gewählt)

Nur um das auch noch einmal aufzuzeigen, wie dies aussehen könnte:

import java.util.stream.IntStream;
import java.util.stream.Stream;

public class PrimeCheck {

    private static boolean isPrim(int number) {
        if (number == 2) return true;
        if ((number & 1) == 0) return false;

        int limit = (int)Math.sqrt(number) / 2;
        return !IntStream .rangeClosed(1, limit)
                .parallel()
                .map(n -> n*2+1)
                .filter(n -> number%n == 0)
                .findAny().isPresent();
    }

    public static void main(String[] args) {
        System.out.println("2: " +isPrim(2));
        System.out.println("3: " +isPrim(3));
        System.out.println("4: " +isPrim(4));
        System.out.println("9: " +isPrim(9));
        System.out.println("17: " +isPrim(17));
        System.out.println("21: " +isPrim(21));

        for (int n =2; n<= Integer.MAX_VALUE; n++) {
            if (isPrim(n)) System.out.println(n + " ist eine Primzahl!");
        }
    }
}

Paar Dinge sind hier zu erwähnen:
- die 2 ist eine Primzahl - das ist ein erster Check.
- die Teilbarkeit durch 2 wird zuerst separat geprüft. Dazu mache ich einfach ein bitweises AND um dann zu schauen, ob das einer-Bit 0 ist.
- Man könnte Limit auf die Wurzel der Nummer setzen. Aber bei iterate haut das parallel() nicht wirklich hin (war zumindest, was ich gelesen habe). Daher habe ich das Limit durch 2 geteilt. Daher muss ich aber nun zu den jeweiligen Werten kommen und das ist *2 + 1:
1 -> 3
2 -> 5
3 -> 7
...
Und dann interessieren mich nur Teiler, d.h. die remainder Operation muss 0 ergeben.
Und dann interessiert mich nur ein erstes gefundenes Element - egal ob es der kleinste Teiler ist oder nicht.
Und wir haben eine Primzahl, wenn kein solcher Teiler gefunden wurde.

Die Laufzeit von dem Algorithmus habe ich jetzt nicht verglichen - das wäre ggf- noch etwas zum herumspielen

 

[httpdigest]

@kneitzel : zu deinem Benchmark: Verlässliche Benchmarks in Java zu schreiben, ist sehr sehr schwer, aufgrund der diversen Compilerstages, die für unterschiedlich häufige Ausführungen des Codes herangezogen werden.
JMH hat sich mittlerweile als das de-fakto Framework für Benchmarking mit der JVM etabliert:

import org.openjdk.jmh.annotations.*;
import org.openjdk.jmh.runner.Runner;
import org.openjdk.jmh.runner.options.OptionsBuilder;
import static java.util.concurrent.TimeUnit.MILLISECONDS;
import static java.util.concurrent.TimeUnit.NANOSECONDS;
import static org.openjdk.jmh.annotations.Mode.AverageTime;
import static org.openjdk.jmh.annotations.Scope.Benchmark;
@State(Benchmark)
@OutputTimeUnit(NANOSECONDS)
@Warmup(iterations = 5, time = 1000, timeUnit = MILLISECONDS)
@Measurement(iterations = 5, time = 1000, timeUnit = MILLISECONDS)
@BenchmarkMode(AverageTime)
@Fork(value = 1)
public class Bench {
    private static final int number = Integer.MAX_VALUE;
    @Benchmark
    public int for1() {
        final int limit = (int) Math.sqrt(number);
        int c = 0;
        for (int i = 3; i < limit; i += 2)
            c++;
        return c;
    }
    @Benchmark
    public int for2() {
        int c = 0;
        for (int i = 3; i < (int) Math.sqrt(number); i += 2)
            c++;
        return c;
    }
    public static void main(String[] args) throws Exception {
        new Runner(new OptionsBuilder()
                .include(Bench.class.getName())
                .build()
        ).run();
    }
}

Ergebnis bei mir:

Benchmark   Mode  Cnt    Score   Error  Units
Bench.for1  avgt    5  451,841 ± 4,520  ns/op
Bench.for2  avgt    5  225,654 ± 2,393  ns/op

Also: Die for-Schleife, bei der der Math.sqrt() Aufruf in der Condition direkt steht, ist sogar schneller.

Warum das c++ und return c? -> Die JVM optimiert hier sehr schnell deine gesamte Schleife einfach weg, weil sie nichts tut, also kein Wert von ihr abhängt. Dies sorgt dafür, dass das nicht passiert.

Aber ja... am Ende des Tages spielt das alles keine Rolle, wenn der Code sowieso nur einmal ausgeführt wird und die ganzen Optimierungen der JVM gar nicht erst zum Tragen kommen.

 

[mihe7]

aufgrund der diversen Compilerstages, die für unterschiedlich häufige Ausführungen des Codes herangezogen werden.

Mal nebenbei: wieso kennst Du die ganzen Details der JVM?!? Ziehst Du Dir vor dem Schlafengehen noch ein wenig JVM-Quellcode rein, oder woher kommt das? Das ist ja nicht normal.

 

[httpdigest]

Also, was Tiered Compilation ist, sollte man bei der JVM schon wissen. Also zumindest, dass es das gibt und dass es den Interpreter, den C1 (client-compiler) und den C2 (server-compiler) gibt und, dass diese herangezogen werden, je häufiger Code ausgeführt wird. Das ist eigentlich Allgemeinwissen, was Java bzw. die JVM bzw. HotSpot angeht
Irgendwann bin ich einfach auf Aleksey Shipilevs (einer der OpenJDK Committer) Seite gestossen: https://shipilev.net/

 

[kneitzel]

Danke für die Hinweise.

Das meine Tests nur grobe Werte ergeben würden, war mir klar. Daher ja eben auch die Veränderung der Reihenfolge zur groben Verifizierung von Ergebnissen. Das mit dem Framework muss ich mir mal ansehen, aber in der Regel mache ich solche Tests nicht, daher hatte ich das in der Vergangenheit eher ignoriert.

Der Hinweis bezüglich der leeren Schleife ist aber natürlich richtig und sehr wichtig. Das hat den gezeigten Test natürlich komplett verfälscht. Ich habe bei mir das mit dem Hochzählen der Variable mit eingebaut und das Ergebnis dann auch noch ausgegeben -> Und jetzt habe ich auch auf meinem System vergleichbare Ausgaben. Damit kann man relativ sicher sagen, dass diese Optimierung durchgeführt wurde / wird bei AdoptOpenJDK 16 und auch bei der GraalVM.

Beim Native-Image war der Test nicht wirklich aussagefähig. Das wäre ggf. nur mit dem Framework sinnvoll möglich. Da scheint es massive Startup-Belastungen zu geben, die den ersten anlaufenden Test dann verzögert. (Daher ja auch immer der Check mit unterschiedlicher Reihenfolge)

 

[mihe7]

Irgendwann bin ich einfach auf Aleksey Shipilevs (einer der OpenJDK Committer) Seite gestossen: https://shipilev.net/

Aha! Doch Bettlektüre. Dir ist aber schon klar, dass da vieles Russisch und nicht Bytecode ist?

LOL: Do It Yourself (OpenJDK) Garbage Collector (Because why not.)

Aber: russisch, black magic, (thread)ripper, anatomy, inside out, bleeding (edge) -- wer diese Seite besucht, steht automatisch unter Beobachtung.

 

[Neumi5694]

Ohne parallalele Abarbeitung kann sich bei den Tests auch auf bisher gefundene Primzahlen beschränken.

    public static ArrayList<Integer> getAllPrimesOptimized(int upperLimit) {
        upperLimit = Math.max(0, upperLimit);
        ArrayList<Integer> primes = new ArrayList<>(106000000);
        //2 ist hardcodiert drin, da bin ich faul.
        if (upperLimit >= 2) {
            primes.add(2);
        } else {
            return primes;
        }
        if (Integer.MAX_VALUE - upperLimit > 2) {
            //kein Überlauf, normale Schleife
            for (int i = 3; i <= upperLimit; i += 2) {
                if (isOddNumberPrime(i, primes)) {
                    primes.add(i);
                }
            }
        } else {
            //nutzt den Überlauf bei Integer.MAX_INTEGER als Abbruchbedingung
            for (int i = 3; i > 0; i += 2) {
                if (isOddNumberPrime(i, primes)) {
                    primes.add(i);
                }
            }
        }
        return primes;
    }

    /**
     * Bestimmt, ob eine ungerade Zahl eine Primzahl ist. Funktioniert nicht für gerade Zahlen, nur für die interne
     * Verwendung gedacht.
     *
     * @param oddNumber Der übergebene Wert MUSS underade sein, sonst geht's in die Hose
     */
    private static boolean isOddNumberPrime(int oddNumber, ArrayList<Integer> knownprimes) {
        double sq = Math.sqrt(oddNumber);
        for (int d : knownprimes.subList(1, knownprimes.size())) { //2 wird übersprungen
            if (d > sq) {
                return true;
            } else if (oddNumber % d == 0) {
                return false;
            }
        }
        return true;
    }

Dies geht freilich nur, wenn man ohne parallele Threads arbeitet. Dann aber spart man sich dadurch sehr viel Zeit.


Wer mathematisch mehr auf dem Kasten hat, kann sich mit der Probedivision auseinanderssetzen.
Schon vor 150 Jahren konnte MAX_INTEGER durch nur 372 Divisionen als Primzahl bestätigt werden.

 

[mihe7]

Da kann man noch mehr machen, wenn man will. Das JDK verwendet in BigInteger#isProbablePrime z. B. https://en.wikipedia.org/wiki/Miller–Rabin_primality_test und https://en.wikipedia.org/wiki/Lucas–Lehmer_primality_test (letzteren Test für Zahlen mit einer Länge ab 100 Bits).

 

[Barista]

Hat jemand eine Idee, woher man garantiert korrekte Primzahlen als Erfolgskriterium in einem Unit-Test bekommt?

Unter anderem auch richtig viele Primzahlen, wenn man Algorithmen an der Grenze des Arbeitsspeichers testen will.

 

[Neumi5694]

Hat jemand eine Idee, woher man garantiert korrekte Primzahlen als Erfolgskriterium in einem Unit-Test bekommt?

Unter anderem auch richtig viele Primzahlen, wenn man Algorithmen an der Grenze des Arbeitsspeichers testen will.

Wenn du sie im oder für den Unit-Test berechnen willst, dann ist die oben genannte Methode (Dividieren bis zur Wurzel aus der Zahl) bereits garantiert korrekt.
Mit der daraus erzeugten Liste kannst du optimierte Verfahren testen.

 

[LimDul]

Google
z.B. https://www.wiwald.com/ds/eine-million-primzahlen/id/ww-primes

 

[Barista]

Google
z.B. https://www.wiwald.com/ds/eine-million-primzahlen/id/ww-primes

Habe ich runtergeladen.

CSV-Format, Headerzeile ja, Trennzeichen Semikolon.

Hier der Code zum Einlesen der Primzahlen (Eclipse-Projekt, die Datei befindet sich im Ordner data):

[CODE lang="java" title="PrimesFromCsvFileIterator"]package ???;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.NoSuchElementException;

public class PrimesFromCsvFileIterator
{
static final File eclipseProjectDir = new File( System.getProperty( "user.dir" ) );

private final BufferedReader reader;

private int index;

private int prime;

private boolean hasNext;

/**
* Constructor.
*
* @throws FileNotFoundException
*/
public PrimesFromCsvFileIterator()
throws IOException
{
final File dataDir = new File( eclipseProjectDir , "data" );

final File primesCsvFile = new File( dataDir , "ww-primes.csv" );

reader = new BufferedReader( new FileReader( primesCsvFile ) );

// skip header line
reader.readLine();

this.hasNext = true;

this.hasNext = next();

final Thread closeReaderShutdownHook =
new Thread()
{

@Override
public void run()
{
try
{
PrimesFromCsvFileIterator.this.reader.close();
}
catch ( IOException e )
{
throw new RuntimeException( e );
}
}
};

Runtime.getRuntime().addShutdownHook( closeReaderShutdownHook );
}

public boolean hasNext()
{
return this.hasNext;
}

/**
* Skip to next prime.
*
* @return has next
* @throws IOException
*/
public boolean next()
throws IOException
{
if ( ! hasNext )
{
throw new IllegalStateException();
}

final String line = reader.readLine();

if ( line == null )
{
this.hasNext = false;
return false;
}

final String indexStr =
line.substring(
//beginIndex
0 ,
//endIndex
line.indexOf( ';' ) );

this.index = Integer.parseInt( indexStr );

final String primeStr =
line.substring(
//beginIndex
line.indexOf( ';' ) + 1 ,
//endIndex
line.length() );

this.prime = Integer.parseInt( primeStr );

return true;
}

/**
* @return the index
*/
public int getIndex()
{
if ( ! hasNext )
{
throw new NoSuchElementException();
}

return index;
}

/**
* @return the prime
*/
public int getPrime()
{
if ( ! hasNext )
{
throw new NoSuchElementException();
}

return prime;
}

}
[/CODE]

 

[Barista]

Habe ich runtergeladen.

Hier mein Sieb des Eratosthenes:

[CODE lang="java" title="SieveOfEratosthenes"]package ???;

import java.io.IOException;
import java.util.Arrays;

public class SieveOfEratosthenes
{

public static void main(String[] args)
throws IOException
{
final int upperLimit = 15485863;

System.out.println( "upper limit: " + upperLimit );

final int[] primes =
getPrimes(
upperLimit );

System.out.println( "prime count: " + primes.length );

//System.out.println( Arrays.toString( primes ) );

final PrimesFromCsvFileIterator primesFromCsvFileIterator = new PrimesFromCsvFileIterator();

for ( int i = 0; i < primes.length; i++ )
{
final int prime = primes[ i ];

if ( prime != primesFromCsvFileIterator.getPrime() )
{
throw new RuntimeException( "wrong prime: " + prime + " at index: " + i );
}

primesFromCsvFileIterator.next();
}

System.out.println( "ok" );
}

public static int[] getPrimes(
final int upperLimit )
{
// in Java wird für jedes boolean 8 bit im Speicher benutzt, schade, aber zur Vereinfachung erst mal nicht-optimiert verwendet
final boolean[] isPrimeArray = new boolean[ upperLimit + 1 ];

Arrays.fill( isPrimeArray , true );

// die beiden Speicherstellen am Index 0 und 1 werden nicht verwendet, könnten eingespart werden, hier erst mal ignoriert
isPrimeArray[ 0 ] = false;
isPrimeArray[ 1 ] = false;

final int flooredSqrtOfUpperLimit =
(int) Math.floor(
Math.sqrt(
upperLimit ) );
// Primzahl 2
for ( int i = 4 ; i < isPrimeArray.length ; i += 2 )
{
isPrimeArray[ i ] = false;
}

// Primzahl 3
for ( int i = 9 ; i < isPrimeArray.length ; i += ( 2 * 3 ) )
{
isPrimeArray[ i ] = false;
}

// https://de.wikipedia.org/wiki/Sieb_des_Eratosthenes#Implementierung
for ( int i = 5 ; i <= flooredSqrtOfUpperLimit ; ++i )
{
if ( isPrimeArray[ (int) i ] )
{
// ...und streiche seine Vielfachen, beginnend mit i*i (denn k*i mit k<i wurde schon als Vielfaches von k gestrichen)
final int noPrimeStart = i * i;

// noPrimeStart ist immer ungerade, ungerade + ungerade gibt eine gerade zahl, aber diese sind bereits alle gestrichen (no prime).
// Deshalb Erhoehung um 2 * prime (ungerade + gerade ergibt ungerade)
final int noPrimeStep = 2 * i;
for ( long j = noPrimeStart ; j <= upperLimit ; j += noPrimeStep )
{
isPrimeArray[ (int) j ] = false;
}
}
}

int primeCount =
trueCount(
isPrimeArray );

// TODO eventuell Iterieren um den Speicherbedarf fuer alle gefundenen Primzahlen zu vermeiden
final int[] primes = new int[ primeCount ];

int primesIndex = 0;
for ( int i = 0 ; i < isPrimeArray.length ; i++ )
{
if ( isPrimeArray[ i ] )
{
primes[ primesIndex++ ] = i;
}
}

return primes;
}

static int trueCount(
final boolean[] boolArray )
{
int trueCount = 0;

for (int i = 0; i < boolArray.length; i++)
{
if ( boolArray[ i ] )
{
trueCount++;
}
}

return trueCount;
}

}
[/CODE]

 

[Barista]

Hier mein Sieb des Eratosthenes:

Noch ein bisschen optimiert:
[CODE lang="java" title="SieveOfEratosthenes"]package ???;

import java.io.IOException;

public class SieveOfEratosthenes
{

public static void main(String[] args)
throws IOException
{
final int upperLimit = 15485863;

System.out.println( "upper limit: " + upperLimit );

final int[] primes =
getPrimes(
upperLimit );

System.out.println( "prime count: " + primes.length );

//System.out.println( Arrays.toString( primes ) );

final PrimesFromCsvFileIterator primesFromCsvFileIterator = new PrimesFromCsvFileIterator();

for ( int i = 0; i < primes.length; i++ )
{
final int prime = primes[ i ];

if ( prime != primesFromCsvFileIterator.getPrime() )
{
throw new RuntimeException( "wrong prime: " + prime + " at index: " + i );
}

primesFromCsvFileIterator.next();
}

System.out.println( "ok" );
}

public static int[] getPrimes(
final int upperLimit )
{
final int oddUpperLimit;
if ( upperLimit > 2 &&
upperLimit % 2 == 0 )
{
// eine gerade Zahl groesser 2 kann keine Primzahl sein
oddUpperLimit = upperLimit - 1;
}
else
{
oddUpperLimit = upperLimit;
}

// in Java wird fuer jedes boolean 8 bit im Speicher benutzt, schade, aber zur Vereinfachung erst mal nicht-optimiert verwendet
// Die Speicherstellen an den Array-Index 0 und 1 werden nicht verwendet, aber zur Vereinfachung des Codes mit reserviert
final boolean[] isPrimeArray = new boolean[ oddUpperLimit + 1 ];

isPrimeArray[ 2 ] = true;

for ( int n = 3 ; n < isPrimeArray.length ; n += 2 )
{
isPrimeArray[ n ] = true;
}


final int flooredSqrtOfUpperLimit =
(int) Math.floor(
Math.sqrt(
oddUpperLimit ) );

// https://de.wikipedia.org/wiki/Sieb_des_Eratosthenes#Implementierung
for ( int n = 3 ; n <= flooredSqrtOfUpperLimit ; ++n )
{
if ( isPrimeArray[ (int) n ] )
{
// ...und streiche seine Vielfachen, beginnend mit i*i (denn k*i mit k<i wurde schon als Vielfaches von k gestrichen)
final int noPrimeStart = n * n;

// noPrimeStart ist immer ungerade, ungerade + ungerade gibt eine gerade zahl, aber diese sind bereits alle gestrichen (no prime).
// Deshalb Erhoehung um 2 * prime (ungerade + gerade ergibt ungerade)
final int noPrimeStep = 2 * n;
for ( long noPrime = noPrimeStart ; noPrime <= oddUpperLimit ; noPrime += noPrimeStep )
{
isPrimeArray[ (int) noPrime ] = false;
}
}
}

int primeCount =
trueCount(
isPrimeArray );

// TODO eventuell Iterieren um den Speicherbedarf fuer alle gefundenen Primzahlen zu vermeiden
final int[] primes = new int[ primeCount ];

int primesIndex = 0;
for ( int i = 0 ; i < isPrimeArray.length ; i++ )
{
if ( isPrimeArray[ i ] )
{
primes[ primesIndex++ ] = i;
}
}

return primes;
}

static int trueCount(
final boolean[] boolArray )
{
int trueCount = 0;

for (int i = 0; i < boolArray.length; i++)
{
if ( boolArray[ i ] )
{
trueCount++;
}
}

return trueCount;
}

}
[/CODE]

 

[Barista]

Die nächste Idee ist, nur ungerade Zahlen im Array zu vermerken, denn ausser der 2 sind alle Primzahlen ungerade.

Dadurch halbiert sich der Speicherbedarf und hoffentlich auch die Laufzeit.

[CODE lang="java" title="SieveOfEratosthenesWithSkippingNumbersMultipleOf2"]package ???;

import java.io.IOException;
import java.util.Arrays;

// Sieb des Eratosthenes mit Überspringen aller geraden Zahlen
// Dadurch wird nur die halbe Speichermenge benoetigt
public class SieveOfEratosthenesWithSkippingNumbersMultipleOf2
{

public static void main(String[] args)
throws IOException
{
final int upperLimit = 15485863;

System.out.println( "upper limit: " + upperLimit );

final int[] primes =
getPrimes(
upperLimit );

System.out.println( "prime count: " + primes.length );

//System.out.println( Arrays.toString( primes ) );

final PrimesFromCsvFileIterator primesFromCsvFileIterator = new PrimesFromCsvFileIterator();

for ( int i = 0; i < primes.length; i++ )
{
final int prime = primes[ i ];

if ( prime != primesFromCsvFileIterator.getPrime() )
{
throw new RuntimeException( "wrong prime: " + prime + " at index: " + i );
}

primesFromCsvFileIterator.next();
}

System.out.println( "ok" );
}

public static int[] getPrimes(
final int upperLimit )
{
final int oddUpperLimit;
if ( upperLimit > 2 &&
upperLimit % 2 == 0 )
{
// eine gerade Zahl groesser 2 kann keine Primzahl sein
oddUpperLimit = upperLimit - 1;
}
else
{
oddUpperLimit = upperLimit;
}

// in Java wird fuer jedes boolean 8 bit im Speicher benutzt, schade, aber zur Vereinfachung erst mal nicht-optimiert verwendet
// Die Speicherstellen an den Array-Index 0 und 1 werden nicht verwendet, aber zur Vereinfachung des Codes mit reserviert
final boolean[] isPrimeArray = new boolean[ ( oddUpperLimit + 1 ) / 2 ];

Arrays.fill( isPrimeArray , true );

// die 1 ist keine Primzahl
isPrimeArray[ 0 ] = false;

final int flooredSqrtOfUpperLimit =
(int) Math.floor(
Math.sqrt(
oddUpperLimit ) );

// https://de.wikipedia.org/wiki/Sieb_des_Eratosthenes#Implementierung
for ( int n = 3 ; n <= flooredSqrtOfUpperLimit ; n += 2 )
{
final int nIndex = ( (int) n ) / 2;
if ( isPrimeArray[ nIndex ] )
{
// ...und streiche seine Vielfachen, beginnend mit i*i (denn k*i mit k<i wurde schon als Vielfaches von k gestrichen)
final int noPrimeStart = n * n;

// noPrimeStart ist immer ungerade, ungerade + ungerade gibt eine gerade zahl, aber diese sind bereits alle gestrichen (no prime).
// Deshalb Erhoehung um 2 * prime (ungerade + gerade ergibt ungerade)
final int noPrimeStep = 2 * n;
for ( long noPrime = noPrimeStart ; noPrime <= oddUpperLimit ; noPrime += noPrimeStep )
{
final int noPrimeIndex = ( (int) noPrime ) / 2;
isPrimeArray[ noPrimeIndex ] = false;
}
}
}

// TODO eventuell Iterieren um den Speicherbedarf fuer alle gefundenen Primzahlen zu vermeiden
int primeCount =
SieveOfEratosthenes.trueCount(
isPrimeArray );

final int[] primes =
new int[
primeCount +
// Platz fuer die Primzahl 2
1 ];

primes[ 0 ] = 2;

int primesIndex = 1;

for ( int i = 1 ; i < isPrimeArray.length ; i++ )
{
if ( isPrimeArray[ i ] )
{
primes[ primesIndex++ ] = ( i * 2 ) + 1;
}
}

return primes;
}

/*
static int[] getPrimes(
final int upperLimit )
{
// in Java wird für jedes boolean 8 bit im Speicher benutzt, schade, aber zur Vereinfachung erst mal nicht-optimiert verwendet
final boolean[] isPrimeArray = new boolean[ (int) Math.ceil( ( ( upperLimit / ARRAY_SIZE_DIVISOR ) - 1 ) ) ];

Arrays.fill( isPrimeArray , true );

//int currentNumber = START_NUMBER - 1;
int currentNumber = 2;
int count2 = 2;

//for ( int isPrimeArrayIndex = 0 ; isPrimeArrayIndex < isPrimeArray.length ; )
for ( int isPrimeArrayIndex = 0 ; currentNumber < upperLimit ; )
{
currentNumber++;

if ( ( --count2 ) == 0 )
{
count2 = 2;
continue;
}

if ( isPrimeArray[ isPrimeArrayIndex ] )
{
setNoPrimes(
isPrimeArray ,
//primeNumber
currentNumber ,
upperLimit );

}

isPrimeArrayIndex++;
}


int primeCount =
SieveOfEratosthenes.trueCount(
isPrimeArray );

final int[] primes =
new int[
primeCount +
// Platz fuer die Primzahl 2
1 ];

primes[ 0 ] = 2;

int primesIndex = 1;

currentNumber = 2;
count2 = 2;

//for ( int isPrimeArrayIndex = 0 ; isPrimeArrayIndex < isPrimeArray.length ; )
for ( int isPrimeArrayIndex = 0 ; currentNumber < upperLimit ; )
{
currentNumber++;

if ( ( --count2 ) == 0 )
{
count2 = 2;
continue;
}

if ( isPrimeArray[ isPrimeArrayIndex ] )
{
primes[ primesIndex++ ] = currentNumber;

}

isPrimeArrayIndex++;
}

return primes;
}

private static void setNoPrimes(
final boolean[] isPrimeArray ,
final int primeNumber ,
final int upperLimit )
{
//System.out.println( "setNoPrimes: " + primeNumber );

long numberToSetNoPrime = primeNumber * primeNumber;

int currentNumber = 2;
int count2 = 2;

//for ( int isPrimeArrayIndex = 0 ; isPrimeArrayIndex < isPrimeArray.length ; )
for ( int isPrimeArrayIndex = 0 ; currentNumber < upperLimit ; )
{
currentNumber++;

if ( ( --count2 ) == 0 )
{
if ( currentNumber == numberToSetNoPrime )
{
//System.out.println( "setNoPrimes, currentNumber skip: " + currentNumber );
numberToSetNoPrime += 2 * primeNumber;
}

count2 = 2;
continue;
}

if ( currentNumber == numberToSetNoPrime )
{
//System.out.println( "setNoPrimes, currentNumber: " + currentNumber );
isPrimeArray[ isPrimeArrayIndex ] = false;
numberToSetNoPrime += primeNumber;
}

isPrimeArrayIndex++;
}
}
*/
}
[/CODE]

 

[Barista]

Ich hatte noch ein bisschen überlegt, habe aber keine Lust meine Ideen auszuimplementieren.

Prinzipiell gehe ich davon aus, dass das forward-domain-restriction-Prinzip des Sieb des Erastosthenes (hoffentlich richtig geschrieben) schneller als das Prüfen anhand bereits berechneter Primzahlen ist.

Dafür benötigt das Sieb des Erastosthenes mehr Speicher (nicht getestet).

Für die Annahme, dass das Sieb des Erastosthenes mehr Speicher mehr Speicher als die Primzahlenliste benötigt spricht folgendes Programm:

[CODE lang="java" title="MaxPrimeGapFromFile"]package ???;

import java.io.IOException;

public class MaxPrimeGapFromFile
{

public static void main(final String[] args)
throws IOException
{
final PrimesFromCsvFileIterator primesFromCsvFileIterator = new PrimesFromCsvFileIterator();

int lastPrime = primesFromCsvFileIterator.getPrime();

int maxPrimeGap = 0;

final IntTreeBag histogramm = new IntTreeBag();

while ( primesFromCsvFileIterator.next() )
{
final int prime = primesFromCsvFileIterator.getPrime();

final int primeGap = prime - lastPrime;

if ( primeGap > maxPrimeGap)
{
System.out.println( primeGap + " " + prime );
}

histogramm.increment( primeGap );

maxPrimeGap =
Math.max(
maxPrimeGap ,
primeGap );

lastPrime = prime;
}

System.out.println( "max prime gap: " + maxPrimeGap );

System.out.println( "histogramm size: " + histogramm.size() );
System.out.println( histogramm );
}

}
[/CODE]

[CODE lang="java" title="IntTreeBag"]package ???;

import java.util.TreeMap;

@SuppressWarnings("serial")
public class IntTreeBag
extends TreeMap<Integer, Integer>
{
public void increment(
final int key )
{
final int oldValue;
final Integer oldValueObj = get( key );

if ( oldValueObj == null )
{
oldValue = 0;
}
else
{
oldValue = oldValueObj;
}

this.put( key , oldValue + 1 );
}

}
[/CODE]

[CODE title="MaxPrimeGapFromFile Konsolen-Ausgabe"]1 3
2 5
4 11
6 29
8 97
14 127
18 541
20 907
22 1151
34 1361
36 9587
44 15727
52 19661
72 31469
86 156007
96 360749
112 370373
114 492227
118 1349651
132 1357333
148 2010881
154 4652507
max prime gap: 154
histogramm size: 78
{1=1, 2=86027, 4=85832, 6=146518, 8=62750, 10=80399, 12=97826, 14=52826, 16=37688, 18=66465, 20=33777, 22=29583, 24=41731, 26=18928, 28=20591, 30=33960, 32=10100, 34=10536, 36=16301, 38=7196, 40=8600, 42=11657, 44=4492, 46=3822, 48=6305, 50=3449, 52=2412, 54=4054, 56=1862, 58=1753, 60=3194, 62=910, 64=980, 66=1664, 68=625, 70=906, 72=771, 74=392, 76=319, 78=612, 80=279, 82=197, 84=429, 86=122, 88=118, 90=276, 92=76, 94=73, 96=119, 98=52, 100=73, 102=63, 104=35, 106=27, 108=51, 110=26, 112=18, 114=34, 116=14, 118=8, 120=21, 122=6, 124=7, 126=17, 128=4, 130=2, 132=10, 134=3, 136=4, 138=6, 140=4, 142=2, 144=1, 146=1, 148=2, 150=1, 152=1, 154=3}
[/CODE]

Am Ende ist die Lücke 154 Bit gross, es würde aber ein 32-Bit-Integer zum Vermerken der Primzahl ausreichen.

Bei höheren Primzahlen werden sicher auch die Lücken grösser.

Nun hatte ich folgende Idee:

Um mehr Speicher zu haben (mehr Primzahlen berechnen zu können) könnte man den forward-Speicher als Sparse-Array aufbauen.

Wenn das Sparse-Array Ranges speichert, fallen irgendwann die Lücken zu einem Range zusammen, während einzelne im hohen Bereich liegende Streichungen als Werte gespeichert werden.

Das Sparse-Array könnte auch Bereiche negiert speichern, wenn dies Speicher spart.


Weitere Variante: Daten auf Disk auslagern.

Weitere Variante: Wenn man die vorherigen Primzahlen nicht vermerkt, benötigt man noch weniger Speicher, aber sicher mehr Zeit.

Es gibt noch das Sieb von Atkin, ist mir aber zu hoch, verstehe ich nicht:

Sieb von Atkin – Wikipedia

de.wikipedia.org

Ist alles keine Frage und auch keine Aufforderung zur Diskussion, nur meine Gedanken, eventuell zum Wiederfinden durch mich selbst.