Fastprime Quadrupel und Primzahlvierlinge

Gammatester · Beiträge: 328 Erhaltene Danke: 101

pzktupel hat folgendes geschrieben :

Ok, es ist Freebasiccode, mit C++ habe ich es nicht so.
Anmerkung aber: Das ist ein Ergebnis nach Jahren der Tüftellei. Auch ist dieser unübersichtlich.

Hallo und willkommen im Forum. Ich habe es auch nicht so mit C++ allerdings auch nicht mit Basic. Ich würde allerdings wetten, daß Dein Programm keine Primzahlen(-vierlinge) ausgibt, sondern nur mögliche Kandidaten aussiebt, Ich weiß zwar nicht genau, was der letzte Stand im Programm von user profile icon

Mathematiker und user profile icon

Horst_H ist, aber bisher war der schon einfache Fermat-Test für die Kandidaten der Flaschenhals.

Ist der angegebene Code nur ein Ausschnitt? Was ich nicht glaube wegen der Dateiausgabe. Oder wird die Dateiausgabe in ein eigentliche Primzahl-Testprogramm gefüttert?

Gruß Gammatester

pzktupel · Hält's aus hier Beiträge: 129 Erhaltene Danke: 30

Hallo,

ja richtig, der gibt keine Primzahlen 4er aus, sondern Kandidaten Quadrupel die mittels PFGW ( das schnellste Fermattestprogramm ) getestet werden müssen.
Die Ausgabe in die Datei ist PFGW - tauglich gestaltet. Eine 660 stellige Zahl wird in 1/100 s getestet. Wäre sinnlos was anderes zu nehmen, gerade für hohe n. Das Programm, wer es kennt, hat 15 Jahre Entwicklung hinter sich.
Habs soweit, dass alle pfgw.logs nebenbei im Prozess in Abständen automatisch ausgelesen werden und bei 4-Tupel gibts ne Voiceausgabe "4 Tupel gefunden" :-)

Der Code ist der komplette Algorithmus.

Wegen n=665 : mittlerweile bald 3500 Mrd Offset fertig gesiebt und 2300 Mrd Offset abgesucht. Man sieht also den Fortschritt zum letzten Post - Zeitpunkt diesbezüglich.
Fang bald an den 4. Billionenblock zu sieben. 12h ca. 3000 Mrd. auf einem Phenom II X6 2.8 Ghz.

Gammatester · Beiträge: 328 Erhaltene Danke: 101

pzktupel hat folgendes geschrieben :

Hallo,

ja richtig, der gibt keine Primzahlen 4er aus, sondern Kandidaten Quadrupel die mittels PFGW ( das schnellste Fermattestprogramm ) getestet werden müssen.
Die Ausgabe in die Datei ist PFGW - tauglich gestaltet. Eine 660 stellige Zahl wird in 1/100 s getestet.

Danke für die Info. (Blödsinn der gestrichen wurde). Ich habe PFGW noch nie benutzt: Was wird den außer dem Fermattest noch verwendet? (MPArith mit BPSW braucht ca 400 ms für x)

Gruß Gammtester

pzktupel · Hält's aus hier Beiträge: 129 Erhaltene Danke: 30

Also das glaub ich jetz nicht mit 0,05 ms=0,0005s oder 2000 Stück pro Sekunde auf einem Kern. PFGW macht den Fermattest. 100 pro Sekunde. Intel doppelt so viele.

Bin da jetzt nicht im bilde. PFGW gibt aus, ob es sich um eine wahrscheinliche Primzahl handelt, gibt also aus ob 3^n mod n=3 ist oder nicht.

Wenn das 0.05ms braucht, was stellt den der dann fest bei einer Zahl ?

Gammatester · Beiträge: 328 Erhaltene Danke: 101

pzktupel hat folgendes geschrieben :

Also das glaub ich jetz nicht mit 0,05 ms=0,0005s o

Richtig. Habe auf die Schnelle die zwei Parameter für spsp(x,2) im TCalc-Rechner vertauscht, korrekt sind dann 120 ms. Mein Edit hat sich mit Deinem Beitrag überlappt.

pzktupel · Hält's aus hier Beiträge: 129 Erhaltene Danke: 30

Gammatester hat folgendes geschrieben :

pzktupel hat folgendes geschrieben :

Also das glaub ich jetz nicht mit 0,05 ms=0,0005s o

Richtig. Habe auf die Schnelle die zwei Parameter für spsp(x,2) im TCalc-Rechner vertauscht. Mein Edit hat sich mit Deinem Beitrag überlappt.

Also wäre PFGW 12-20 mal fixer (wegen intel vs AMD geschätzt) ? ( 1/0.4 und 1/0.01)

Wegen PFGW. Da gibt es nix schnellers. Jeder kennt Prime95 , genau diese Code ist dort enthalten.

Gammatester · Beiträge: 328 Erhaltene Danke: 101

pzktupel hat folgendes geschrieben :

Also wäre PFGW 40 mal fixer ? ( 1/0.4 und 1/0.01)

Richtig, aber umso interessanter wäre zu wissen, was PFGW wirklich macht, eine spsp(x,3) braucht auch ca 110 ms bei mir,

pzktupel · Hält's aus hier Beiträge: 129 Erhaltene Danke: 30

Gammatester hat folgendes geschrieben :

pzktupel hat folgendes geschrieben :

Also wäre PFGW 40 mal fixer ? ( 1/0.4 und 1/0.01)

Richtig, aber umso interessanter wäre zu wissen, was PFGW wirklich macht, eine spsp(x,3) braucht auch ca 110 ms bei mir,

PFGW gibt aus, ob es sich um eine wahrscheinliche Primzahl handelt oder zusammengesetzt, gibt also aus ob 3^n mod n=3 ist oder composite

Bsp.

10^ 665+2285465591911 is 3-PRP! (0.0190s+0.0001s)
10^ 665+2285465591911+2 is 3-PRP! (0.0194s+0.0043s)

Horst_H · Verfasst: Mo 04.09.17 18:35

Hallo,

nur sieben mit 300Mio/s ist ja schon recht schnell.
Sieben eines Zahlbereiches mit einer konstanten Anzahl an Primzahlen dauert auch nur eine konstante Zeit, egal wo ich da siebe.
Bei 30 Mio Siebprimzahlen sind es im Lazarusprogramm etwa 3,5 Sekunden für 460 Mio., also erheblich langsamer.
Aber weiter oben das Konsolenprogramm saust in 3 Sekunden durch 4e9 , aber die Übertragsbestimmung stimmt noch nicht, damit ich bei 10^1000 anfangen kann.

Gruß Horst

Mathematiker · Verfasst: Mo 04.09.17 18:57

Hallo,
darf ich noch einmal auf mein Problem www.entwickler-ecke.....php?p=708452#708452 zurückkommen.

Ich habe versucht den Absturz zu lokalisieren.
Konkret: Ist ein Zugriff aus dem 2.Thread auf das Programmformular; hier eine Ausgabe in die Listbox, überhaupt gestattet?
Ich vermute nicht und habe es jetzt herausgenommen. Scheinbar läuft es jetzt stabil. Den Quelltext habe ich aktualisiert.

Da ich mit mehrfachen Threads keine Ahnung habe, hoffe ich, ihr seht mir die vielleicht blöde Frage nach.

Danke
Steffen

_________________
Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein

pzktupel · Hält's aus hier Beiträge: 129 Erhaltene Danke: 30

Da hab ich keinen Schimmer, was in der Konsole passiert

Anbei, nach unter 15h konnte ich die beast-number knacken UND wie der Teufel so will, auch noch das kleinste 5-Tupel !!!

n=666: 10^665+2969689524331 +d,d=-4,0,2,6,8 sind PRPs !!!

pzktupel · Hält's aus hier Beiträge: 129 Erhaltene Danke: 30

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:

procedure PrimSieben;
var
  i,p: NativeInt;
Begin
  fillchar(PrimSieb,SizeOf(PrimSieb),Ord(true));
  p := 2;
  repeat
    i := p*p;
    while i <= High(PrimSieb) do
    Begin
      PrimSieb[i] := false;
      inc(i,p);
    end;
    repeat
      inc(p);
    until PrimSieb[p]
  until (p*p) >High(PrimSieb);
end;

Ich habe mich mal eingelesen.
Warum nicht standard auf false lassen und Elemente auf True ?
P:=3 beginnen und i=p*p+2*P , und inc (i,2*p)
PrimeSieb[i]=True setzen

p=p+2
und dann prüfen, ob p Teiler wie 3,5,7 hat, aber selbst nicht 3,5,7 ist, dann zurück und p=p+2 wie bei 9,15,21, usw
IF p=p then PrimeSieb[p]=false

Das Auslesen der Primes in ein extra Feld und zwar alle ungeraden ab 3 + 2i,oder gleich ab 23+2i

Moderiert von Th69: Delphi-Tags hinzugefügt

Horst_H · Verfasst: Mo 04.09.17 20:00

Hallo,

das primsieben ist doch auf die simpelste Art, weil es die Laufzeit kaum berührt.
Bei 4e9 muss doch nur bis 63245 gesiebt werden.
Das "große" Sieb sucht 100Mio Primzahlen in 1,4 Sekunden, aber das wird ja auch nur einmal bei den zig Stunden Suche gebraucht.
Ich habe jetzt mal mit diesen Zahlen ab dem ersten Vielfachen der Primzahl nach Quadrupeln sieben lassen.
Jetzt 2,7 Sekunden.

@ user profile icon

Mathematiker:
Ich meine gelesen zu haben , dass man auf VCL-Sachen nur über synchronize oder siehe delphi Wiki zugreifen kann.

Gruß Horst

pzktupel · Hält's aus hier Beiträge: 129 Erhaltene Danke: 30

Nehme ( nur zur Information ) n=999, 10^998+...

Mathematiker · Verfasst: Mo 04.09.17 20:17

Hallo Horst,

Horst_H hat folgendes geschrieben :

Hallo,
Ich meine gelesen zu haben , dass man auf VCL-Sachen nur über synchronize oder siehe delphi Wiki zugreifen kann.

Danke, das ist es.

LG Steffen

_________________
Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein

Delphi-Laie · Verfasst: Mo 04.09.17 21:12

Mathematiker hat folgendes geschrieben :

Hallo Horst,

Horst_H hat folgendes geschrieben :

Hallo,
Ich meine gelesen zu haben , dass man auf VCL-Sachen nur über synchronize oder siehe delphi Wiki zugreifen kann.

Danke, das ist es.

Nun, diese Essentialität steht in jeder "Rumpfdatei", die man über Datei -> Neu -> Thread-Objekt erhält, schon drin.

Edit: Wobei in dem Satz

Zitat:

Wichtig: Objektmethoden und -eigenschaften in der VCL können in Methoden
verwendet werden, die mit Synchronize aufgerufen werden, z.B.:

das entscheidende Wörtchen "nur" fehlt, also "...können nur in Methoden..." oder auch an anderer Stelle "....die nur mit Synchronize...."

Ohne Synchronisation ist es ein fragiles Glücksspiel, das oft, wenn nicht meistens schiefgeht.

Edit 2: Das war auf die Schnelle aus Delphi 4 kopiert. Delphi 2 und 3 waren in dieser Hinsicht schon weiter und präziser:

Zitat:

Wichtig: Methoden und Eigenschaften eines Objekts in der VCL
können nur in einem Methodenaufruf mit SYNCHRONIZE
genutzt werden, z.B.

Mathematiker · Verfasst: Mo 04.09.17 21:38

@Delphi-Laie.
Ich hatte geschrieben:
"Da ich mit mehrfachen Threads keine Ahnung habe, hoffe ich, ihr seht mir die vielleicht blöde Frage nach."

Ich werde mich bemühen, keine blöden Fragen mehr zu stellen.

Steffen

_________________
Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein

Delphi-Laie · Verfasst: Mo 04.09.17 21:56

Alles halb so wild.

Luckies Thread-Anleitung ist Goldstaub wert. Aber auch schon das Grundgerüst, das Delphi einem bietet, ist nützlich.

Ich hatte auch weiter vorn schon etwas dazu geschrieben (übersehen?). Man kann durchaus in die Threadorganisation eingreifen, allerdings nur sehr begrenzt.

Threads benutze ich z.B. in meinem Langzahlentaschenrechner und - dort auf "perverse Weise" - im Sortierprogramm. Deshalb hatte ich ja auch geschrieben, daß die Threadkommunikation mit Botschaften - und ressourchenschonendens Warten auf diese - wesentlich besser als das ressourcenhungrige "Polling" ist.

OlafSt · Verfasst: Di 05.09.17 08:05

Natürlich kann man sogar sehr massiv in die Thread-Verwaltung eingreifen, sogar festlegen auf welchem Kern der Thread laufen soll (und er bleibt dann auch da). Aber Multithreading ist nicht so trivial, wie einem gern vorgemacht wird. Erste Stolperfallen sind ja schon aufgetaucht.

Grundsätzlich kann man per TEvent z.B. Threads wunderbar synchronisieren. Zugriffe mehrerer Threads auf eine gemeinsame Liste per MultiReadExclusiveWriteSynchronizer. Und als oberste Regel gilt: Niemals von einem Thread aus auf die GUI zugreifen. Das darf nur der Hauptthread, solche Sachen müssen per Synchronize-Aufruf erledigt werden - was aber wieder Rechenzeit kostet, denn der Workerthread wird angehalten, bis der Hauptthread den Synchronize-Aufruf durchgeführt hat.

Ich kenne mich da ganz gut aus und kann Fragen durchaus beantworten.

_________________
Lies, was da steht. Denk dann drüber nach. Dann erst fragen.

Delphi-Laie · Verfasst: Di 05.09.17 09:54

OlafSt hat folgendes geschrieben :

Natürlich kann man sogar sehr massiv in die Thread-Verwaltung eingreifen, sogar festlegen auf welchem Kern der Thread laufen soll (und er bleibt dann auch da).

Gut, das vergaß ich.

Das ist allerdings auch eine leichte Zangengeburt. Nötig ist "SetThreadAffinityMask" und wurde in meinem Programm "Prozesse" nach einer gefühlten halben Ewigkeit implementiert.

Dennoch, und insofern bleibe ich dabei, läßt sich Windows in seinem Eingemachten, in diesem Falle nämlich, wann, wie oft, wie lange Threads gestartet und / oder unterbrochen werden, nicht hineinreden.

OlafSt hat folgendes geschrieben :

Aber Multithreading ist nicht so trivial, wie einem gern vorgemacht wird.

Nanu, wer behauptete denn wann und wo so etwas?

OlafSt hat folgendes geschrieben :

Erste Stolperfallen sind ja schon aufgetaucht.

Sehen wir es mal positiv: Delphi unterstützt die Threadprogrammierung besser als so manch andere Programmiersprache.

Edit: Suspend und Resume...sind Befehle, mit denen man Threads mit eigener Programmierung anhalten und fortsetzen kann.

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme