Du bist zu ungeduldig, nach einer Weile spuckt dein Beispiel als erste Zahl 9223372036854775837 aus.Dein Check ist natürlich ziemlich langsam, und für das eingebaute isProbablePrime ist es extrem unwahrscheinlich, falsch zu liegen, also sollte für praktische Belange sowas ausreichen:
private boolean isPri(BigInteger b) {
return b.isProbablePrime(5);
}
Wenn du es wirklich absolut sicher haben willst, müsstest du dir andere Tests anschauen, Probedivisionen werden sehr schnell viel zu langsam.
Es wird sich übrigens schon für größere longs lohnen, das isProbablePrime auszuführen, um Nicht-Primzahlen schnell auszuschließen, selbst wenn du danach für die verbliebenen Kandidaten noch die Probedivisionen machst.
hab ich mir durchgelesen, vor allem interessant ist:
Otherwise a is called a strong liar, and n is a strong probable prime to base a. The term „strong liar“ refers to the case where n is composite but nevertheless the equations hold as they would for a prime.
Arnault [5] gave a 397-digit composite number for which all bases a less than 307 are strong liars.
The more bases a are tried, the better the accuracy of the test. It can be shown that if n is composite, then at most 1⁄4 of the bases a are strong liars for n.[2][6] As a consequence, if n is composite then running k iterations of the Miller–Rabin test will declare n probably prime with a probability at most 4−k.
Aber die Laufzeit, soft-O(k log^2 n) ist schon mal sehr gut.
Nun ich möchte tatsächlich starke Lügner ausschließen. Aber wahrscheinlich gibt es bessere und genaue Tests als den, den ich jetzt mal nebenläufig gemacht hab, um etwas schneller Ergebnisse zu erhalten:
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.Callable;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.FutureTask;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.TimeoutException;
public class PrimeIterator {
private boolean long_based = true;
private long start_long;
private BigInteger start_bi;
public PrimeIterator(BigInteger start) {
if (start.compareTo(BigInteger.valueOf(Long.MAX_VALUE)) > 0) {
long_based = false;
}
if (long_based) {
start_long = start.longValue();
} else {
start_bi = start;
}
}
public BigInteger nextPrime() {
BigInteger b;
while (true) {
if (long_based) {
if (isPri(start_long)) {
b = BigInteger.valueOf(start_long);
inc();
return b;
} else {
inc();
}
} else {
if (isPri(start_bi)) {
b = start_bi;
inc();
return b;
} else {
inc();
}
}
}
}
private boolean isPri(long l) {
if (l % 2 == 0) {
return false;
}
long s = (long) Math.sqrt(start_long);
for (long i = 3; i <= s; i += 2) {
if (l % i == 0) {
return false;
}
}
return true;
}
private boolean isPri(BigInteger b) {
if (b.isProbablePrime(5)) {
if (b.mod(BigInteger.TWO).compareTo(BigInteger.ZERO) == 0) {
return false;
}
BigInteger s = b.sqrt();
BigInteger part = s.divide(BigInteger.valueOf(8));
List<FutureTask<Boolean>> taskList = new ArrayList<FutureTask<Boolean>>();
for (int i = 0; i < 8; i++) {
final int multiplier = i;
taskList.add(new FutureTask<>(new Callable<Boolean>() {
@Override
public Boolean call() throws Exception {
BigInteger from = part.multiply(BigInteger.valueOf(multiplier)).add(BigInteger.valueOf(3));
BigInteger to = part.multiply(BigInteger.valueOf(multiplier + 1)).add(BigInteger.valueOf(3));
System.out.println("starting: " + b + " " + from + " " + to);
return isPri(b, from, to);
}
}));
}
ExecutorService executor = Executors.newFixedThreadPool(4);
for (FutureTask<Boolean> futureTask : taskList) {
executor.execute(futureTask);
}
for (int i = 0; i < 2; i++) {
for (FutureTask<Boolean> futureTask : taskList) {
try {
if (!futureTask.get(1, TimeUnit.SECONDS)) {
executor.shutdownNow();
return false;
}
} catch (InterruptedException | ExecutionException | TimeoutException e) {
}
}
}
System.out.println("10 seconds no results...");
for (FutureTask<Boolean> futureTask : taskList) {
try {
if (!futureTask.get()) {
executor.shutdownNow();
return false;
}
} catch (InterruptedException | ExecutionException e) {
e.printStackTrace();
}
}
executor.shutdownNow();
return true;
}
return false;
}
private boolean isPri(BigInteger b, BigInteger from, BigInteger to) {
for (BigInteger i = from; to.compareTo(i) > 0; i = i.add(BigInteger.TWO)) {
if (Thread.interrupted()) {
return false;
}
if (b.mod(i).compareTo(BigInteger.ZERO) == 0) {
return false;
}
}
return true;
}
private void inc() {
if (long_based) {
if (start_long == Long.MAX_VALUE) {
long_based = false;
start_bi = BigInteger.valueOf(Long.MAX_VALUE).add(BigInteger.ONE);
} else {
start_long++;
}
} else {
start_bi = start_bi.add(BigInteger.ONE);
}
}
public static void main(String[] args) {
PrimeIterator pi = new PrimeIterator(BigInteger.valueOf(1));
for (int i = 0; i < 20; i++) {
System.out.println(pi.nextPrime());
}
pi = new PrimeIterator(BigInteger.valueOf(Long.MAX_VALUE - 15));
for (int i = 0; i < 3; i++) {
System.out.println(pi.nextPrime());
}
}
}
Die Bounds stimmen noch nicht ganz. 15/8 wäre 1, 1*8+3 wäre 11, also 4 weniger als 15.
Eigentlich würde ich mit Dingen, die ich dazu sage, gerne „weiter oben“ ansetzen. Aber fangen wir mal unten an:
Hundert Millionen mal haben die schon hundert Millionen Leute gesagt: Verwende vernünftige Variablen- und Methodennamen, und befolge die naming conventions. Mal im Ernst: Welche Rechtfertigung gibt es (dann noch) dafür, das nicht zu tun? Mir würde keine einfallen, bei der du, wenn ich sie äußern würde, nicht anfangen würdest rumzuflennen: „Näh-näh, der hat mich ‚dumm‘ genannt, warum darf der das, aber wenn ich es mache, werden meine Beiträge gelöscht“
Wenn man das Ding „PrimeIterator“ nennt, sollte es auch ein Iterator<BigInteger> sein.
Bei dem, was du da jetzt „„nebenläufig gemacht““ hast, läuft’s mir kalt den Rücken runter.
Wenn man eine Klasse hat, bei der (praktisch) jede Methode ein if (foo) doFoo(); else doBar() ist, dann ist das ein deutliches Zeichen dafür, dass das zwei Klassen sein sollten (aber da müßte man über die sinnvollste Struktur noch etwas nachdenken)
Hab ich doch. Du müsstest dich nur mal dazu herablassen, diese auch mal zu lesen.
Ansonsten habe ich das mit den richtigen Bounds jetzt auch gelöst (indem immer +1 gerechnet wird), die Nebenläufigkeit gefällt mir aber noch nicht so…
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.Callable;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.FutureTask;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.TimeoutException;
public class PrimeIterator {
private boolean long_based = true;
private long start_long;
private BigInteger start_bi;
public PrimeIterator(BigInteger start) {
if (start.compareTo(BigInteger.valueOf(Long.MAX_VALUE)) > 0) {
long_based = false;
}
if (long_based) {
start_long = start.longValue();
} else {
start_bi = start;
}
}
public BigInteger nextPrime() {
BigInteger b;
while (true) {
if (long_based) {
if (isPri(start_long)) {
b = BigInteger.valueOf(start_long);
inc();
return b;
} else {
inc();
}
} else {
if (isPri(start_bi)) {
b = start_bi;
inc();
return b;
} else {
inc();
}
}
}
}
private boolean isPri(long l) {
if (l % 2 == 0) {
return false;
}
long s = (long) Math.sqrt(start_long);
for (long i = 3; i <= s; i += 2) {
if (l % i == 0) {
return false;
}
}
return true;
}
private boolean isPri(BigInteger b) {
if (b.isProbablePrime(5)) {
if (b.mod(BigInteger.TWO).compareTo(BigInteger.ZERO) == 0) {
return false;
}
BigInteger s = b.sqrt();
BigInteger part = s.divide(BigInteger.valueOf(10)).add(BigInteger.ONE);
List<FutureTask<Boolean>> taskList = new ArrayList<FutureTask<Boolean>>();
for (int i = 0; i < 10; i++) {
final int multiplier = i;
taskList.add(new FutureTask<>(new Callable<Boolean>() {
@Override
public Boolean call() throws Exception {
BigInteger from = part.multiply(BigInteger.valueOf(multiplier)).add(BigInteger.valueOf(3));
BigInteger to = part.multiply(BigInteger.valueOf(multiplier + 1)).add(BigInteger.valueOf(3));
System.out.println("starting: " + b + " " + from + " " + to + " " + s);
return isPri(b, from, to);
}
}));
}
ExecutorService executor = Executors.newFixedThreadPool(3);
for (FutureTask<Boolean> futureTask : taskList) {
executor.execute(futureTask);
}
for (int i = 1; i <= 3; i++) {
for (FutureTask<Boolean> futureTask : taskList) {
try {
if (!futureTask.get(1, TimeUnit.SECONDS)) {
executor.shutdownNow();
return false;
}
} catch (InterruptedException | ExecutionException | TimeoutException e) {
}
}
}
System.out.println("30 seconds no results...");
for (FutureTask<Boolean> futureTask : taskList) {
try {
if (!futureTask.get()) {
executor.shutdownNow();
return false;
}
} catch (InterruptedException | ExecutionException e) {
e.printStackTrace();
}
}
executor.shutdownNow();
return true;
}
return false;
}
private boolean isPri(BigInteger b, BigInteger from, BigInteger to) {
for (BigInteger i = from; to.compareTo(i) > 0; i = i.add(BigInteger.TWO)) {
if (Thread.interrupted()) {
return false;
}
if (b.mod(i).compareTo(BigInteger.ZERO) == 0) {
return false;
}
}
return true;
}
private void inc() {
if (long_based) {
if (start_long == Long.MAX_VALUE) {
long_based = false;
start_bi = BigInteger.valueOf(Long.MAX_VALUE).add(BigInteger.ONE);
} else {
start_long++;
}
} else {
start_bi = start_bi.add(BigInteger.ONE);
}
}
public static void main(String[] args) {
PrimeIterator pi = new PrimeIterator(BigInteger.valueOf(1));
for (int i = 0; i < 20; i++) {
System.out.println(pi.nextPrime());
}
pi = new PrimeIterator(new BigInteger("999999999999999999999"));
for (int i = 0; i < 3; i++) {
System.out.println(pi.nextPrime());
}
}
}
Nö, einen vollständigen Iterator bedarf es nicht, da es immer eine nächste Primzahl gibt (Satz von Euklid). Deswegen wäre es auch nicht sinnvoll, solch einen Iterator zum Beispiel mit einer for-each zu verwenden.
Warum ich mich jetzt dazu herablasse, nochmal https://www.oracle.com/java/technologies/javase/codeconventions-namingconventions.html zu posten, weiß ich nicht genau. Der Einwand, der darauf rausläuft, dass hasNext immer true zurückgeben könnte/müßte, könnte gerechtfertigt sein, wenn da nicht der Name wäre, und man dann nicht über PrimeSupplier philosophieren könnte…
Ach, du meinst die Unterstriche _… und dass isPri nicht ausgeschrieben ist und dass Supplier vielleicht der „bessere“ Begriff wäre… Nunja, das hat ja nun nicht direkt etwas mit den Konventionen zu tun… für mich ist das einfach angenehmer zu lesen.
Und naja, das if-else Geraffel lässt sich vielleicht noch um zwei Zeilen kürzen - berechtigter Einwand.
Gibt es eine andere und bessere Möglichkeit, außer mit einer Liste von FutureTasks, alle FutureTasks abzubrechen, sobald einer/ ein FuturTask das Ergebnis „false“ liefert?
Aber das finde ich in gewisser Hinsicht genauso „schmuddelig“ wie das Beenden aller Threads über den Interrupt-„Mechanismus“… Da muss doch noch etwas Besseres an Bord sein.
Edit: Du meinst das so, oder?
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.Callable;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.FutureTask;
public class PrimeIterator {
private boolean longBased = true;
private long startLong;
private BigInteger startBI;
public PrimeIterator(BigInteger start) {
if (start.compareTo(BigInteger.valueOf(Long.MAX_VALUE)) > 0) {
longBased = false;
}
if (longBased) {
startLong = start.longValue();
} else {
startBI = start;
}
}
public BigInteger nextPrime() {
BigInteger b;
while (true) {
if (longBased) {
if (isPrime(startLong)) {
b = BigInteger.valueOf(startLong);
increase();
return b;
}
} else {
if (isPrime(startBI)) {
b = startBI;
increase();
return b;
}
}
increase();
}
}
private boolean isPrime(long toTest) {
if (toTest % 2 == 0) {
return false;
}
long sqrt = (long) Math.sqrt(startLong);
for (long i = 3; i <= sqrt; i += 2) {
if (toTest % i == 0) {
return false;
}
}
return true;
}
private static class MyTask implements Callable<Boolean> {
private final BigInteger toTest;
private final BigInteger part;
private final int multiplier;
private static volatile boolean hasFalseResult;
private MyTask(BigInteger toTest, BigInteger part, int multiplier) {
this.toTest = toTest;
this.part = part;
this.multiplier = multiplier;
hasFalseResult = false;
}
@Override
public Boolean call() throws Exception {
BigInteger from = part.multiply(BigInteger.valueOf(multiplier)).add(BigInteger.valueOf(3));
BigInteger to = part.multiply(BigInteger.valueOf(multiplier + 1)).add(BigInteger.valueOf(3));
System.out.println("starting: " + toTest + " " + from + " " + to + " " + toTest.sqrt());
return isPrime(toTest, from, to);
}
private boolean isPrime(BigInteger b, BigInteger from, BigInteger to) {
for (BigInteger i = from; to.compareTo(i) > 0; i = i.add(BigInteger.TWO)) {
if (hasFalseResult) {
return false;
}
if (b.mod(i).compareTo(BigInteger.ZERO) == 0) {
hasFalseResult = true;
return false;
}
}
return true;
}
}
private boolean isPrime(BigInteger toTest) {
// if (toTest.isProbablePrime(5)) {
if (toTest.mod(BigInteger.TWO).compareTo(BigInteger.ZERO) == 0) {
return false;
}
BigInteger sqrt = toTest.sqrt();
BigInteger part = sqrt.divide(BigInteger.valueOf(10)).add(BigInteger.ONE);
List<FutureTask<Boolean>> taskList = new ArrayList<FutureTask<Boolean>>();
for (int i = 0; i < 10; i++) {
taskList.add(new FutureTask<>(new MyTask(toTest, part, i)));
}
ExecutorService executor = Executors.newFixedThreadPool(3);
for (FutureTask<Boolean> futureTask : taskList) {
executor.execute(futureTask);
}
try {
for (FutureTask<Boolean> futureTask : taskList) {
if (!futureTask.get()) {
return false;
}
}
} catch (InterruptedException | ExecutionException e) {
e.printStackTrace();
return false;
}
return true;
// }
// return false;
}
private void increase() {
if (longBased) {
if (startLong == Long.MAX_VALUE) {
longBased = false;
startBI = BigInteger.valueOf(Long.MAX_VALUE).add(BigInteger.ONE);
} else {
startLong++;
}
} else {
startBI = startBI.add(BigInteger.ONE);
}
}
public static void main(String[] args) {
PrimeIterator pi = new PrimeIterator(BigInteger.valueOf(1));
for (int i = 0; i < 20; i++) {
System.out.println(pi.nextPrime());
}
pi = new PrimeIterator(BigInteger.valueOf(Long.MAX_VALUE - 10));
for (int i = 0; i < 5; i++) {
System.out.println(pi.nextPrime());
}
}
}
Viele. Die Frage ist, wofür der Code gedacht ist. Um mal eben Parallelisierung auszuprobieren, okay. Aber wenn es dir um Performance geht: Egal wie viel du parallelisierst, einen asymptotisch schnelleren Algorithmus wirst du damit nicht einholen. Übrigens glaube ich nicht, dass du durch die Sonderbehandlung der longs wirklich so viel einsparst, vielleicht kann der Compiler die Objekterzeugung sogar wegoptimieren. Es wäre mal eine interessante Aufgabe, BigInteger als Java-15-Record nachzuimplementieren (ist ja intern nicht viel mehr als ein int-Array).
Würde doch nichts ändern, außer dass lazy-initialisierte Werte direkt initialisiert oder jedes Mal neu berechnet werden müssten. Du verwechselst da glaub ich was mit Project Valhalla?
Den AKS-Test, das Paper „PRIMES is in P“ war eine mathematische Sensation. Viele Java-Implementierungen habe ich nicht gefunden, und ich weiß auch nicht, wie gut sie sind (es gibt jede Menge Verbesserungen am Ausgangsalgorithmus). Ein Beispiel wäre https://stromberg.dnsalias.org/svn/aks-primality/trunk/AKS.java
Sicher, ist kein Patent drauf. Für eine gute Performance wird der Pseudocode aber nicht ausreichen, wie gesagt gibt es verschiedene Verbesserungen, und die effiziente Programmierung der Schritte ist auch nicht trivial.
Gleichheit in einer Restklasse r, also links mod r == rechts mod r. Beim Rechnen in Restklassen muss man aufpassen, z.B. kann a*b 0 gelten (für a und b ungleich 0), wenn r keine Primzahl ist.
Lenstra und Pomerance haben zu dieser Vermutung in Remarks on Agrawal’s Conjecture eine Heuristik zum Finden von möglichen Gegenbeispielen angegeben. Ob es Zahlen wie die in deren Vermutung angenommenen gibt, ist jedoch bisher nicht bekannt.
klingt danach, als gebe es im verbesserten AKS-Algorithmus ebenfalls „starke Lügner“.
Du müsstest dich nur mal dazu herablassen, diese auch mal zu lesen.
?
