Entwickler-Ecke
Algorithmen, Optimierung und Assembler - Fastprime Quadrupel und Primzahlvierlinge
Mathematiker - Mo 31.07.17 14:50
Titel: Fastprime Quadrupel und Primzahlvierlinge
Hallo,
ich bin im Moment im Matheforum
Matroids Matheplanet [
http://matheplanet.com/] an der Suche nach sogenannten fastprimen Quadrupeln beteiligt.
Eine fastprime Zahl (2.Grades) ist eine natürliche Zahl, die genau aus 2 Primteilern besteht, z.B. 35 = 5*7 .
Bei einem fastprimen Quadrupel müssen die vier Zahlen innerhalb eines Zehners, die auf 1, 3, 7 und 9 enden, jeweils fastprime Zahlen sein. Das kleinste Beispiel ist 321, 323, 327, 329 mit
321 = 3 * 107 ; 323 = 17 * 19 ; 327 = 3 * 109 und 329 = 7 * 47
Mit Hilfe Gammatesters genialem mp_arith habe ich ein kleines Programm gebastelt, bei dem nach solchen Quadrupeln gesucht wird, allerdings keine kleinen Zahlen, sondern Zahlen von etwa 30 bis 250 (evtl. noch mehr) Stellen Länge.
Eingegeben wird eine Startzahl. Von dieser aus wird das nächste Quadrupel gesucht.
Für die 100stellige Startzahl (10^100-1)/9 -1 (Zahl besteht aus 99 "Einsen" und einer "Null", voreingestellt im Programm) findet mein Rechner nach knapp 17 s ein Quadrupel
Quelltext
1: 2: 3: 4: 5: 6: 7: 8:
| 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111164509081 = 43 · 25839793281653746770025839793281653746770025839793281653746770025839793281653746770025839794523467 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111164509083 = 1291 · 860659264996987692572510543075996213099234013254152680953610465616662363370341681728203804155313 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111164509087 = 7 · 158730158730158730158730158730158730158730158730158730158730158730158730158730158730158730166358441 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111164509089 = 463 · 2399808015358771298296136309095272378209743220542356611471082313414926805855531557475401967957903 |
Es funktioniert problemlos.
Das Problem ist, dass ich in einem kleinen "Wettbewerb" bin. Im Moment bin ich noch auf "Platz 1", aber es ist schon ein C++ Programm angekündigt, das wohl schneller sein will.
Nun meine Fragen:
1. Sieht jemand von euch eine Möglichkeit, den Algorithmus (Erklärung weiter unten) noch etwas zu optimieren?
2. Kann jemand von euch den Quelltext einmal mit einem 64bit-Delphi übersetzen und mir die Exe senden (ich weiß nicht, ob das legal ist)? Ich hoffe auf einen kleinen Zeitgewinn.
Ich habe die D10 Starter-Version getestet. Allerdings braucht deren Exe 2 s mehr, d.h. etwas langsamer.
Danke für jede Hilfe
Steffen
PS: Es wäre nicht schön, wenn so ein "komisches" C-Programm unser geliebtes Delphi schlägt. :wink:
Erklärung meines Algorithmus:
Beginnend ab einer großen Zahl, im Quelltext m1, werden in einem Feld "zahl" die 20 Millionen Werte mit einem Primzahlsieb bearbeitet, d.h. alle durch die Primzahlen teilbaren Werte ausgesiebt.
Ist eine Zahl durch eine der Primzahlen < 10 Millionen teilbar, so wird der Feldwert um 1 erhöht.
Evtl. fastprime Zahlen dürfen und sollen hier nach dem Siebvorgang nur einmal ausgesiebt sein, d.h. der Feldwert von "zahl" muss 1 sein.
Nur wenn alle vier Zahlen (auf 1,3,7,9 endend) den Wert 1 haben, sind sie "Kandidat" für ein Quadrupel.
Anschließend wird jeder Kandidat genauer getestet, d.h. ein kleiner Primteiler ermittelt und der verbleibende Faktor auf Primzahleigenschaft getestet.
Kann dies für alle vier Zahlen des Zehners bestätigt werden, ist ein Quadrupel gefunden.
Wird unter den 20 Millionen Zahlen des Feldes "zahl" nichts gefunden, wird die Anfangszahl m1 um 20 Millionen erhöht und der ganze Vorgang erneut gestartet.
Die Größe des Feldes (20 Millionen) und die maximale Testprimzahl (10 Millionen) habe ich durch Versuch und Irrtum so bestimmt, dass die Rechenzeit möglichst kurz wird.
Ein gefundenes Ergebnis wird nachträglich unter
http://www.alpertron.com.ar/ECM.HTM kontrolliert, da der 2.Faktor "nur" mit einem starken Pseudoprimzahltest kontrolliert wird.
Der aktuelle Rekord (nicht von mir) mit meinem Programm ist ein Quadrupel ab dem 300stelligen 3*10^299+333333333333333333333333667017821 nach 1 Stunde Rechenzeit.
Edit: Letzte Verbesserung (Rev 3) von Horst_H durchgeführt. Danke.
Rev 4 enthält Verbesserung durch Gammatester. Danke.
Rev 5 vom 4.8.17
Edit: Titel geändert, da es auch um Primzahlvierlinge geht
Gammatester - Mo 31.07.17 15:46
Leider wird die Portierung auf 64-Bit nicht einfach, und es liegt nicht an meinem Code (der erzeugt nur einige Warnung, die IMO via explizites Ansi-String behoben werden können). Die fehlende
mp_bas64.inc kann man sich aus dem Archiv holen, und dann sind alle Files da. Das
Hauptproblem ist der ASM-Code
IstPrime von Hagen Reddmann, der ist nämlich für
32-Bit-Assembler. Das Ergebnis
Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41: 42: 43: 44: 45: 46: 47: 48: 49: 50: 51: 52: 53: 54:
| C:\TEST>D:\DMX\M1864\DCC64 -b FastprimeQuadrupel.dpr Embarcadero Delphi for Win64 compiler version 25.0 Copyright (c) 1983,2013 Embarcadero Technologies, Inc. std.inc(632) std.inc(632) btypes.pas(200) std.inc(632) mp_conf.inc(175) mp_types.pas(739) mp_conf.inc(175) std.inc(632) mp_conf.inc(175) std.inc(632) isaac.pas(424) mp_isaac.inc(101) mp_prng.pas(198) mp_bas64.inc(180) mp_base.pas(11195) std.inc(632) mp_conf.inc(175) std.inc(632) mp_conf.inc(175) mp_modul.pas(1761) std.inc(632) mp_conf.inc(175) mp_prm16.inc(411) mp_pbits.inc(262) mp_prime.pas(2218) mp_numth.pas(7667) Uquadrupel.pas(70) Error: E2116 Invalid combination of opcode and operands Uquadrupel.pas(71) Error: E2116 Invalid combination of opcode and operands Uquadrupel.pas(72) Error: E2116 Invalid combination of opcode and operands Uquadrupel.pas(73) Error: E2116 Invalid combination of opcode and operands Uquadrupel.pas(80) Error: E2116 Invalid combination of opcode and operands Uquadrupel.pas(84) Error: E2116 Invalid combination of opcode and operands Uquadrupel.pas(86) Error: E2107 Operand size mismatch Uquadrupel.pas(87) Error: E2107 Operand size mismatch Uquadrupel.pas(99) Error: E2116 Invalid combination of opcode and operands Uquadrupel.pas(100) Error: E2116 Invalid combination of opcode and operands Uquadrupel.pas(101) Error: E2116 Invalid combination of opcode and operands Uquadrupel.pas(102) Error: E2116 Invalid combination of opcode and operands Uquadrupel.pas(132) Error: E2116 Invalid combination of opcode and operands Uquadrupel.pas(147) Error: E2116 Invalid combination of opcode and operands Uquadrupel.pas(151) Error: E2116 Invalid combination of opcode and operands Uquadrupel.pas(152) Error: E2116 Invalid combination of opcode and operands Uquadrupel.pas(157) Error: E2116 Invalid combination of opcode and operands Uquadrupel.pas(185) Error: E2116 Invalid combination of opcode and operands Uquadrupel.pas(238) Error: E2116 Invalid combination of opcode and operands Uquadrupel.pas(276) Warning: W1058 Implicit string cast with potential data loss from 'TCaption' to 'AnsiString' Uquadrupel.pas(285) Warning: W1057 Implicit string cast from 'AnsiString' to 'string' Uquadrupel.pas(342) Warning: W1057 Implicit string cast from 'AnsiString' to 'string' Uquadrupel.pas(342) Warning: W1057 Implicit string cast from 'AnsiString' to 'string' Uquadrupel.pas(406) FastprimeQuadrupel.dpr(5) Fatal: F2063 Could not compile used unit 'Uquadrupel.pas' |
Ich vermute, daß auf Grund der 'Optimierung' der Asmcode nicht auf 64-Bit gerettet werden kann (soweit ich mich erinnere, wurde das schon ein paar mal versucht). Vielleicht hat Horst_H ja eine Freepascal-64-Bit Lösung.
Wenn Du nur 32-Bit-Primzahltest machen willst (wie Hagen), kann man auch mein
IsPrime32 nehmen.
Gruß Gammatester
Mist: Habe wieder Zitat statt Edit gedrückt. Der erste Beitrag kann gelöscht werden. Wann gibt's eigentlich einmal eine Löschmöglichkeit für den Ersteller?
Mathematiker - Mo 31.07.17 16:00
Hallo Gammatester,
vielen Dank für deine Bemühungen.
Es ist nicht so schlimm, wenn es nichts mit den 64bit wird.
Ich habe nämlich noch die Hoffnung, dass ein C-Programm nicht so einfach dein schnelles mp_arith schlagen kann. :wink:
Ich werde jetzt erst einmal dein isprime32 einbauen.
Vielen Dank
Steffen
Gammatester - Mo 31.07.17 16:17
Habe mal mit IsPrime32 gerechnet, das Ergebnis auf meinem CoreI3/2.3 GHz mit D18/64 under Win7/64:
Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16:
| Test bis 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110 + 20000000 Kandidaten = 4512 Test bis 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111131111110 + 20000000 Kandidaten = 4657 Test bis 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111151111110 + 20000000 Kandidaten = 4605 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111164509081 = 43 · 25839793281653746770025839793281653746770025839793281653746770025839793281653746770025839794523467 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111164509083 = 1291 · 860659264996987692572510543075996213099234013254152680953610465616662363370341681728203804155313 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111164509087 = 7 · 158730158730158730158730158730158730158730158730158730158730158730158730158730158730158730166358441 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111164509089 = 463 · 2399808015358771298296136309095272378209743220542356611471082313414926805855531557475401967957903 Zeit: 20,98 s ---------- |
Gruß Gammatester
PS: Hatte erst immer Fehler beim Starten, das Problem bei 64-Bit ist {$R windowsxp.res}, nachdem ich's auskommentiert habe läuft das Programm (schein eine inkompatible 32-Bit-Resource zu sein).
Edit: Vielleicht hilf auch ein aufgebohrtes
Delphi-Quelltext
1: 2:
| procedure s_mp_nextprime_sieve(safe: boolean; var n: mp_int); |
statt Deiner Kandidatenwahl.
Mathematiker - Mo 31.07.17 16:34
Hallo,
Gammatester hat folgendes geschrieben : |
Habe mal mit IsPrime32 gerechnet, das Ergebnis auf meinem CoreI3/2.3 GHz mit D18/64 under Win7/64: ... Zeit: 20,98 s
|
Danke, das klingt doch schon gut.
Gammatester hat folgendes geschrieben : |
Hatte erst immer Fehler beim Starten, das Problem bei 64-Bit ist {$R windowsxp.res}, nachdem ich's auskommentiert habe läuft das Programm (schein eine inkompatible 32-Bit-Resource zu sein). |
Danke für den Hinweis. Ich habe den Anhang im 1.Beitrag schon geändert.
Gammatester hat folgendes geschrieben : |
Vielleicht hilf auch ein aufgebohrtes
Delphi-Quelltext 1: 2:
| procedure s_mp_nextprime_sieve(safe: boolean; var n: mp_int); |
statt Deiner Kandidatenwahl. |
Danke für den Hinweis. Sehe ich mir gleich an.
Steffen
Mathematiker - Mo 31.07.17 17:07
Hallo,
ich habe noch ein kleine Verbesserung, die sich vor allem bei längeren Berechnungen zeigt.
Ich berechne zu Beginn 700000 Primzahlen und stecke sie in ein Feld. Dadurch spare ich bei jedem neuen Sieben die Berechnung.
Mit Gammatesters isprime32 bin ich damit beim Ausgangsbeispiel bei 16,4 s, also schneller.
Und besonders wichtig: 32bit-Istprime von Hagen Reddmann ist ersetzt.
Im ersten Beitrag habe ich den Anhang geändert.
Steffen
Gammatester - Mo 31.07.17 17:08
Mathematiker hat folgendes geschrieben : |
Danke für den Hinweis. Ich habe den Anhang im 1.Beitrag schon geändert. |
Du solltest auch gleich
mp_bas64.inc in den Anhang packen, damit 64-Bit-Tester nicht gleich abgeschreckt werden.
Mathematiker - Mo 31.07.17 17:48
Hallo,
es geht noch schneller.
Die jetzt 800000 Primzahlen berechne ich am Anfang mit einem Sieb, statt einer Funktion.
Zeitgewinnung noch einmal eine knappe Sekunde, d.h. beim Eingangsbeispiel nun 15,4 s.
Der Anhang ist angepasst.
Steffen
Delete - Mo 31.07.17 17:56
- Nachträglich durch die Entwickler-Ecke gelöscht -
Mathematiker - Mo 31.07.17 18:01
Frühlingsrolle hat folgendes geschrieben : |
Zitat: | Die jetzt 800000 Primzahlen berechne ich am Anfang mit einem Sieb, statt einer Funktion. |
Wäre das nicht gleichgesetzt mit Schummeln? |
Wieso?
Es geht darum, so schnell wie möglich fastprime Zahlen in der Größenordnung von 100 Stellen zu berechnen.
Dazu braucht man die Primzahlen.
Ob ich sie mit istprime, Gammatesters isprime32 oder irgendwie anders ermittle ist egal.
Im Gegenteil, ja einfacher (raffinierter :wink: ) der Algorithmus ist, desto besser.
Steffen
Delete - Mo 31.07.17 18:05
- Nachträglich durch die Entwickler-Ecke gelöscht -
Mathematiker - Mo 31.07.17 18:24
Frühlingsrolle hat folgendes geschrieben : |
Schon klar, es soll möglichst flott gehen, nur wenn die Anwendung eine Zeitspanne von x braucht um zu starten / Primzahlen auszusieben, und erst im Anschluss die Berechnung / Zeitmessung erfolgt, fühlt es sich "nicht richtig" an. Lass' dich davon jetzt irritieren. Ich hab' nur zu laut gedacht. :D |
Richtig.
Schau dir den Quelltext an. Dort wird erst die Startzeit ermittelt und danach gesiebt.
Also ist es korrekt.
Steffen
Gammatester - Mo 31.07.17 18:25
Mathematiker hat folgendes geschrieben : |
Hallo,
es geht noch schneller.
Die jetzt 800000 Primzahlen berechne ich am Anfang mit einem Sieb, statt einer Funktion.
Zeitgewinnung noch einmal eine knappe Sekunde, d.h. beim Eingangsbeispiel nun 15,4 s.
Der Anhang ist angepasst.
Steffen |
Bei mir braucht deine EXE 21,7s und meine angepaßte 64-Bit 13,25s (angepaßt weil ich
Delphi-Quelltext
1: 2: 3: 4:
| uses Winapi.Windows, winapi.Messages, system.SysUtils, system.Variants, system.Classes, vcl.Graphics, vcl.Controls, vcl.Forms, vcl.Dialogs, vcl.StdCtrls, mp_base, mp_numth, mp_prng, mp_prime, mp_types, vcl.Buttons, Vcl.Samples.Spin; |
und außerdem den Stack erhöhen mußte, weil die Default-Einstellungen einen Stack-Overflow erzeugen)
Mathematiker - Mo 31.07.17 18:28
Gammatester hat folgendes geschrieben : |
Bei mir braucht deine EXE 21,7s und meine angepaßte 64-Bit 13,25s ... |
Sehr schön, die Exe würde mich interessieren.
Steffen
Horst_H - Mo 31.07.17 18:37
Hallo,
nun ja bis 1e7 kann ein modifiziertes Erathotenes Sieb schon in 0.02 s fertig sein, das macht den Kohl nicht fett
http://rosettacode.org/wiki/Sieve_of_Eratosthenes#alternative_using_wheel .
IstPrim war ja auch nicht für aufeinanderfolgende Zahlen gedacht.
Vielleicht sollte man sich bei Kim Walisch ein paar Tipps holen, der macht das schon seit mindestens 2001 und vor 20h auch.
https://github.com/kimwalisch/primesieve
Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9:
| Primzahlen bis .. 200560490130 ( 2*3*5*7*11*13*17*19*23*29*31 ) Prime numbers: 8028643010 Twin primes: 425177757 Prime triplets: 73990934 Prime quadruplets: 2166281 Prime quintuplets: 427251 Prime sextuplets: 14804
Elapsed time: 34.55 sec |
Er benutzt spezielle Bit-Masken um die Quadrupel in dem Bitfeld zu finden.
Sicher werden die C-Leute darauf zurückgreifen, aber das eigentliche Problem bleibt das testen auf "möglicherweise prim".
Man sollte die Zeit mal dafür stoppen.
Vielleicht gibt es einen Dreh, nur die möglichen Quadrupel abzufragen und so das sieben zu beschleunigen.Will sagen, wenn ich weiß, dass das nächste mögliche Quadrupel 1000 weiter liegt,( oben liegen sie im Mittel scheinbar 1e5 auseinander, 2e6 von 2e11 ) brauche ich die Primzahlen dazwischen auch nicht testen.Aber das halte ich nicht für entscheidend.
Gruß Horst
Holgerx - Mo 31.07.17 18:58
Hmm..
Ich habe mir FastprimeQuadrupel angeschaut..
Wenn es noch um ein (klitzekleines) Speedup geht:
Mache keine Anzeige im Memo oder oben (Zeitanzeige) während der Berechnungen..
Sammle die Text-Ausgaben in einer eigenen Stringlist und bringe diese erst (nach dem Timer Stop) ins Memo..
Sind zwar nur minimale Zeitersparnisse, aber vielleicht ist das dann das entscheidende halbe Sekündchen ;)
Jeder Zugriff aufs Memo mit allen seinen Messeges und Co dauert lange.
Oder zu Begin deiner Berechnung 'Memo1.Lines.BeginUpdate;' und dann zum Schluss 'Memo1.Lines.EndUpdate;', somit bleiben die Change-Events aus.
Ist nicht viel, aber wir reden hier von HighSpeed ;)
Oder, um die VCL-Bremse auszuschalten:
Mach nen Konsolenprogramm daraus.. ;)
Oder steht irgendwo geschrieben, wie die Ausgabe gemacht werden muß?
Gammatester - Mo 31.07.17 19:37
Horst_H hat folgendes geschrieben : |
Hallo,
nun ja bis 1e7 kann ein modifiziertes Erathotenes Sieb schon in 0.02 s fertig sein, das macht den Kohl nicht fett |
Mit bord-eigenen Mittel (sprich MPArith) kann man die Primzahlen bis 800000 in ca 50 ms berechnen
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32:
| program t_tt5;
{$i STD.INC} {$i mp_conf.inc}
{$ifdef APPCONS} {$apptype console} {$endif}
uses hrtimer, mp_prime, mp_base, mp_types;
var p: longint; HR: THRTimer; sieve: TSieve; const PMAX = 8000000; begin StartTimer(HR); prime_sieve_init(sieve, 2); repeat p := prime_sieve_next(sieve); until p>PMAX; writeln('Time [s]: ',ReadSeconds(HR):1:6); prime_sieve_clear(sieve); end.
D:\Work\MPArith>t_tt5.exe Time [s]: 0.048456 |
aber wie gesagt, daß macht den Kohl nicht fett.
Mathematiker - Mo 31.07.17 19:43
Hallo,
Gammatester hat folgendes geschrieben : |
prime_sieve_init(sieve, 2);
repeat
p := prime_sieve_next(sieve);
until p>PMAX;
prime_sieve_clear(sieve);
|
So funktioniert das! Sehr interessant.
Ich habe mich selbst ziemlich dämlich angestellt und bekam nur Unfug.
Die Frage ist jetzt nur, wie ich auf die einzelnen Primzahlen im Sieb zugreife.
Steffen
Gammatester - Mo 31.07.17 20:07
Mathematiker hat folgendes geschrieben : |
Hallo,
...
Die Frage ist jetzt nur, wie ich auf die einzelnen Primzahlen im Sieb zugreife.
|
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22:
| var p,cnt: longint; HR: THRTimer; sieve: TSieve; myprimes: array[1..63951] of longint; begin StartTimer(HR); prime_sieve_init(sieve, 2); cnt := 0; repeat p := prime_sieve_next(sieve); inc(cnt); myprimes[cnt] := p; until cnt=63951; writeln(p); writeln('Time [s]: ',ReadSeconds(HR):1:6); prime_sieve_clear(sieve); end.
D:\Work\MPArith>t_tt5.exe 799999 Time [s]: 0.009524 |
Delete - Mo 31.07.17 20:28
- Nachträglich durch die Entwickler-Ecke gelöscht -
Delphi-Laie - Mo 31.07.17 20:30
Mathematiker hat folgendes geschrieben : |
2. Kann jemand von euch den Quelltext einmal mit einem 64bit-Delphi übersetzen und mir die Exe senden (ich weiß nicht, ob das legal ist)? |
Die Weitergabe der Compilate ist rechtlich unproblematisch.
Ansonsten gib den Versuch auf, in bezug auf Geschwindigkeit die Nase vorn zu behalten. Sofern der gleiche Algorithmus zugrundeliegt, ist es aussichtslos, Delphi- mit C-Compilaten mithalten zu lassen (sofern nicht mit Assembler "gemogelt" wird). Delphi hat andere Stärken, so z.B. tendenziell geringere Entwicklungszeiten.
Horst_H - Mo 31.07.17 20:49
Hallo,
@
Gammatester
s_mp_nextprime_sieve kann man schneller machen, wenn man vorgesiebte Zahlen nimmt.
Wenn man 2,3,5,7,11,13 siebt wiederholt sich das Muster alle 2*3*5*7*11*13 = 30030, wenn man die 1 wieder setzt und 2,3,5,7,11,13 entfernt.Das kann noch weiter (17,19.. ) treiben, wird aber unhandlich.
Wenn Deine Siebgröße ein Vielfaches von 30030 wäre, könntest Du diese vorgesiebten Zahlen direkt einfügen und bräuchtest erst mit 17 beginnen.Wenn man dann noch in 8 Bit die möglichen Primzahlen von 1..30 ( fehlen eben Vielfache von 2,3,5 ) nutzt, wird es sehr kompakt. mit 1001 Byte pro 30030 bei 32KB Level-1 Cache kommt man schon auf 32*30030= 960960 Zahlen für ein Sieb.
Siebnummer = Zahl / 30030;
Sieboffset = Zahl mod 30030
Etwas rechnerischer Aufwand wäre die erstmalige Bestimmung des Übertrages der 800.000 Streichprimzahlen, bei den riesigen Zahlen... (800.000 * 11 Division ( 100 Dezimalen im 2^31 longint- Format, sind 11 LongInts ( 2^(11*31 ) ) etwa 1 Sekunde schätze ich) )
Wenn ich jetzt sehe, das nach 64 Mio schon ein Quadrupel gefunden wird...
Du nutzt ja nur ungerade Zahlen als Bits gespeichert.
Habe ich auch mal mit boolean getan, bei Sieb mit Startzahl.Um 4 Sekunden für 4e9 ( immer noch Haswell 3.5 Ghz )
Wenn man einmal die Überträge hat, kann man einfach kontinuirlich sieben, indem man nicht die absolute Zahl speichert sondern nur die Anzahl der Siebe bis man wieder mit einer Zahl streichen muss und den Übertrag dort.Bei jedem Durchgang zählt man die um eins runter und bei Null beginnt man bei dem gespeicherten Übertrag weiter zu machen.
Also ein Sieb mit begrenzter Zahl an Siebprimzahlen sieben und dann nur die möglichen Quadrupel auf probably prime testen.
Ich gespannt,was das hier ergibt,
Gruß Horst
Gammatester - Mo 31.07.17 21:31
Horst_H hat folgendes geschrieben : |
Hallo,
@ Gammatester
s_mp_nextprime_sieve kann man schneller machen, wenn man vorgesiebte Zahlen nimmt.
|
Kann sein, aber wie Du schon geschrieben hast, die Bestimmung der Primzahlen macht den Kohl nicht fett, die meiste Zeit wird für dem Fermat- und den BPSW-Test verbraucht.
@
Mathematiker Hier eine dramatische Verbesserung:
Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17:
| Primzahlberechnung: 0,2378 s Test bis 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110 + 20000000 Kandidaten = 4385 Test bis 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111131111110 + 20000000 Kandidaten = 4535 Test bis 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111151111110 + 20000000 Kandidaten = 4490 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111164509081 = 43 · 25839793281653746770025839793281653746770025839793281653746770025839793281653746770025839794523467 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111164509083 = 1291 · 860659264996987692572510543075996213099234013254152680953610465616662363370341681728203804155313 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111164509087 = 7 · 158730158730158730158730158730158730158730158730158730158730158730158730158730158730158730166358441 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111164509089 = 463 · 2399808015358771298296136309095272378209743220542356611471082313414926805855531557475401967957903 Zeit: 8,719 s ---------- |
Dies wird erreicht durch die Ersetzung
Delphi-Quelltext
1: 2: 3:
| ergeb := mp_is_spsp_d(m3,2) and mp_is_slpsp(m3); |
damit spart man sich den doppelten Test auf kleine Faktoren.
Mathematiker - Mo 31.07.17 21:32
Hallo,
und erst einmal an alle Danke für die vielen Anregungen.
Ich habe jetzt einiges berücksichtigt, u.a. die Ausgaben während der Rechnung reduziert, aber vor allem Gammatesters Primzahlsieb eingebaut. Das ist richtig schnell.
Außerdem bin ich zum Delphi 5-Compiler zurück, da die Exe ein klein wenig fixer ist. Die maximale Stackgröße muss aber auf $00800000 gesetzt werden.
Im Matheforum haben sich die Anderen darauf geeinigt, für den Primzahltest nur einen Fermattest zur Basis 2 zu verwenden, da sehr große Tupel ohnehin über
https://www.alpertron.com.ar/ECM.HTM nachgeprüft werden.
Deshalb habe ich auch Gammatesters Fermattest eingebaut.
Alle zusammen dauert die Rechnung für (10^100-1)/9 - 1 nur noch 9,14 s. Hauptursache ist der schnellere Fermattest.
Der Anhang ist wieder geändert.
@Delphi-Laie: Dass C i.A. schnellere Exen liefert, ist klar. Aber ohne eine sehr schnelle Langzahlarithmetik, wie mp_arith, geht es nicht.
Wir werden sehen, wie schnell das Programm sein wird.
Die anderen Hinweise sehe ich mir noch an, insbesondere das Primzahlsieb. Vielleicht kann noch etwas Zeit gewonnen werden.
Eigentlich ist die Suche nach diesen Zahlen vollkommen ohne Bedeutung. Ich finde es aber gerade reizvoll zu testen, wie weit man ein Verfahren noch optimieren kann.
Mein allererster Versuch benötigte für (10^64-1)/9 noch 1053 Sekunden, jetzt sind es noch 1,04 s. So etwas finde ich schön.
Beste Grüße und nochmals Danke für die bisherige Hilfe
Steffen
@Gammatester: Ich habe gerade den neuen Eintrag gesehen. Danke.
Gammatester - Mo 31.07.17 22:02
Mathematiker hat folgendes geschrieben : |
Dass C i.A. schnellere Exen liefert, ist klar. Aber ohne eine sehr schnelle Langzahlarithmetik, wie mp_arith, geht es nicht.
Wir werden sehen, wie schnell das Programm sein wird. |
Richtig, aber schnelle Arithmetik ist nicht alles.
https://gmplib.org/ ist wahrscheinlich sau-schnell, aber es fehlen halt einige High-Level-Funktionen für Zahlentheorie (Fermat-Test ist wohl vorhanden, weil der für Miller-Rabin/RSA gebraucht wird). Soweit ich das sehe, gibt es für eine ältere Version ein GMP-FPC-Interface.
Horst_H - Di 01.08.17 17:23
Hallo,
ein bisschen was geht beim Sieben.Bei mir jetzt statt fast 7s nun 5,6s.
Ich speichere bei den Primzahlen die Überträge mit ab, sodass nur bei der Erstellung der Primzahlliste der erste Übertrag ins Siebfeld berechnet werden muss und nicht bei jedem neuen Sieb.Das Sieb habe ich 1e6 verkleinert, dass es in den Level-2 Cache passt, das bringt ungefähr nichts bis garnichts ;-) Aber mit 1,5 bis 3,5 Mio Primzahlen zu sieben bringt etwas.Wenn man bedenkt, das die Primzahlen schon erheblich größer als das Sieb sind.
Mir fehlt eine zündende Idee die kleine Primzahl auch zu kompakt im Sieb zu speichern.Momentan schwebt mir etwas wie Anzahl als Byte und Streichprimzahlnr shl 8 vor. Dann hätte ich 24 Bit für Primzahlindex-> 16,7 Mio..
Da es keine 250 Streichungen für Zahlen mit 100 Dezimalen gibt, könnte das klappen.
Damit hätte man den kleinen Teiler < Obergrenze == 10000 schon sicher gefunden und könnte bei einem Index > 1228 ( die 5 fehlt ) schon direkt eine Prüfung sparen.
Gruß Horst
Mathematiker - Di 01.08.17 18:41
Hallo Horst,
Danke für deine Änderungen.
Ich habe es probiert und bin begeistert, da deutlich schneller.
Seit 1 Stunden versuche ich nun herauszufinden, warum bei den Startzahlen
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110
und
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111120
völlig unterschiedliche Zahlen herauskommen.
Im 1.Fall tolle 7,84 s, im 2.Fall das Doppelte, nämlich 15,2 s.
Ich habe keine Ahnung.
Beste Grüße
Steffen
Nachtrag: Ich habe es gefunden. Bei
Delphi-Quelltext
1: 2: 3: 4: 5:
| with primzahlen[1] do Begin prPrimZ :=3; prUebertrag := 3-rest; end; |
war ein p 'reingerutscht.
Super, damit sind es 15 % Zeitgewinn.
Gammatester - Di 01.08.17 19:38
Mathematiker hat folgendes geschrieben : |
Hallo Horst,
Danke für deine Änderungen.
Ich habe es probiert und bin begeistert, da deutlich schneller.
Seit 1 Stunden versuche ich nun herauszufinden, warum bei den Startzahlen
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110
und
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111120
völlig unterschiedliche Zahlen herauskommen.
Im 1.Fall tolle 7,84 s, im 2.Fall das Doppelte, nämlich 15,2 s.
Ich habe keine Ahnung.
|
Ich habe ähnliches festgestellt (mit Deinem alten Progamm), wenn ich die Einstellung
kleiner Teiler maximal ändere. Hier für
default 10000
Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9:
| 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111164509081 = 43 · 25839793281653746770025839793281653746770025839793281653746770025839793281653746770025839794523467 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111164509083 = 1291 · 860659264996987692572510543075996213099234013254152680953610465616662363370341681728203804155313 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111164509087 = 7 · 158730158730158730158730158730158730158730158730158730158730158730158730158730158730158730166358441 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111164509089 = 463 · 2399808015358771298296136309095272378209743220542356611471082313414926805855531557475401967957903 Zeit: 13,7 s |
und für 1000
Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9:
| 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111253982611 = 7 · 158730158730158730158730158730158730158730158730158730158730158730158730158730158730158730179140373 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111253982613 = 13 · 85470085470085470085470085470085470085470085470085470085470085470085470085470085470085470096460201 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111253982617 = 23 · 48309178743961352657004830917874396135265700483091787439613526570048309178743961352657004837129679 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111253982619 = 673 · 1650982334489020967475648010566286940729734191844147267624236420670298827802542512795113092502203 Zeit: 30,2 s |
Ich vermute, daß eine andere Kandidatenwahl stattfindet, d.h. daß die Kandiatenwahl von diesem (und ev. anderen Parametern abhängt) und nicht für alle Parameter dieselbe ist. Bei kleineren max. Teiler, dürften sonst nur ein paar Zahlen beim Elimiminieren der kleinen Teiler als prim durchgehen, die dann aber durch den Fermat-Test erschlagen werden.
Mathematiker - Di 01.08.17 19:45
Hallo Gammatester,
Gammatester hat folgendes geschrieben : |
Ich habe ähnliches festgestellt (mit Deinem alten Progamm), wenn ich die Einstellung kleiner Teiler maximal ändere. |
Das ist klar. Ich nutze deine Funktion
Delphi-Quelltext
1:
| mp_small_factor(m1,minteiler,maxteiler,teilerx); |
Dann wird im 2.Beispiel die 1291 aus dem 1. nicht erkannt.
Beste Grüße
Steffen
Gammatester - Di 01.08.17 19:49
Mathematiker hat folgendes geschrieben : |
Das ist klar. Ich nutze deine Funktion
Delphi-Quelltext 1:
| mp_small_factor(m1,minteiler,maxteiler,teilerx); |
Dann wird im 2.Beispiel die 1291 aus dem 1. nicht erkannt.
|
Natürlich, jetzt kommt es wieder. Du suchst ja Semi-Primzahlen, und der (zeitaufwendige) Test findet nur für den großen Teiler statt. Richtig?
Mathematiker - Di 01.08.17 19:51
:zustimm:
Gammatester - Di 01.08.17 20:47
Noch eine kleine Verbesserung: Mit den neuen Erkenntnissen habe ich auch für den Primzahlcheck des großen Teilers eine Suche nach kleinen Faktoren eingefügt. Dies bringt bei Delphi6 aus der IDE ca. 7% (von 10.6s nach 9.9). Die Code-Änderungen in Button1Click:
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12:
| const MAXTM3 = 512; var tb: mp_digit; ... mp_div(m1,m2,m3); if teilerx <= MAXTM3 then begin mp_small_factor(m3,teilerx,MAXTM3,tb); end else tb := 0; ergeb:= (tb=0) and s_mp_is_psp2(m3); |
Mathematiker - Di 01.08.17 21:14
Hallo Gammatester,
Danke für die Verbesserung. Bei mir sind es knapp 10 %.
Beste Grüße
Steffen
Horst_H - Mi 02.08.17 12:02
Hallo,
endlich komme ich mit Lazarus 1.8 RC1 Linux-64Bit unter 3s und mit Lazarus 1.8 RC3 unter Wine 2.0 32-Bit unter 5s :D
Aber nur, wenn ich die Labelausgabe abschalte, die kostet enorm Zeit :-( -> unter wine dann 6s.
Ein bisschen Trickserei ist nötig, denn unter CPU64 ist mparith auch fast doppelt so schnell und deshalb lohnt sich das exzessive sieben auch nicht.Also nur 0.75 statt 1.8 Mio Siebprimzahlen.
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9:
| const {$IFDEF CPU64} groesse = 1000 * 1000; anzahl_primzahlen = 750 * 1000; {$ELSE} groesse = 1000 * 1000; anzahl_primzahlen = 1800 * 1000; {$ENDIF} MAXTM3 = 512; |
Ich siebe jetzt mit doppelter Schrittweite, dafür muss der Übertrag anders bestimmt werden.
Das bringt nicht mehr viel.
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17:
| prime_sieve_init(sieve, 7); i := 2; repeat p := prime_sieve_next(sieve); mp_mod_int(m4, p, rest); mp_mod_int(m4, 2 * p, rest2); with primzahlen[i] do begin prPrimZ := p; if (rest <> rest2) then prUebertrag := 2 * prPrimZ - rest else prUebertrag := prPrimZ - rest; end; Inc(i); until i > anzahl_primzahlen; prime_sieve_clear(sieve); |
Die Multiplikation der vier aufeinanderfolgenden Werte habe ich durch eine if-Kette ersetz, das ist ein paar ms schneller, eher in der Messtoleranz.
Mein Versuch mit der Abspeicherung von TeilerX brachte noch nichts, irgendwann hatte ich einen Wurm oder doch nur einen Käfer drin.
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8:
| while (isieb <= groesse) do begin zahl[isieb] := ((zahl[isieb] + 1) and $000000FF) + i; Inc(isieb, p); end; inc(pPrim); inc(i,256); |
und dann
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12:
| const deltaP: array[1..4] of integer = (0, 2, 6, 8 ); ... if ((zahl[j] and $FF) = 1) and ((zahl[j + 2] and $FF) = 1) and ((zahl[j + 6] and $FF) = 1) and ((zahl[j + 8] and $FF) = 1) then begin Inc(testzahl); p := 1; repeat ergeb := False; teilerx := primzahlen[Zahl[j + deltaP[p]] shr 8].prPrimZ; |
Schauen mer mal, denn sehen mer schon....
Gruß Horst
[EDIT]
Fehler gefunden, bei der Vermeidung der Bestimmung von teilerX.Unter 64-Bit doch deutliche 0.6s schneller.
Statt 2.9s nun 2.3s :-)
Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10:
| 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111164509081 = 43 * 25839793281653746770025839793281653746770025839793281653746770025839793281653746770025839794523467 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111164509083 = 1291 * 860659264996987692572510543075996213099234013254152680953610465616662363370341681728203804155313 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111164509087 = 7 * 158730158730158730158730158730158730158730158730158730158730158730158730158730158730158730166358441 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111164509089 = 463 * 2399808015358771298296136309095272378209743220542356611471082313414926805855531557475401967957903 Zeit: 00:00:02.269 ---------- |
32-bittig ist es nur 0.1 s schneller, 4.8s statt 4.9s
[EDIT 2]
Ich habe mal cross-compilieren probiert, geht ja einfach...
32-bittig wird schneller
Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16:
| Linux 64 fpc 3.1.1 ( experimentell ) ... = 463 * 2399808015358771298296136309095272378209743220542356611471082313414926805855531557475401967957903 Zeit: 00:00:02.407 ---------- Win64 und wine 2 fpc 3.1.1 ... = 463 * 2399808015358771298296136309095272378209743220542356611471082313414926805855531557475401967957903 Zeit: 3.308 s ---------- Linux32 fpc 3.1.1 ... = 463 * 2399808015358771298296136309095272378209743220542356611471082313414926805855531557475401967957903 Zeit: 00:00:04.273 ---------- Win32 und wine 2 fpc 3.1.1 ... = 463 * 2399808015358771298296136309095272378209743220542356611471082313414926805855531557475401967957903 Zeit: 4.809 s ---------- |
Mathematiker - Mi 02.08.17 15:26
Hallo Horst,
Danke für deine Verbesserung.
Leider komme ich erst morgen nachmittag an meinen Rechner 'ran.
Ich werde es dann sofort ausprobieren.
Steffen
Mathematiker - Do 03.08.17 12:46
Hallo Horst,
vielen Dank für deine neuerlicher Verbesserung des Programms.
Es wird mir immer rätselhafter, wie du immer wieder noch mehr aus einem Algorithmus herausholen kannst. Einfach sensationell.
Ich habe das Programm getestet und es war bei mir wieder eine Sekunde für die Startzahl aus den vielen Einsen.
Noch besser wurde es bei der 200stelligen Startzahl 10^199.
Danach habe ich deine Lösung unter dem aktuellen Lazarus als 64bit-Programm kompiliert und war überrascht.
Bei meinem Win8 braucht das Programm nur noch 144 Sekunden für 10^199, im Gegensatz zu den mehr als 200 s im 32bit-Fall. Ob das auch bei anderen so ist, weiß ich nicht.
Ich hänge hier das Lazarus-Projekt an. Hoffentlich habe ich alle notwendigen Dateien im ZIP-File.
Nochmals Danke
Steffen
Horst_H - Do 03.08.17 13:35
Hallo,
wie oben schon einmal bemerkt, mparith von
Gammatester wird mit 64-Bit auch fast doppelt so schnell.
Ich habe gerade das Sieb geändert und auf eine Länge von 2*3*5*7*...*17 = 510510 gebracht.
Das dann wie beim wheel-sieving genutzt werden kann.Alle 510510 wiederholen sich die Streichungen für Primzaheln von 2..17.
Das Feld berechnen ich nur einmal und kopiere es beim Sieben in zahl[] und siebe dann ab 19.
Ich dachte zuerst, ich müsste auch erst den Übertrag des Feldes in die riesige Zahl berechnen.Tut aber nicht nötig, denn es ist ein Rad und wo ich beginne ist Wurst-egal, die Runde bleibt gleich lang, solange die Groesse von Zahl ist ein Vielfaches davon ist, kein Problem.
Wie Du Dir denken kannst bringt das nichts :-(
Quelltext
1: 2: 3:
| = 463 * 2399808015358771298296136309095272378209743220542356611471082313414926805855531557475401967957903 Anzahl Siebungen 105 Zeit: 00:00:02.314 |
Die Prüfung der Zahlen ist der Verbrecher ;-)
Es wäre zu überlegen, die Anzahl der Siebprimzahlen zu erhöhen, je länger die Zahlen werden.
Auf 10^199 habe ich nicht warten wollen...
Gruß Horst
hydemarie - Do 03.08.17 14:25
Mathematiker hat folgendes geschrieben : |
PS: Es wäre nicht schön, wenn so ein "komisches" C-Programm unser geliebtes Delphi schlägt. :wink: |
Schreib's doch in Inline-ASM. 8)
(Allerdings: In puncto Geschwindigkeit wird's wohl schwierig, hochoptimierte C++-Compiler davon abzuhalten, die neuesten fiesen CPU-Funktionen auszunutzen.)
32-Bit-ASM auf 64 Bit zu portieren ist jetzt aber kein allzu gewaltiges Problem, wenn das Programm hinterher nicht allzu viel können muss. Die Register heißen nur anders und einige Zahlen sehen anders aus. (Das ist jetzt etwas vereinfacht ausgedrückt.)
Horst_H - Do 03.08.17 14:56
Hallo,
die Crux an diesem Problem ist, dass man nicht einfach nur ausstreichen muss, wie bei einem Primzahlsieb, sondern zählen muss.Die Treffer durch Primzahlen zählen muss.Die gesuchten Quadrupel sind eben keine Primzahlquadrupel, da gibt es viel mehr zu testen.
Am Ende steht und fällt es mit den Langzahltest auf prim.
Bei der Beispielzahl des Programmes sind es bis zur Erreichung der Lösung nur etwa 11000 Langzahl-Divisionen und -Primtests(, bie 500.000 Testprimzahlen.
Gruß Horst
P.S:
Einmal mit 16.777.215 Primzahlen( mehr geht so einfach nicht ) im 2*3*..*17*19 (=9.699.690 ) grossen Sieb gesucht:
Alleine die Zeit bis zur ersten Anzeige( Erstellung der Primzahlen, erstes Sieb (0.2 s) ) war 6s und paar gequetschte.
Zeit bis zur Lösung bei [99x]1_0 fast 5000 weniger Langzahltests.
und für [198x1]_0 // war über 7min20smit 5 Mio Primzahlen.
Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26:
| 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111164509081 = 43 * 25839793281653746770025839793281653746770025839793281653746770025839793281653746770025839794523467 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111164509083 = 1291 * 860659264996987692572510543075996213099234013254152680953610465616662363370341681728203804155313 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111164509087 = 7 * 158730158730158730158730158730158730158730158730158730158730158730158730158730158730158730166358441 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111164509089 = 463 * 2399808015358771298296136309095272378209743220542356611471082313414926805855531557475401967957903 Zeit: 00:00:07.963 Anzahl Siebungen 6 Anzahl Langtests 6094 TestBereich 58198140 ---------- 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111114621127981 = 113 * 9832841691248770894788593903638151425762045231071779744346116027531956735496558505408062930186823992133726647000983284169124877089478859390363815142576204523107177974434611602753195673549686912637 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111114621127983 = 11 * 101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101329193453 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111114621127987 = 37 * 30030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030124895351 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111114621127989 = 193 * 5757052389176741508347725964306275187104202648244099021301093839953943580886586067933218192285549798503166378814047207829591249280368451352907311456534254461715601611974668969487622337363288192373 Zeit: 00:06:41.681 Anzahl Siebungen 362 Anzahl Langtests 377211 TestBereich 3511287780 ---------- |
Gammatester - Do 03.08.17 15:50
hydemarie hat folgendes geschrieben : |
32-Bit-ASM auf 64 Bit zu portieren ist jetzt aber kein allzu gewaltiges Problem, wenn das Programm hinterher nicht allzu viel können muss. Die Register heißen nur anders und einige Zahlen sehen anders aus. (Das ist jetzt etwas vereinfacht ausgedrückt.) |
Das Umschreiben auf 64-Bit-Assembler ist das kleinste Problem.
Das Hauptproblem, die zitierte Funktion 64-bittig zu machen, ist daß der Algorithmus geändert werden. Für 32-Bit-Tests reichen halt drei starke Pseudoprimzahltests mit den Basen 2,7,61, aber nicht für 64-Bit. Für n < 341550071728321 ~ 2^48 reichen SPSP mit 2, 3, 5, 7, 11, 13 und 17, siehe
http://primes.utm.edu/prove/prove2_3.html ).
Durch komplettes Nachrechnen habe einige Leute rausgefunden, daß für 64-Bit
ein BPSW-Test reicht (das ist der gleiche Test, den mein
mp_ispprime genutzt), nur ist der nicht mehr so billig zu haben. (Eine Liste von SPSP brauchte CPU-Jahre zum Berechnen,
http://www.janfeitsma.nl/math/psp2/index,
Many CPU years have been spent on the computating facilities of the University of Groningen). Mit dieser Liste wurde BPSW-64 verifiziert. Eine 64-Bit-C-Implementation findet man hier:
http://www.trnicely.net/misc/bpsw.html. Wenn Du genau hinsieht, entdeckst Du, daß dort ein SPSP-2 gemacht wird.
Im Kontext sind allerdings die kleinen Primzahltests hier völlig irrelevant und werden entweder durch prime_sieve_next oder is_prime32 erschlagen; und wie es aussieht, ist das Suchen nach nach wesentlich größeren Teilern als ein paar Millionen sogar kontraproduktiv (für die Geschwindigkeit).
Gruß Gammatester
Gammatester - Do 03.08.17 16:39
Horst_H hat folgendes geschrieben : |
Hallo,
die Crux an diesem Problem ist, dass man nicht einfach nur ausstreichen muss, wie bei einem Primzahlsieb, sondern zählen muss.Die Treffer durch Primzahlen zählen muss.Die gesuchten Quadrupel sind eben keine Primzahlquadrupel, da gibt es viel mehr zu testen.
Am Ende steht und fällt es mit den Langzahltest auf prim. |
Nicht unbedingt: Die Fermat-Tests und die vertrackte Logik sind die Bremsen. Ich denke, daß man Deine Methode noch ein wenig aufbohren könnte: Ist ein kleiner kleiner Teiler gefunden, wird sofort der Fermattest gemacht, der aber (hoffentlich) fehlschlägt, wenn m3 einen Teiler hat, der >= dem gefundenen kleinen kleinen Teiler ist. Also könnte man auch m3 nochmal mit kleinen Teilern bearbeiten, damit ein Fermattest nicht unnötig gemacht werden muß. Allerdings ist dies keine garantierte Verbesserung, sondern hängt von der Primfaktorzerlegung der großem Quadrupel ab.
Besonders blöd wäre es, wenn bei der vierten Quadrupelzahl zwei kleine Teiler gefunden würden, die dann drei Fermattests in die Tonne treten. Irgendwie müßte alle vier Quadrupelzahlel simultan sieben bzw. nach kleinen Faktoren durchsuchen.
Edit: Ich sehe gerade, daß dieser Beitrag vielleicht teilweise überholt ist durch die Darstellung in
http://matheplanet.com/matheplanet/nuke/html/viewtopic.php?rd2&topic=230154&start=40#p1677261 .
Horst_H - Do 03.08.17 21:33
Hallo,
Ich wollte die Zeit für einen Langzahltest abschätzen, eigentlich die Division /TeilerX und anschliessendem Primtest.+ und - braucht keine Zeit dagegen.
ich habe mal kleine Experimente gemacht mit einer Zahl mit 150 Stellen und dabei die Anzahl der Siebprimzahlen und zum Ende die Größe des Siebes verzehnfacht.
Es lohnt sich bei so hohen Stellenzahlen viele Primzahlen zu nutzen.
Wenn das Feld ohnehin nicht mehr in den CPU Cache passt , kann man es noch größer machen.
Die Primzahlen sind ja schon ab 664579 ? ( da war mal was ) im Bereich von Bereich 10 Mio ~ Siebgröße, die streichen nur jedes 2.te mal, meist wird nur der Übertrag um eine Sieblänge korrigiert, deshalb steigt Siebzeit nur sehr gering.
Von 0,8s -> 1s für 1,5 Mio -> 16.8 Mio Primzahlen. // ~11x
Die Laufzeit sinkt von 2m40s auf 1m48, das ist nicht wenig.
Weil der Langzahltest überproportional mit der Stellenzahl zeitaufwändiger wird, braucht es noch mehr Primzahlen.
Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41: 42: 43: 44: 45: 46: 47: 48: 49: 50: 51: 52: 53: 54: 55: 56: 57: 58:
| Groesse Sieb = 2*3*5*7*....*17*19 = 9.699.690 ~40 Mb Testzahl '1' gefolgt von 149x'0' ---------- 1.....01824150031 = 71 * 140845....39776761 1.....01824150033 = 61 * 163934....43018853 1.....01824150037 = 2767 * 3614....26318811 1.....01824150039 = 23 * 434782....66267393 Zeit: 00:02:40.802 Anzahl Siebungen 200 Anzahl Langtests 364418 Anzahl TestBereich 1833241410 // 500.000 Primzahlen ---------- Zeit zum vorsieben 00:00:00.082 Zeit zum 10x Sieben 00:00:00.811 = 71 * 1408.. = 61 * 1639.. = 2767 * 36.. = 23 * 4347.. Zeit: 00:02:15.972 -> 135,972 - 16,22 => 119,752 / 297804 == 402 µs / Langtest Anzahl Siebungen 200 -> 16,22 s Anzahl Langtests 297804 Anzahl TestBereich 1833241410 //1.500.000 Primzahlen
Zeit zum vorsieben 00:00:00.124 Zeit zum 10x Sieben 00:00:00.843 = 71 * 1408.. = 61 * 1639.. = 2767 * 36.. = 23 * 4347.. Zeit: 00:02:07.192 -> 127,192-16,86 s =110,332 -> 405 µs /Langtest Anzahl Siebungen 200 -> 16,86s Anzahl Langtests 272081 Anzahl TestBereich 1833241410 //2.500.000 Primzahlen
Zeit zum vorsieben 00:00:00.230 // Primzahlen Suche langsam Zeit zum 10x Sieben 00:00:00.887 = 71 * 1408.. = 61 * 1639.. = 2767 * 36.. = 23 * 4347.. Zeit: 00:01:59.447 = 119,447-17,74-0.230 = 101,477s/ 242129 = 419 µs Anzahl Siebungen 200 -> 17,74 Anzahl Langtests 242129 Anzahl TestBereich 1833241410 //5.000.000 Primzahlen
Zeit zum vorsieben 00:00:00.737 // Primzahlensuche langsam Zeit zum 10x Sieben 00:00:01.049 = 71 * 1408.. = 61 * 1639.. = 2767 * 36.. = 23 * 4347.. Zeit: 00:01:55.149 = 115,149-20,98-0,737 = 93,432s/ 199546 = 468 µs /Langzahltest Anzahl Siebungen 200 -> 20,98s Anzahl Langtests 199546 Anzahl TestBereich 1833241410 //16.777.215 Primzahlen ( 1 shl 24 -1) ---------- Jetzt Sieb 10x ---------- 10x Sieb - >10* 2*3*5...*17*19 = 96.996.900 x4Byte ~ 400 Mb Zeit zum vorsieben 00:00:00.966 // Vorsieb ist auch 400 Mb Zeit zum 10x Sieben 00:00:09.520 = 71 * 1408.. = 61 * 1639.. = 2767 * 36.. = 23 * 4347.. Zeit: 00:01:48.360 0 108,36s- 19,046-0,966 = 88,348s => 443 µs Anzahl Siebungen 20 sein -> 19,046s Anzahl Langtests 199546 Anzahl TestBereich 1842941100 //16.777.215 Primzahlen ( 1 shl 24 -1)
Bei 200 Stellen dauert ein Lanzahltest etwa 920 µs Bei 250 Stellen dauert ein Lanzahltest etwa 1650 µs, die habe ich nur einmal gemessen ;-) |
Stellenzahl ^ n = Laufzeit passt nicht, der Exponent steigt von 1,19..(150)--> 1,34..(250)
n ^ Stellenzahl = Laufzeit passt auch nicht n =1.04--> 1.03
nicht übel ist
n^ sqrt(Stellenzahl) = Laufzeit n = 1,63 -> 1,597
Blödes rumgerate ....
Da kann man besser mit einem Programmschnipsel der nur eine Primzahl der Größe testet abschätzen.
Lange Rede, keinen Sinn es dauert lange....
Wie das HyperG auf matheplanet geschafft hat ?
Zitat: |
So, mit 13 parallelen Prozessen und 3,8 Stunden später
habe ich eine 410 stellige Zahl gefunden! |
Wie kommt man auf 410 Stellen ? Grob umgerechnet 49,4 h
1,6^(sqrt(410)) -> etwa 13,6 ms pro Test ( ~ 34x von 150 Stellen ), sieben wird nicht teuerer.
-> 73,6 Test/s ->13.089.024 Tests
13 MIo/200000 = 65x 1842941100 bei etwa +119*1e9 da müsste das Quadrupel aufgetaucht sein.
Das müsste
Mathematiker in Erfahrung bringen können.
Natürlich kann man parallel sieben lassen, dann müssten die Überträge seperat geführt werden.
Und ab und an neu berechnen, wenn man jeden Thread 10 Sieb-Abstand gibt.eben alle 10x .
Oder aber man siebt und sammelt die möglichen Quadrupel, aka merkt sich die Position j im Sieb/zahl.
Das dauert ja nur einen Wimperschlag.Dazu braucht es ein m0 als Startzahl des Siebes, das alle threads nutzen können.
Die verteilt man dann auf die n-Threads und gut ist.Im großen Sieb waren das 10000.Da sind die schon gut beschäftigt ;-)
Gruß Horst
Gammatester - Do 03.08.17 22:21
Horst_H hat folgendes geschrieben : |
Bei 200 Stellen dauert ein Lanzahltest etwa 920 µs
Bei 250 Stellen dauert ein Lanzahltest etwa 1650 µs, die habe ich nur einmal gemessen ;-)
Stellenzahl ^ n = Laufzeit passt nicht, der Exponent steigt von 1,19..(150)--> 1,34..(250)
n ^ Stellenzahl = Laufzeit passt auch nicht n =1.04--> 1.03
nicht übel ist
n^ sqrt(Stellenzahl) = Laufzeit n = 1,63 -> 1,597
Blödes rumgerate ....
|
Beim Fermattest für eine Zahl mit n Bits werden n Quadrierungen, n Montgomery-Reduktionen und durchschnittlich n/2 Shifts+Addition benötigt. Wenn man sehr vereinfacht annimmt, daß man sich dauernd im Karatsuba-Bereich befindet, sollten die Zeiten ungefähr wie a*bitsize^1.59 bzw. b*Stellenzahl^1.59 skalieren.
Horst_H - Do 03.08.17 23:27
Hallo,
das ist ja mal ein Anhaltspunkt.Wobei natürlich der Test nicht immer ganz durchläuft, wenn nicht-prim festgestellt ist.
Ich habe die Zeiten nur für sieben gemessen um feststellen, ob ein mögliches fast primes Quadrupel vorliegt.Komplett ohne mp_inc / copy und div ausser bei der erstmaligen Bestimmung der Überträge ins Sieb.Wer hätte gedacht das nur mp_inc(m1), m4 und das ein copy schon 10% == 0.2 Sekunden ausmachen.
Das kann man im Programm über j/j4 auch regeln und nur bei Bedarf rechnen.Ob ich 145Mio 1 raufzähle oder nur 20000 mal ein longInt mp_add mache, sollte man merken.
Die Laufzeiten sind für alle Stellenzahlen, wie erwartet konstant mit 2s.
Auch die Anzahl der zu testenden Quadrupel in einem Bereich ist auch sehr konstant.
Da gibt es keine Abnahme, bedingt durch begrenzte Anahl an Siebprimzahlen.
Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23:
| Stellenzahl 50 Zeit: Vorsieben 00:00:03.586 // für 1 shl 24 -1 Primzahlen und Bestimmung der Überträge Zeit: Sieben 00:00:02.001 // Zeit für sieben und finden(zählen) Anzahl Siebungen 15 Anzahl Testquadr 20358 Anzahl Langtests 0 TestBereich 145495350 ---------- Stellenzahl 150 Zeit: Vorsieben 00:00:08.611 Zeit: Sieben 00:00:01.988 Anzahl Siebungen 15 Anzahl Testquadr 20561 Anzahl Langtests 0 TestBereich 145495350 ---------- Stellenzahl 450 Zeit: Vorsieben 00:00:24.994 Zeit: Sieben 00:00:01.988 Anzahl Siebungen 15 Anzahl Testquadr 20352 Anzahl Langtests 0 TestBereich 145495350 |
Also sind es 10000 Quadruple/Sekunde, die es zu testen gilt.
Bei 13,6 ms Zeit/Quadruple ( geraten für 410 Stellen ) wären dazu 136 threads nötig :D
Nicht wirklich mein Rechner.
Bei 100 Stellen reichen vier Threads zum testen und einer zum sieben.
Vielleicht ist gmp viel schneller beim Test auf prim?
Gruß Horst
Gammatester - Do 03.08.17 23:52
Horst_H hat folgendes geschrieben : |
Vielleicht ist gmp viel schneller beim Test auf prim?
Gruß Horst |
Glaube ich nicht, jedenfalls nicht für den Bereich um 200-400 Stellen und den Standard-Primtest:
This function performs some trial divisions, then reps Miller-Rabin probabilistic primality tests. Wobei die MR-Tests mit Zufallsbasen gemacht wird. Wenn GMP, dann solltest Du einfach testen, ob
2^(m3-1) = 1 mod m3 ist.
Natürlich ist GMP schneller als MPArith, die Skalierung sollte aber ähnlich sein. Wäre schon interessant zu wissen, um wie viel schneller.
Mathematiker - Fr 04.08.17 07:19
Hallo,
als ich heute früh aufgestanden bin, hatte ich eine "Eingebung". Ich weiß, dann sollte man schnellsten zum Arzt gehen. :wink:
Ich habe beim Erzeugen der Primzahlen in deren Liste jetzt ein paar Primzahlquadrate aufgenommen.
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19:
| const quadratzahl = 13; quadrate : array[1..13] of integer = (9,27,81,3*3*3*3,49,7*7*7,121,169,289,361,23*23,29*29,31*31); begin ... for i:=1 to quadratzahl do begin mp_mod_int(m4, quadrate[i], rest); mp_mod_int(m4, 2 * quadrate[i], rest2); with primzahlen[i+1] do begin prPrimZ := quadrate[i]; if (rest <> rest2) then prUebertrag := 2 * prPrimZ - rest else prUebertrag := prPrimZ - rest; end; end; ... end; |
Damit werden auch alle Zahlen ausgesiebt, die z.B. zwei kleine Primfaktoren 3 haben, usw.
Das Ergebnis war für mich überraschend.
Statt 4,1 s bei der Startzahl sind es jetzt noch 3,2 s; also doch etwas Gewinn. Ob man dies noch ausbauen kann, weiß ich nicht.
Steffen
Nachtrag: Beim Experimentieren ist mir aufgefallen, dass ein maximaler kleiner Teiler (jetzt 1000000) bei großen Startzahlen jetzt besser ist. Begründen kann ich es nicht.
Für die Startzahl 10^199 sind es dann nur noch 70 s. Nicht schlecht.
Horst_H - Fr 04.08.17 08:46
Hallo,
Zitat: |
Nachtrag: Beim Experimentieren ist mir aufgefallen, dass ein maximaler kleiner Teiler (jetzt 1000000) bei großen Startzahlen jetzt besser ist. Begründen kann ich es nicht. |
Der maximal kleine Teiler sollte am besten die größte Primzahl sein, mit der gesiebt wird.
Du erweiterst damit Anzahl der möglichen FastPrim-Quadrupel und scheinbar sind Zahlen, die schon von 999999 kleinen Primzahlen nicht getroffen wurden, auch öfter im zweiten Faktor prim.
Man könnte mal als Obergrenze die höchtse Siebprimzahl einsetzen.
Es geht auch andersherum, wenn man das Ziel schon kennt ;-)
Nimm mal des Testbeispiel mit 100 Stellen und schränke auf die Lösungsmenge ein:
untere Grenze 7, obere 1291.Das ist eine ganze Ecke schneller.
Ich vermute, die Anhebung der unteren Grenze wirkt noch viel stärker.
Gruß Horst
P.S.
Zitat: |
maximaler kleiner Teiler (jetzt 1000000) |
Ich dachte im Programm wäre es 1 Mio Primzahlen und nicht nur die < 1Mio
P.S.S
Bezüglich Deiner Eingebung, hatte ich jetzt gerade auch eine ( ich wohne neben einer katholischen Kirche, das hilft.Das Spaghetti-Monster ist in Deutschland gescheitert ;-) )...
Wir haben doch mal
Befreundete Zahlen [
https://www.entwickler-ecke.de/viewtopic.php?t=113350&postorder=asc&start=8] gesucht.
Dabei habe ich doch parallel beim Eintragen des Faktors auch die Potenz mitgeführt.
Hier brauchte es nur bis zur zweiten Potenz, um Fastprim auszuschliessen.
Aber wie bekomme ich dann die Anzahl bis zum ersten p^2 heraus?
Wenn ich also bei Startzahl mod p= r1 erhalte, müsste ich noch Startzahl mod (p*p)=r2 berechnen, um zu bestimmen, bei welcher Zahl ich auch durch p^2 teilen könnte.Dann wäre mein momentaner Faktor f= r2/r1.
Stimmt nicht ganz, denn wenn r2=r1 wäre f=1, aber ich starte ich schon mit p*p, ich lasse 1 mal gelten.
Wenn Faktor = 1 -> höherere Potenz , dann erhöhe ich mit jedem streichen den Faktor f und wenn er dann p ist bin ich wieder bei einer höheren Potenz von p angelangt und erhöhe dort die Anzahl Streichungen um 2 und beginne wieder bei 1.
Dann muss ich Vorsiebfeld ändern auf 2*3*3*5*7*7*11*11 = 533610 ( 2 und 5 interessieren hier ja nicht).
Bis zu welcher Primzahl lohnt sich der Aufwand?
Bei 997 würde alle 997 besser alle 2x997( gerade fallen weg )um 2 statt um 1 raufgezählt. Das ist ist im Abstand 2*997*997 ~ 2Mio , Bei einer Zahl 1e6 -> 1e12 , dass lohnt sicher nicht ;-)
Wenn mindestens einmal im Sieb ein Treffer mit 2 sein sollte, hätte mal ja ein Kriterium.
Bei großen Testzahlen kann sich das vielleicht auch weiter lohnen.
Ich habe mein Programm jetzt zerschossen...Mist....
Gammatester - Fr 04.08.17 09:23
Mathematiker hat folgendes geschrieben : |
Ich habe beim Erzeugen der Primzahlen in deren Liste jetzt ein paar Primzahlquadrate aufgenommen.
Delphi-Quelltext 1: 2: 3:
| const quadratzahl = 13; quadrate : array[1..13] of integer = (9,27,81,3*3*3*3,49,7*7*7,121,169,289,361,23*23,29*29,31*31); |
Damit werden auch alle Zahlen ausgesiebt, die z.B. zwei kleine Primfaktoren 3 haben, usw.
|
Wäre es nicht günstiger etwa folgende Liste zu verwenden:
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7:
| const quadratzahl = 15; quadrate : array[1..quadratzahl] of integer = (2*3, 3*7, 3*11, 3*13, 3*17, 7*7, 7*11, 7*13, 7*17, 11*11, 11*13, 11*17, 13*13, 13*17, 17*17); |
IMHO sind bei Dir die höheren Primzahlpotenzen 3^3,3^4,7^3 etc überflüssig, weil sie schon durch p^2 erschlagen werden (oder liege ich hier völlig falsch?).
Leider kann ich meinen Vorschlag nicht testen, da ich nicht auf dem aktuellsten Quellcode-Stand bin (habe in Dein Zip vom 1.8. Horst's Unit eingebaut und dort wieder (an vielleicht falscher Stelle) den Vorschlag. Das Programm scheint aber endlos zu laufen.
Mathematiker - Fr 04.08.17 10:04
Hallo Gammatester,
Gammatester hat folgendes geschrieben : |
Leider kann ich meinen Vorschlag nicht testen, da ich nicht auf dem aktuellsten Quellcode-Stand bin (habe in Dein Zip vom 1.8. Horst's Unit eingebaut und dort wieder (an vielleicht falscher Stelle) den Vorschlag. Das Programm scheint aber endlos zu laufen. |
Da sind mir jetzt schon 2. :(
Ich habe mir gerade meinen Text zerschossen, als ich ihn unter Delphi kompilieren wollte.
Ich melde mich, sobald ich es im Griff habe.
Steffen
Mathematiker - Fr 04.08.17 10:40
Hallo Gammatester,
im 1.Beitrag ist die aktuelle Delphi-Variante.
Ich musste erst einmal die Delphi und Lazarus-Dateien "entwirren". Ich sollte auch nicht 2 Projekte im gleichen Ordner halten. :autsch:
Zum Sieben mit den Quadratzahlen:
Wenn eine Testzahl z.B. zweimal den Primfaktor 3 hat, wird sie bisher im Feld nur einmal gestrichen und nach dem Siebvorgang hat sie den Streichwert 1 und ist ein Kandidat.
Das wollte ich verhindern.
Streichen mit höheren Potenzen ist Quatsch. Das war eine dumme Idee von mir.
Streichen mit Produkten zweier kleiner Primzahlen brauchen wir nicht, da ja mit jeder der kleinen gestrichen wird.
Im aktuellen Delphi-Text habe ich jetzt für die ersten 20 Primzahlen + die 3 das Streichen mit dem Quadrat drin.
Etwas schneller ist es schon.
Beste Grüße
Steffen
Gammatester - Fr 04.08.17 10:43
Horst_H hat folgendes geschrieben : |
Vielleicht ist gmp viel schneller beim Test auf prim? |
Da jetzt offensichtlich alle ihren Quellcode zerschossen habe, habe ich mal zwischendurch einen kleinen Speed-Test gemacht mit dem MPArith/64-Bit-Rechner
http://www.wolfgang-ehrhardt.de/mp_intro.html#t_calc und
Quelltext
1: 2:
| GP/PARI CALCULATOR Version 2.9.3 (released) amd64 running mingw (x86-64/GMP-6.1.2 kernel) 64-bit version |
Für den Bereich 10^400 ist GMP ca 2.1 mal schneller: 16ms vs. 34ms, für 10^1000 sind die Werte 3.3, 63ms, 213ms.
Dabei wurde in mp_calc die Test-Funktion belegt mit:
Delphi-Quelltext
1: 2: 3:
| _TEST: begin mp_set(r,ord(s_mp_is_psp2(v1)) and 1); end; |
Wenn der Algorithmus ausgereizt und 10^1000 realistisch ist, könnte man also noch einen Faktor 2-3 herausholen.
Gammatester - Fr 04.08.17 10:54
Mathematiker hat folgendes geschrieben : |
Zum Sieben mit den Quadratzahlen:
Wenn eine Testzahl z.B. zweimal den Primfaktor 3 hat, wird sie bisher im Feld nur einmal gestrichen und nach dem Siebvorgang hat sie den Streichwert 1 und ist ein Kandidat.
Das wollte ich verhindern.
Streichen mit höheren Potenzen ist Quatsch. Das war eine dumme Idee von mir.
Streichen mit Produkten zweier kleiner Primzahlen brauchen wir nicht, da ja mit jeder der kleinen gestrichen wird. |
Mach mich mal schlau: Ein Kandidat ist ein Zahl k*(großer Wert) mit k=kleiner Teiler und (kleiner Teiler) wird gesiebt? Wer hindert (großer Wert) daran noch einen kleinen Teiler >= k zu haben?
Mathematiker - Fr 04.08.17 11:01
Gammatester hat folgendes geschrieben : |
Mach mich mal schlau: Ein Kandidat ist ein Zahl k*(großer Wert) mit k=kleiner Teiler und (kleiner Teiler) wird gesiebt? Wer hindert (großer Wert) daran noch einen kleinen Teiler >= k zu haben? |
Niemand. Nur scheinbar, sonst wäre es ja nicht etwas schneller (oder habe ich einen bösen Denkfehler), gibt es hinreichend viele Kandidaten, die wohl z.B. zweimal durch 3 aber durch keine weitere kleine Primzahl < maximaler kleiner Teiler teilbar sind.
Anders kann ich es mir nicht erklären.
Steffen
Gammatester - Fr 04.08.17 11:29
Irgendetwas ist bei mir noch faul an Deinem letzten Quellcode: Sowohl D6 (auf zwei Rechnern) aus auch D25/Starter melden Exception: Class TSpinEdit not found. Sehr merkwürdig!
Horst_H - Fr 04.08.17 11:31
Hallo,
aus den Backup Dateien neu zusammen gefügt.
Ich habe ein SpinEdit eingbaut, um mir n[1..9] *50 Testzahlen zu erstellen.
Mit Quadrate kleiner Primzahlen werde ich nach dem WE mal testen, natürlich streichen die Quadrate kleiner Primzahlen ein Menge aus.
3*3 kommt sozusagen alle 18 vor ( 9 (18 ist gerade) 27 45 63, streicht also mehr als eine 19, OK da sind noch zusätzlich Treffer anderer Zahlen, aber alle 9x Primzahl werden erwischt und aussortiert.
Gruß Horst
Mathematiker - Fr 04.08.17 11:39
Gammatester hat folgendes geschrieben : |
Irgendetwas ist bei mir noch faul an Deinem letzten Quellcode: Sowohl D6 (auf zwei Rechnern) aus auch D25/Starter melden Exception: Class TSpinEdit not found. Sehr merkwürdig! |
Schau mal in die dfm-Datei.
Wenn dort noch Spinedit drin steht, bitte dieses Objekt löschen.
Steffen
Horst_H - Sa 05.08.17 17:21
Hallo,
apropos höhere Potenzen von Primzahlen.
Wer hindert einen daran, mit 3*3 7*7 ..11*11.. p*p zu sieben.
Man könnte normal sieben und anschliessend mit ein paar tausend Quadraten von ersten Primzahlen und
dort dann einfach nur eine 2 einzutragen.
Nix mit inc(Speicherstelle) Read-modify-write, bäh... ;-)
Alternativ diese Quadratprimzahlen in die Liste der Siebprimzahlen einfügen.Muss ja nicht sortiert sein, wenn es auch Cache-freundlicher wäre.Die Primzahl selbst erhöht mindestens auf eins und die Quadratzahl dann eben passend auf 2.
Das Vorsieb, mit dem man die zeitaufwändigen Primzahlstreichungen der kleinen Primzahlen einspart, macht schon ab 7 wenig Sinn. Denn alle 7*7= 49 wird ein Feld auf 2 gesetzt, da siebe ich doch lieber mit 13,17 , die viel dichter liegen.
Ich habe es umständlicher gemacht, indem ich von den ersten 167 Primzahhlen nicht nur den Übertrag ins Sieb sondern auch deren Quadrates bestimme.Die Differenz als Vielfaches/Multiplikator der Primzahl ist dann ein Zähler, nach p Schritten ist dann wieder eine Quadratzahl erreicht.
Das brachte auch schon etwas. Die 150-stellige Zahl '100...00' wird mit 5 Mio Siebprimzahlen in 1min 36 statt in 00:01:59.447 gefunden.
Gruß Horst
Horst_H - Mo 07.08.17 21:43
Hallo,
ich habe mal
Mathematiker's Rev 5 etwas modifiziert.
Um immer die passende Langzahl zu haben, werden zwei davon ständig aktualisiert.
Delphi-Quelltext
1: 2:
| mp_inc(m1); mp_inc(m4); |
Dabei gibt es noch die Int-Variablen j und j4, die auch den Index in zahl[..] merken.Deshalb berechne ich die Langzahl nur, wenn eine Testzahl vorliegt, eine Integer-Addition auf die Langzahl geht schnell und ist nur etwa alle 500 nötig.
Auch war eine Teiler von 5 Abfrage im Test auf Quadrupel drin, was einiges an Rechenzeit kostet
Delphi-Quelltext
1: 2: 3: 4: 5:
| mp_add_d(m1, 2, m1); mp_mod_int(m1, 5, rest); if rest = 0 then mp_add_d(m1, 2, m1); |
Das spart schon einiges.
Dann habe ich die Quadratzahlen von kleinen Primzahlen in ein Extra-Feld gepackt.
Zum Vergleich für 100 Stellen:
Die Original Delphi Win32-Exe unter wine 2.0 braucht bei mir:
mit Suche auf 1 min + fertig machen begrenzt:
Jetzt als Lazarus-Win32 Exe unter wine 2.0
Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10:
| 100 53397971 43, 1291, 7, 463 00:00:03.398 101 77526031 7, 3, 3769, 3 00:00:04.662 102 358907441 1481, 7, 359, 1699 00:00:20.449 103 118981061 9421, 7109, 6947, 7 00:00:07.031 104 99900031 19, 3, 37, 3 00:00:06.102 105 61471311 3, 7, 3, 37 00:00:04.189 106 22944281 7, 19, 47, 127 00:00:01.915 107 4261061 31, 7, 1031, 11 00:00:00.761 108 313530491 31, 11, 13, 19 00:00:21.028 Zeit: 01:09.975 |
Jetzt als Lazarus-Linux64.Endlich unter 2 Sekunden für 100-stellig :-)
Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18:
| 100 53397971 43, 1291, 7, 463 00:00:01.685 101 77526031 7, 3, 3769, 3 00:00:02.364 102 358907441 1481, 7, 359, 1699 00:00:10.356 103 118981061 9421, 7109, 6947, 7 00:00:03.539 104 99900031 19, 3, 37, 3 00:00:03.093 105 61471311 3, 7, 3, 37 00:00:02.075 106 22944281 7, 19, 47, 127 00:00:00.925 107 4261061 31, 7, 1031, 11 00:00:00.324 108 313530491 31, 11, 13, 19 00:00:10.424 109 18090611 109, 9463, 17, 563 00:00:00.796 110 20713731 3, 7, 3, 29 00:00:00.869 111 46265411 59, 809, 17, 1163 00:00:01.725 112 140371061 787, 2459, 11, 887 00:00:04.801 113 76378171 7, 3, 31, 3 00:00:02.756 114 137102771 19, 4129, 3739, 521 00:00:05.150 115 181983221 857, 17, 151, 11 00:00:06.984 116 624238811 43, 179, 19, 2789 00:00:23.886 Zeit: 01:21.959 |
Deutlich zu sehen, dass 64-Bit doppelt so schnell ist.
Warum aber die Win64-Version immer ~20% länger brauchen will sich mir nicht erschliessen.
Gruß Horst
[Edit]
Neue Version:
Nur ungerade Zahlen werden gesiebt.Diesmal für für sehr lange Zahlen optimiert.
Alleine das Vorbereiten des Zahlsiebes und die Berechnung der Überträge der 16.777.215 Primzahlen dauert 20 Sekunden bei mir.Dafür wird es insgesamt schneller:
Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12:
| Zuvor: 301 1557971731 4349, 11, 3847, 13 00:09:36.374 jetzt: 301 1557971731 4349, 11, 3847, 13 00:08:22.480 302 250233211 7, 97, 19, 152419 00:01:36.130 303 1800073801 303917, 79, 17, 43 00:09:55.318 304 4587564621 3923, 3, 269, 3 00:24:58.628 305 2078310421 47, 53, 5591, 13721 00:11:28.176 306 1530771211 79, 26029, 1423, 1381 00:08:38.098 307 1386249451 7, 849221, 11, 43 00:07:49.874 308 407647731 661, 3, 13, 3 00:02:31.984 309 4995074881 13, 43, 7, 1039 00:27:41.190 |
Gammatester - Mo 07.08.17 22:19
Horst_H hat folgendes geschrieben : |
Deutlich zu sehen, dass 64-Bit doppelt so schnell ist.
Warum aber die Win64-Version immer ~20% länger brauchen will sich mir nicht erschliessen. |
Das könnte zB am lahmen Default-Memory-Manager liegen, habe ich schon häufiger gesehen. Mit der aktuellen MPArith V1.35.07 habe ich bei mir den Effekt, daß die Zeiten für 500000! mit Default-MM 7.972s und mit cmem 7.158s, also ca 11% (reproduzierbar). Für FPC füge ich beim
uses im Hauptprogramm nur ein
Delphi-Quelltext
1: 2: 3:
| {$ifdef FPC} cmem, {$endif} |
Ich weiß allerdings nicht, ob es unter Lazarus möglich ist, den cmem-MM zu verwenden, da ich Laz nicht benutze.
Mathematiker - Mo 07.08.17 22:49
Hallo Horst,
Horst_H hat folgendes geschrieben : |
ich habe mal Mathematiker's Rev 5 etwas modifiziert.
...
Deutlich zu sehen, dass 64-Bit doppelt so schnell ist.
|
Wie machst du das? Langsam wird es mir umheimlich.
Für die Startzahl 10^199 braucht mein Rechner nur noch 60 s, also wieder deutlich schneller.
Ich werde mir alles genau ansehen und kann nur lernen.
Tiefe Verbeugung :flehan: und vielen Dank
Steffen
Horst_H - Do 10.08.17 08:53
Hallo,
Zitat: |
Ziel erreicht: 1000stellige SemiPrimeQuadrupel gefunden! |
http://matheplanet.com/matheplanet/nuke/html/viewtopic.php?rd2&topic=230154&start=40#p1677898
Eine wundersame und einfache Form, verschiedene Threads zu erzeugen, indem das Programm mit 40 unterschiedlichen Zahlen seperat startet.
Ich dachte daran, einfach ein Programm zu schreiben, dass die Testkandidaten als mp_int-startzahl zu Beginn und dann nur noch die Offsets als Int64, in eine Datei wegschreibt.
Denn fast egal, wie die Stellenzahl ist, etwa 20000 Kandidaten/s sind zu testen.
Diese Datei könnte dann von x-threads, die nur den Fermattest machen, beackert werden.Denn die Primzahlliste und das Sieb brauchen viel Platz und das x-mal macht die Sache nicht besser.Und nur Fermattest dürfte nicht viel Platz kosten, also innerhalb des CPU-Level-I-Cache laufen.
Da sind wir schon wieder bei GMP, wenn das doppelt so schnell testet.
Vielleicht fehlt mp-arith eine Funktion mp_int in gmp-mpz_ -Format zu wandeln.
Was soll's:
Zitat: |
Ziel erreicht: 1000stellige SemiPrimeQuadrupel gefunden! |
Dann sind wir damit durch ;-)
Gruß Horst
Gammatester - Do 10.08.17 12:19
Horst_H hat folgendes geschrieben : |
Vielleicht fehlt mp-arith eine Funktion mp_int in gmp-mpz_ -Format zu wandeln.
|
Die gibt es eigentlich schon: Kommunikation über Dezimal- oder Hex-Darstellung! :wink: Da beide Seiten binär arbeiten, ist speziell die Hex-Form interessant. Ich sehe keinen Sinn darin, daß MPArith eine Zahl direkt ins interne GMP-Format (für die aktuelle Konfiguration) umwandelt.
Horst_H - Do 10.08.17 13:08
Hallo,
fürwahr die Hex Darstellung ist ein gutes Übergabeformat, was sehr leicht umwandeln lässt.
Gruß Horst
Mathematiker - Do 10.08.17 18:27
Hallo Horst,
Horst_H hat folgendes geschrieben : |
Zitat: | Ziel erreicht: 1000stellige SemiPrimeQuadrupel gefunden! |
Dann sind wir damit durch ;-) |
Sind wir und der besondere Dank gilt dir für deine Superoptimierungen.
Ich lasse den Rechner noch etwas weiterrechnen, da ich für alle Startzahlen bis 10^1000 Quadrupel suchen will.
Das dauert noch etwas, aber läuft ja nur im Hintergrund.
Beste Grüße
Steffen
Horst_H - So 13.08.17 22:11
Hallo,
ich habe mich mit multithreading rumgeärgert.Wer A = BeginThread sagt, muss auch B = EndThread sagen ( 128 GB viertueller Speicher habe ich ja noch nie gesehen..)
Ich bin froh das
Mathematiker eine PDF Datein mit einer Tabelle der ersten 310 komplett ins Netzt gestellt hat.
3 Threads ( thdCnt = 3, sollte man viellecht per scrollbar einstellbar machen ) sind tatsächlich fast 3x schneller :D , vielleicht auch wegen cmem?
Quelltext
1: 2: 3: 4: 5:
| 300 492302551 13873, 694747, 827, 11 00:01:03.527 301 1557971731 4349, 11, 3847, 13 00:03:04.191 302 250233211 7, 97, 19, 152419 00:00:38.153 303 1800073801 303917, 79, 17, 43 00:03:36.680 304 4587564621 3923, 3, 269, 3 00:09:04.113// vorher 27 min |
cmem funktioniert, wenn man es in die Projekt - Datei .dpr vor interfaces packt und nicht, wie ich es versuchte, in die normale Unit.
Aber das ist Linux spezifisch.
Ich bin erstaunt, denn meine CPU hat nur 2 Kerne mit SMT, scheint doch ausgesprochen gut zu funktionieren.
Ich habe das mit threads, wie weiter oben beschrieben gemacht, also erst alle Kandidaten in eine Liste und dann prüfen lassen.
Mathematiker wollte ja bis 1000 Stellen alles testen, da könnte das etwas bringen,
Gruß Horst
[EDIT]
Apropos :CPU hat nur 2 Kerne mit SMT
bei 383 Stellen braucht das testen der Kandidaten einer Siebgröße mit 2 threads 54 Sekunden und mit 4 threads 51 Sekunden.
Da sieht man deutlich, das mehr threads als CPU-Kerne hier nicht wirklich lohnt.
Aber es dauert doch zum Teil sehr lange, auch mit 4 threads 1,5 h
Quelltext
1: 2: 3:
| 379 30999026611 77317, 23011, 7, 325153 01:36:46.778 ..oder mal schnell.. 383 744300811 7129, 23, 372803, 7 00:02:42.611 |
Mathematiker - So 13.08.17 22:34
Hallo Horst,
und erneut bin ich tief beeindruckt.
Horst_H hat folgendes geschrieben : |
ich habe mich mit multithreading rumgeärgert. |
Ich sehe es mir morgen sehr genau an und werde wohl wieder viel zum Lernen haben.
Vielen Dank
Steffen
OlafSt - Di 15.08.17 00:02
Das Hyperthreading (4 Threads auf 2 Kernen) bringt nur dann etwas, wenn auf den beiden physischen Kernen von den 4 Threads verschiedene Bereiche der CPU genutzt werden, z.B. ein Thread benutzt die ALU, der zweite Thread die FPU. Dann laufen diese beiden Threads tatsächlich parallel auf diesem einen CPU-Core.
Da hier aber alle Threads dieselben Bereiche der einzelnen CPU-Cores benutzen, bringt das genau gar nichts. Im Gegenteil, es müsste durch den Overhead des Multithreadings von 2*x Threads auf x Kernen sogar eine Spur langsamer sein, als mit x Threads auf x Kernen.
Es ist außerdem die Frage, ob die Bibliothek für diese enorm großen Zahlen auch threadsafe ist, sonst sind eure Ergebnisse evtl. falsch.
Horst_H - Di 15.08.17 07:30
Hallo,
ich weiß nicht, ob es threadsafe ist, aber die Ergebnisse mit den längsten Laufzeiten (bis 3h bei 2..4 threads ) stimmen.
Ja ich dachte auch SMT wäre sehr hinderlich und nahm mal nur 2 threads.Da steckt der Teufel im Detail.
Das Betriebssystem wechselt ab und an die CPU auf dem der thread läuft, bei 54 Sekunden Laufzeit der threads kommt das schon mal vor. Dummerweise benutzt es dabei die 4 logischen Kerne, also ab und an ( also 50:50 ) auf dem selben physikalischen Kern und brauchten die threads plötzlich 97s.
Man kann wohl die threads an Kerne binden, aber ich hatte jetzt keine Lust dazu, das Wie heraus zu finden, und mit 4 threads lief es konstant in 51 Sekunden ( bei 387 Stellen und ??? Lösungskandidaten, steht oben irgendwo )
Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41: 42: 43: 44: 45: 46: 47: 48: 49: 50: 51: 52: 53: 54: 55: 56: 57: 58: 59: 60: 61: 62: 63: 64: 65: 66: 67: 68: 69: 70: 71: 72: 73: 74: 75: 76: 77: 78: 79: 80: 81: 82: 83: 84: 85: 86: 87: 88: 89: 90: 91: 92: 93: 94:
| 310 6829816651 17 19 13 7 00:13:47.536 311 8672563641 32771 3 23 3 00:17:28.398 312 1196632831 7 173 41 297397 00:02:37.840 313 3577075021 1487 31 17 1657 00:07:23.219 314 1552863351 7 3 11 3 00:03:20.270 315 1731173191 53 43 7 456451 00:03:39.699 316 7789036631 3 13 3 17 00:16:04.655 317 1293664111 4229 118043 17 32009 00:02:49.689 318 4421143201 83 13 306167 70823 00:09:16.782 319 379099141 163 1361 31 293 00:00:58.497 320 1077897001 84307 97 17 503 00:02:26.936 321 266732401 7 14411 31 303529 00:00:43.551 322 3579133291 17 7 117503 13 00:07:53.516 323 406839271 173 6607 433 877 00:01:04.490 324 2470682971 47 4409 13 7 00:05:33.624 325 1360504141 257 1723 31247 223 00:03:08.113 326 753438931 6473 11923 31 47 00:01:49.741 327 2522373301 7129 11 337081 277 00:05:41.711 328 12710554381 19 101 7537 7 00:28:18.686 329 3377692841 3 223 3 41243 00:07:48.519 330 11671406551 37 7 14851 1741 00:26:43.830 331 2019134001 11287 3 65519 3 00:04:46.657 332 3411859471 533543 19 1913 43 00:08:02.532 333 1716096331 7 71 11 4243 00:04:10.306 334 3671628061 811 17 10987 2017 00:08:40.648 335 2960662591 59 20903 29 53 00:07:04.541 336 1712327341 410899 11 397 23 00:04:09.730 337 1930221001 53 17 103 173 00:04:44.619 338 3523723741 271 11 167 23 00:08:37.569 339 9699771181 31 109 157 13 00:23:36.797 340 4213608211 7 11 79 1031 00:10:28.885 341 8429248501 770239 197 13523 7 00:20:50.745 342 5968548751 13 19 517289 11131 00:14:56.310 343 6663542761 229 61 751 941 00:16:42.335 344 2161616371 1151 148549 7 239 00:05:34.687 345 348959941 1607 227 43 2909 00:01:05.127 346 5845745911 2963 23 136573 687061 00:14:53.270 347 1068546631 5653 37 19 84559 00:02:53.898 348 802685791 277 47 11 1499 00:02:14.465 349 10806706711 19 23 41 541 00:28:08.244 350 5050331641 967 3347 7 283 00:13:20.822 351 2129154751 89 7 78487 13 00:05:44.928 352 10671258691 198859 16139 7 244129 00:28:12.834 353 11928307951 11 6151 17 109 00:31:32.000 354 2150049641 3 17 3 264529 00:05:51.343 355 4309780261 827 13331 307823 263 00:11:33.736 356 2815760071 71 929 7 130477 00:07:41.966 357 2389735951 101 41 37 487 00:06:41.236 358 9837132721 599 37 127 41 00:27:07.692 359 8908659941 3 569 3 20029 00:24:44.814 360 4354219861 986351 713311 2377 59 00:12:14.941 361 9401736631 199 1951 7 6397 00:26:29.980 362 6564346381 752651 11 7 13 00:18:45.009 363 4635585421 7 23 31 2381 00:13:35.053 364 56972091 7 3 17 3 00:00:22.629 365 13842035011 31 853 23 11 00:39:29.264 366 895914631 21613 13249 7 13 00:02:46.324 367 142525501 7 11 26177 11681 00:00:36.584 368 1492888441 10883 7 1327 73 00:04:35.252 369 5441746261 60859 41 127 580303 00:16:06.237 370 4014172831 349963 229 2011 13 00:11:59.377 371 369923161 13 4483 919 21347 00:01:18.277 372 1624753561 733 185021 31 88681 00:04:59.141 373 154327561 948971 61 11777 19 00:00:39.456 374 5790998111 3 67 3 7 00:17:22.117 375 13956960661 199 179 991 61 00:42:18.048 376 2190540811 211 2111 6199 11059 00:07:00.570 377 9670222751 3 7507 3 11 00:29:37.381 378 1706225941 309403 7 331 42569 00:05:22.341 379 30999026611 77317 23011 7 325153 01:36:46.778 380 10343087851 43 268573 7 53 00:32:23.573 381 1288532611 43 13 71 593 00:04:11.303 382 8160019131 17 3 179 3 00:25:44.084 383 744300811 7129 23 372803 7 00:02:42.611 384 50640221281 11 5087 17 6389 03:04:11.541 385 9435147871 59 389 13 127 00:32:35.248 386 22052425381 251 139 60383 67 01:14:12.670 387 1122696751 109 5783 73 19 00:03:48.219 388 7966788431 3 59 3 7 00:27:02.082 389 12164917141 241 563 199 379 00:41:06.283 390 3867874651 804031 31 17 2053 00:12:52.925 391 696184471 157 12163 11 67 00:02:28.904 392 9211348231 59 17 4493 29 00:30:22.536 393 587329801 2267 103 29 18947 00:02:10.300 394 11544611671 19 11 13 41 00:38:49.645 395 5120524981 19 4643 4663 59 00:17:31.159 396 3046926091 39703 9887 23 13 00:10:34.664 397 7470846631 425233 241 37 690119 00:25:48.414 398 7373872681 182101 11 19 57397 00:25:41.418 399 3356559061 233 2521 13 113 00:11:51.837 400 609453511 28349 13781 7 367 00:02:22.690 401 2401690261 487 19 71 16561 00:08:34.277 402 221472831 911 3 29 3 00:00:59.231 403 13388267161 17 149 1061 131 00:47:12.809 |
Was enorm auffällt ist die enorme Zunahme der Laufzeit in Tests/s .
328 Stellen 7.48 Mio/s
375 Stellen 5.50 Mio/s
403 Stellen 4,73 Mio/s
1,22x Stellenzahl -> 1,58x Laufzeit (s/test), dass ist leicht überquadratisch ( 1,25^2 ).
Ein thread braucht keine 4kB für die Variablen bei 1000 Stellen und die Laufzeit ist von ms weit entfernt...
Nun denn, ich bin gespannt wann alle ersten fastprimen Quadrupel der Form 10^(k-1)+n bis 1000 Stellen gefunden sind,wie es
Mathematiker mal vorhatte.
Gruß Horst
Mathematiker - Mi 16.08.17 12:39
Hallo Horst,
ich habe jetzt alles eingebaut, ausprobiert aber natürlich nicht verstanden.
Die auf deinem Rechner erzielten Zeiten sind beeindruckend.
Leider klappt das bei mir unter Win8 überhaupt nicht.
Das neue Programm braucht für 10^99 nun 67 s, deine vorhergehende Lösung 2,0 s.
Irgendetwas mag Win8 offensichtlich nicht. Im Moment habe ich keine Idee, was es sein könnte.
Danke für deine Bemühungen
Steffen
Horst_H - Mi 16.08.17 15:26
Hallo,
Das macht alles nur Sinn ab 200 Stellen aufwärts.Dann laufen die threads für ein Sieb 10s statt 55s bei 400 Stellen. Bei 100 Stellen einem kleinem Sieb und 500000 primzahlen ist ein thread in den 20ms die bei der Erstellung dazwischen Zeit lasse schon komplett fertig.Vielleicht muss man bei Windows dort mehr Zeit lassen. ( Bei mir hatte ich auch plötzlich 16 threads , obwohl interlockedIncrement(thdCount) machte und bei 4 threads keine mehr erzeugen wollte. )
Das Programm sucht jetzt über einen "riesigen" Bereich.
3*3*5*7*11*13*17*19*10 das 145,5 mio ungerade Zahlen( deshalb öfter die 2*groesse ) a 4 Byte 581 Mb.
Es siebt mit den Primzahlen 3..19 und 3*3 vor, weil die am längsten zum Sieben brauchen.Also nochmals 581 Mb.
Dann 2^24-1 Primzahlen ( bis 307 Mio? ) a 8Byte -> 134 Mb
Bei mir dauert bis zum allerersten sieben über 20 Sekunden.Bei einer dann folgenden neunen Zahl 9s
Die Überträge zu berechnen ist ein zeitlich aufwendiges Unterfangen.
Dann die Checkliste also die möglichen Kandidaten, die das fastprime Quadrupel Kriterium einschliesslich Min und MaxTeiler erfüllen:
Delphi-Quelltext
1: 2: 3: 4: 5:
| tChkListItem = record clSiebNr, clOffset : LongWord; clquadTeil:tquadTeiler; end; |
Sind also nur 25000x24 = 6Mb
Zur Laufzeit wurden laut HTOP virtuell 1,6 Gb und tatsächlich 1,2 Gb
Ich erzeuge ja nun ständig threads und beende diese, statt sie wieder zu verwenden, was man mit der Klasse TThread wohl kann.
Vielleicht ist Windows bei der threaderstellung langsamer?
Ich kann ja mal später Win64 erstellen und laufen lassen ( dann Win7 oder wine )
Die Liste kannst Du ja mit den oben angegebenen testen und gegebenenfalls bis 403 Stellen ergänzen.
Für so kleine ;-) 100 Stellen müsste man groesse und genutzte Primzahlen anpassen, aber dann kann man nicht die Nacht durchlaufen lassen, weil es immer langsamer wird, gegenüber dieser Monster-Version
Gruß Horst
Mathematiker - Mi 16.08.17 16:17
Hallo Horst,
Danke für die Erklärung. Alles klar.
Ich habe meinen Rechner in Verdacht. Könnte es sein, dass die 6 GB Arbeitsspeicher zu wenig sind?
Beste Grüße
Steffen
Horst_H - Mi 16.08.17 18:52
Hallo,
jetzt mal für Win32 ( kann nur 3 GB ) kompiliert unter wine:
Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11:
| 200 292710691 509, 31, 3313, 159671 00:00:35.467 201 35078311 17, 57493, 11, 419 00:00:11.095 202 12830011 17183, 13, 2087, 423127 00:00:09.238 203 37811851 2081, 36563, 17, 4679 00:00:11.333 204 173238931 367, 56737, 2647, 17 00:00:23.733 205 181105241 3, 851231, 3, 2917 00:00:24.355 206 69468391 31, 19, 75931, 571 00:00:13.742 207 517728691 842077, 9137, 349, 7 00:00:55.993 208 899820511 17, 3037, 7, 887 00:01:41.153 209 105308761 37, 11, 3079, 5323 00:00:21.507 Zeit: 00:05:51.675 |
Mysteriös :-) selbst hier keine
Gruß Horst
Mathematiker - Mi 16.08.17 19:06
Hallo Horst,
ich habe die Ursache gefunden.
Deinen Text habe ich mit Lazarus 64bit kompiliert und dort läuft es extrem langsam.
Die von dir angehängte Delphi-Exe läuft etwa so schnell wie bei dir.
Beste Grüße
Steffen
Quelltext
1: 2: 3: 4: 5: 6: 7:
| 200 292710691 509, 31, 3313, 159671 00:00:46.523 201 35078311 17, 57493, 11, 419 00:00:13.016 202 12830011 17183, 13, 2087, 423127 00:00:10.669 203 37811851 2081, 36563, 17, 4679 00:00:13.455 204 173238931 367, 56737, 2647, 17 00:00:29.778 205 181105241 3, 851231, 3, 2917 00:00:30.880 206 69468391 31, 19, 75931, 571 00:00:17.055 |
Delphi-Laie - Mi 16.08.17 20:32
Mathematiker hat folgendes geschrieben : |
Ich habe meinen Rechner in Verdacht. Könnte es sein, dass die 6 GB Arbeitsspeicher zu wenig sind? |
Mit ziemlicher Sicherheit nicht. 6 GByte muß man erstmal füllen.
Der Taskmanager gibt über den Speicherbedarf ausreichend Auskunft.
Horst_H - Mi 16.08.17 21:26
Hallo,
wahrscheinlicher liegt es an der Compilereinstellungen
http://wiki.freepascal.org/Lazarus_Tutorial/de#Das_Untermen.C3.BC_Projekt dort Compilereinstellungen
Bei mir compilation and linking dort oben rechts 3 ( -O2 + blablabla )
Beim debugging habe ich den debugger abgeschaltet ( vierte Zeile) eund die Zeileninformation aus der exe entfernt, ganz unten ( -Xs )
Der Debugger hat bei Threading enorm viel Zeit gekostet.
Professioneller, wäre sicher die Nutzung von n-Threads, die man einmal erzeugt und dann nur immer neu startet.
Der Aufbau hier ist ja besonders simpel.Jeder Thread packt sich einen Kandidaten indem er den aktuellen Bearbeitungsindex TestThdIdx in die Liste threadsafe erhöht ( InterlockedIncrement ), damit die anderen Threads die Finger davon lassen, und dann das Element davor bearbeitet.
Diese threadvar sind die lokalen Variablen der Threads, die also jeder seine eigenen hat.
Hast Du,
Mathematiker, denn noch Ambitionen, bis 1000 komplett die Liste zu erstellen.
Dann mache es doch wie dem Collatz vermutung im Mathe-forum, der hat es bei BOINC machen lassen, aber das geht auch sicher hier.
Kannst ja Leute, die sich melden per PN Aufgaben-bereiche nennen. 800..819 oder so ähnlich.
Wenn ich daran denke das hyperG nur mal so
Zitat: |
Bei der 1000stelligen Zahl brachte einer der 40 Prozesse nach über 10,5 Stunden das Ergebnis. (in Summe wären das ohne die Parallelität fast 18 Tage) |
Natürlich macht es nur Sinn, wenn man keine bessere Idee für den Algorithmus hat, der alles erheblich beschleunigt.
Feierabend...
Gruß Horst
Mathematiker - Do 17.08.17 22:19
Hallo Horst,
Horst_H hat folgendes geschrieben : |
Hast Du, Mathematiker, denn noch Ambitionen, bis 1000 komplett die Liste zu erstellen. |
Eigentlich schon, nur bin ich im Moment "abgelenkt". :wink:
Durch deine Lösung, die Berechnungen auch in hohen Stellenzahlen möglich macht, habe ich mich an mein altes Problem erinnert, die Suche nach Primzahlvierlingen.
Ich habe deinen Text etwas verändert und wieder die Suche nach den kleinsten n-stelligen Primzahlvierlingen aufgenommen.
siehe
http://mathematikalpha.de/primzahlvierlinge
und
http://matheplanet.com/matheplanet/nuke/html/viewtopic.php?topic=230446&post_id=1678162
Diese Suche ist zwar mühevoller, aber hat mehr Sinn.
Horst_H hat folgendes geschrieben : |
Dann mache es doch wie dem Collatz vermutung im Mathe-forum, der hat es bei BOINC machen lassen, aber das geht auch sicher hier. |
Wäre schön, aber ich habe die Bemühungen bei der Collatz-Vermutung verfolgt und weiß, das übersteigt meine Fähigkeiten extrem.
Noch einmal ganz herzlichen Dank für deine Hilfe
Steffen
Nachtrag: Ich hänge die Lazarus-Quelltexte der Primzahlvierlingssuche an. Sie beruhen noch auf einer älteren Verbesserung von dir.
Horst_H - Fr 18.08.17 09:23
Hallo,
fastprim und prim und schon ein Unterschied.
Bei prim "ballert" man einfach Zahlen weg und zählt nicht die Treffer und merkt sich den letzten Täter.
Willst Du nicht einen neuen thread öffnen?
Gruß Horst
Gammatester - Fr 18.08.17 13:21
Hallo
Mathematiker,
Horst_H,
das mit dem Wegballern macht die Sache im Prinzip einfacher, aber ich denke, daß das Problem insgesamt viel schwieriger ist, weil die Dichte der Vierlinge im Bereich 10^n circa 1/(ln(10^n))^4 ist. Man muß also ca k=28*n^4 Kandidaten testen, bevor man einen Vierer hat, d.h
Quelltext
1: 2: 3:
| n=100 k = 2'811'012'357 n=200 k = 44'976'197'718 n=500 k = 1'756'882'723'368 |
Also ziemlich viel Arbeit :(
Edit: Allerdings bedeutet das selbstverständlich nicht, daß man immer so viel testen muß. Ich habe gerade die Tabelle (Formeln 3..9) auf
http://mathworld.wolfram.com/PrimeQuadruplet.html gesehen.
Horst_H - Fr 18.08.17 14:00
Hallo,
ich habe mal bis 4000 Kandidaten ( ohne anschliessenden test) für verschiedene Stellenzahlen zählen lassen.
Quelltext
1: 2: 3: 4:
| 100 816926830 200 805201750 400 832790860 < wundersam wenige 800 798116980 |
Man hätte mal bei fastprim einen Zähler einbauen sollen.Aber das sind sicher mehr
Bei fastprimen Zahlen muss man etwa 32..33 Mio abklappern,um 4000 Kandidaten zu finden.Auch bei 400 Stellen braucht es einen größeren Bereich.
Für prime Quadrupel ist man mit einem Abschnitt etwa einen Faktor (800/32) = 25 schneller durch.
Deshalb verstehe ich die angeblich lange Laufzeit nicht wirklich.
Zum Beispiel braucht fastprime Quadrupel für 403 Stellen (2 Cpu-Kerne mit 4 threads voll belastet )
Quelltext
1:
| 403 13388267161 17 149 1061 131 00:47:12.809 |
Das prime Quadrupel 10^399+ 34,99e9 müsste dann in 34,99/13,39 / 25 *47 min = 5 min fertig sein.
Natürlich müsste man die Siebzeit jetzt stärker berücksichtigen, aber es sind statt 47 Siebe ( * 2s) dann 120
Sagen wir 6min. Als 1 thread, ohne threads zu nutzen, also etwa 12 min
Gruß Horst
EDIT:
Dauert doch erheblich länger.Denn pro Sieb kommen nur um 800 Kandidaten zusammen, statt 20000+
Dabei hat das Sieb einen Bereich 2x(nur ungerade) 3*3*5*7*11*13*17*19*10 = 291 Mio Zahlen..
Sieben mit einem thread dauert fast solange wie testen mit 4 threads :-(
Wieder mit 2 Cpu Kernen und 4 Threads: Uff, es stimmt mit mathworld überein.
Quelltext
1:
| 400 34993836001 0, 0, 0, 0 00:13:21.804 |
Also am besten ein Bit-Sieb wie bei
Gammatester schon eingebaut. vielleicht sollte man das um quadrupel erweitern.
Noch ein Edit:
Wenn ich mit 32Mio statt 16.7 Mio Primzahlen sieben, wird es etwas schneller
Quelltext
1:
| 400 34993836001 0, 0, 0, 0 00:12:30.458 |
Mathematiker - Mi 23.08.17 17:10
Hallo,
im Ergebnis der Verbesserung des Programms durch
Horst_H läuft jetzt ein Projekt zur Suche nach den kleinsten n-stelligen Primzahlvierlingen, d.h. wir suchen für jede Stellenzahl n = 1, ..., 1000 einen Summanden a, so dass
10^{n-1}+a, 10^{n-1}+a+2, 10^{n-1}+a+6, 10^{n-1}+a+8 jeweils Primzahlen sind.
Im Moment sind außer Horst_H auch zwei vom Matroids Matheplaneten am "rechnen", natürlich ich auch.
Sollte jemand von euch mitmachen wollen, so gibt's unter
http://mathematikalpha.de/primzahlvierlinge ein kleines Programm und eine genauere Erklärung der Suche.
Bevor man mitmacht ist es aber ratsam, sich die aktuelle Liste der Vierlinge anzusehen, da regelmäßig neue Ergebnisse eingehen.
Außer einer lobenden Erwähnung gibt es aber leider nichts zu gewinnen.
Großes Ziel ist es bis zu 1000 Stellen zu kommen. Mehr wäre schön, aber leider steigt der Rechenaufwand immer mehr.
So eine Berechnung wurde bisher noch nicht durchgeführt. D.h., jeder, der einen neuen Wert findet, geht in die "Mathematikgeschichte" ein. :wink:
Beste Grüße und (vielleicht) erfolgreiches Suchen
Steffen
Gammatester - Fr 25.08.17 13:01
Hier ein Vierling bei 10^(620-1)+49370415361 etc. Noch mal separat mit mp_pprime
getestet.
Gruß Gammatester
Edit nach Horst's Beitrag: Noch ein paar Anregungen zum Programm. Wenn noch Zahlen offen, sind sollten diese sofort angezeigt werden, nicht erst nach
Suche. Und
wichtig: Bei großen Zahlen ist es mM besser, nicht ganze 20-er Blöcke zu bearbeiten, da man muß schon großes Glück haben. Ich habe gestern ohne Erfolg 620-639 bearbeitet, bis mir klar wurde, daß ich ca 20-mal schneller bin, wenn ich nur 620 beackere, habe dann Dein Programm ausgetrickst 8)
Edit 2
Horst_H: ich habe nur Anhalts-Punkte für die Zeit: Ich bin heute um ca 9:00 mit 620,7228500000 gestartet und vor ca 45 min fertig geworden. Vielleicht eine weitere Anregung für die nächste Programmversion.
Horst_H - Fr 25.08.17 13:12
Hallo,
da würde mich die Laufzeit interessieren.
Gerade eben auf i3-4330 3.5 Ghz in fast 12h fertig:
Quelltext
1:
| 553 1447073137021 11:53:33.600 |
Ich schätze um die 30 min == 12h *( 620/553)^2.2 ) * 49.37/1447
Gruß Horst
Mathematiker - Fr 25.08.17 14:02
Gammatester hat folgendes geschrieben : |
Hier ein Vierling bei 10^(620-1)+49370415361 etc. Noch mal separat mit mp_pprime
getestet. |
Danke. Ist schon in die Liste eingetragen.
Steffen
Horst_H - So 27.08.17 14:41
Hallo,
ein kleines Testprogramm, um GMP und mpArith zu vergleichen:
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41: 42: 43: 44: 45: 46: 47: 48: 49: 50: 51: 52: 53: 54: 55: 56: 57: 58: 59: 60: 61: 62: 63: 64: 65: 66: 67: 68: 69: 70: 71: 72: 73: 74: 75: 76: 77: 78: 79: 80: 81: 82: 83: 84: 85: 86: 87: 88: 89: 90: 91: 92: 93: 94: 95: 96: 97: 98: 99: 100: 101: 102: 103: 104: 105: 106: 107: 108: 109: 110: 111:
| program GMP_Test; {$IFNDEF FPC} {$Apptype CONSOLE} {$ELSE} {$MODE DELPHI} {$ENDIF}
uses sysutils,gmp,mp_base, mp_numth, mp_prng, mp_prime, mp_types; type tTestWerte = record twSZ, twVs : NativeUint; end; const cTestwerte : array[1..10] of tTestWerte = ((twSz: 100;twVs:2191), (twSz: 200;twVs:5491), (twSz: 300;twVs:4681), (twSz: 400;twVs:7081), (twSz: 500;twVs:15721), (twSz: 600;twVs:2161), (twSz: 700;twVs:20251), (twSz: 800;twVs:9511), (twSz: 900;twVs:6991), (twSz:1000;twVs:19411)); {$IFDEF CPU32} runden = 25; {$ENDIF} {$IFDEF CPU64} runden = 100; {$ENDIF} var x :mpz_t; y: mp_int;
procedure TestlaufMpArith(var TestZahl:mp_int); var T1,T0: TDateTime; i: integer; Begin t0:= time; For i := 1 to runden do s_mp_is_psp2(TestZahl); t1:= time; Writeln(86400*1000*(T1-T0)/runden:8:6,' ms'); end;
procedure TestlaufGMP(var TestZahl:mpz_t); var T1,T0: TDateTime; i: integer; Begin t0:= time; i := 1; For i := 1 to runden do mpz_probab_prime_p(TestZahl, 0); t1:= time; Writeln(86400*1000*(T1-T0)/runden:8:6,' ms'); end;
var i : integer; begin
mpz_init(x); writeln('GMP'); For i := low(cTestwerte) to High(cTestwerte) do Begin mpz_set_ui(x,10); with cTestwerte[i] do Begin mpz_pow_ui(x,x,twSz-1); mpz_add_ui(x,x,twVs); write(twSz:5,' '); end; TestlaufGMP(x); end; mpz_clear(x);
writeln; writeln('MpArith'); mp_init(y); For i := low(cTestwerte) to High(cTestwerte) do Begin mp_set(y, 10); with cTestwerte[i] do Begin mp_expt_int(y,twSz-1,y); mp_add_d(y,twVs,y); write(twSz:5,' '); end; TestlaufMpArith(y); end; mp_clear(y);
end. |
Laufzeit bei mir, während die Suche auf einem Thread weiterlief.
Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41: 42: 43: 44: 45: 46: 47: 48: 49: 50: 51:
| CPU64 # ./GMP_Test GMP 100 0.030000 ms 200 0.170000 ms 300 0.500000 ms 400 1.080000 ms 500 2.050000 ms 600 3.590000 ms 700 5.340000 ms 800 7.630000 ms 900 10.660000 ms 1000 14.320000 ms
MpArith 100 0.150000 ms 200 0.880000 ms 300 3.400000 ms 400 6.990000 ms 500 12.950000 ms 600 29.610000 ms 700 39.780000 ms 800 52.050000 ms 900 77.090000 ms 1000 104.640000 ms
CPU32 # ./GMP_Test GMP 100 0.120000 ms 200 0.880000 ms 300 2.760000 ms 400 5.920000 ms 500 10.720000 ms 600 18.560000 ms 700 28.560000 ms 800 33.480000 ms 900 50.280000 ms 1000 82.480000 ms
MpArith 100 0.440000 ms 200 3.000000 ms 300 10.720000 ms 400 22.400000 ms 500 40.600000 ms 600 184.160000 ms 700 215.800000 ms 800 278.840000 ms 900 554.600000 ms 1000 674.480000 ms |
Was bleibt gmp ist fast 7x schneller.
Statt 13 Stunden dann 2 ist doch ein Wort. 560 Stellen rödelt schon 16h bei 1.922e12.
Gruß Horst
EDIT: Programm geändert für 32-Bit
Mathematiker - So 27.08.17 14:49
Hallo Horst,
Horst_H hat folgendes geschrieben : |
Hallo,
Was bleibt gmp ist fast 7x schneller.
Statt 13 Stunden dann 2 ist doch ein Wort. 560 Stellen rödelt schon 16h bei 1.922e12.
|
Das ist hervorragend.
Mein Problem nun, wie komme ich an eine Exe zum Ausprobierenheran (64 Bit?).
Liebe Grüße
Steffen
Delphi-Laie - So 27.08.17 15:18
Horst_H hat folgendes geschrieben : |
ein kleines Testprogramm, um GMP und mpArith zu vergleichen: |
Wo gibt es "GMP"? Ist das frei verfügbar? Edit: Erledigt, da gefunden.
Mathematiker hat folgendes geschrieben : |
Mein Problem nun, wie komme ich an eine Exe zum Ausprobierenheran (64 Bit?). |
Welcher Quelltext?
Horst_H - So 27.08.17 16:00
Hallo,
das Programm "program GMP_Test;" 2 Antworten höher habe ich jetzt geändert, einfach mögliche Primzahlen suchen lassen.
Unter 32-Bit sind die Laufzeiten aber erheblich "schlechter", da ist ja nochmal ein Faktor 6 gegenüber 64-Bit drin.
Besonders auffällig ist der Sprung bei mparith bei CPU32 bei Stellenzahl 500-> 600 40->184 ms.
Die Laufzeiten sind ja fast proportional der Stellenzahl n^3 (1000/500 -> 82/10,7 = 2^2,94/ oder 104/12,95 = 2^ 3,03 )
Gruß Horst
Mathematiker - So 27.08.17 16:26
Hallo,
ich stelle mich wohl wieder zu doof an.
Ich bin auf der Seite https://gmplib.org/ und lade die Datei gmp-6.1.2.tar.lz herunter. Ob das für Delphi ist, weiß ich nicht, ist auch egal, da ich das Ding nicht entpacken kann, auch nicht mit dem 7-Zip-Dateimanager.
Und ohne gmp geht es nicht.
Beste Grüße
Steffen
Hast sich erledigt, ich bin eben doch zu doof. :autsch: :autsch:
Delphi-Laie - So 27.08.17 17:56
gmp-6.1.2.tar.bz2 läßt sich mit Winrar öffnen.
Allerdings ist das eine C-Bibliothek und mithin für mich uninteressant.
Oder wie handhabt Ihr diese Quelltexte?
Gammatester - Mo 28.08.17 11:18
Horst_H hat folgendes geschrieben : |
Besonders auffällig ist der Sprung bei mparith bei CPU32 bei Stellenzahl 500-> 600 40->184 ms.
Die Laufzeiten sind ja fast proportional der Stellenzahl n^3 (1000/500 -> 82/10,7 = 2^2,94/ oder 104/12,95 = 2^ 3,03 )
Gruß Horst |
Leider ist mein Netzwerk-Interface auf meinem I3 gestorben. Dies ist via Raspberry-Pi und eine elende Fummelei.
Der Sprung könnte beim Wechsel von Karatsuba auf Toom-3 verursacht werden.
Quelltext
1: 2: 3:
| 10^500 = 1661 Bits = 53 mp_digits 10^600 = 1994 Bits = 64 mp_digits; 10^1000 = 3322 Bits = 107 mp_digits |
Setz mal versuchsweise in mp_type die Toom-3 Schranken hoch, zB. von
Quelltext
1: 2:
| mp_t3m_cutoff := 2*mp_mul_cutoff; mp_t3s_cutoff := 2*mp_sqr_cutoff; |
auf
Quelltext
1: 2:
| mp_t3m_cutoff := 4*mp_mul_cutoff; mp_t3s_cutoff := 4*mp_sqr_cutoff; |
Gruß Gammatester
Gammatester - Mo 28.08.17 16:01
Gammatester hat folgendes geschrieben : |
Der Sprung könnte beim Wechsel von Karatsuba auf Toom-3 verursacht werden.
|
Horst_H, ich kann Deinen Sprung hier nicht nachvollziehen. Hier meine Werte fur den Test mit expt_mod auf i3/2.3 Ghz (Delphi 3 rechnet mit mp_digit bits 15/16, alle anderen mit mp_digit bits 31/32, FPC32/T=4K: FPC32 mit Toom3 = 4*Karatsuba).
Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11:
| D3/16 FPC32 D18/32 FPC64 FPC32/T=4K 100 1.342 1.938 2.459 1.093 1.950 200 6.541 6.042 7.057 4.074 5.551 300 17.410 14.102 20.856 7.424 14.079 400 39.333 28.126 45.369 14.153 28.101 500 77.455 52.632 86.937 24.796 52.558 600 128.781 95.760 150.708 48.929 98.861 700 199.945 142.172 227.475 69.307 147.441 800 293.470 205.109 336.141 98.148 210.664 900 424.481 327.736 476.608 170.889 287.117 1000 568.588 456.911 642.765 207.466 385.704 |
Für FPC32 scheint das Anheben der Toom-3-Grenze
etwas zu bringen.
Gruß Gammatester
Edit: Ich habe die Suche für 621 aufgegeben, nachdem nach tagelanger Suche die Suchlistenanzeige auf "1,-1" gesprungen ist (Programmversion vom 23.08. 07:20). Ist das ein bekanntes Problem?
Mathematiker - Mo 28.08.17 16:31
Hallo Gammatester,
Gammatester hat folgendes geschrieben : |
Ich habe die Suche für 621 aufgegeben, nachdem nach tagelanger Suche die Suchlistenanzeige auf "1,-1" gesprungen ist (Programmversion vom 23.08. 07:20). Ist das ein bekanntes Problem? |
Das ist neu. Im Moment kann ich mir den Grund noch nicht erklären, werde aber den Fehler suchen.
Unter
http://mathematikalpha.de/primzahlvierlinge habe ich eine neuere Variante, die aller drei Minuten den Stand unter suchliste_kopie.txt sicherheitshalber speichert.
Beste Grüße
Steffen
Horst_H - Di 29.08.17 11:22
Hallo,
ich versuche ja, das sieben zu beschleunigen, da ich den PrimzahlTest selbst nicht beschleunigen kann.
Und, wer hätte das gedacht, das geht auch ;-)
4e9 durchsiebt er bei mir in 1,5 Sekunden. ( Edit4 Freepascal Linux 64-Bit oder 32-Bit gleich )
Berechnung der nächsten Position stark vereinfacht, aber nicht unbedingt verständlicher.
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41: 42: 43: 44: 45: 46: 47: 48: 49: 50: 51: 52: 53: 54: 55: 56: 57: 58: 59: 60: 61: 62: 63: 64: 65: 66: 67: 68: 69: 70: 71: 72: 73: 74: 75: 76: 77: 78: 79: 80: 81: 82: 83: 84: 85: 86: 87: 88: 89: 90: 91: 92: 93: 94: 95: 96: 97: 98: 99: 100: 101: 102: 103: 104: 105: 106: 107: 108: 109: 110: 111: 112: 113: 114: 115: 116: 117: 118: 119: 120: 121: 122: 123: 124: 125: 126: 127: 128: 129: 130: 131: 132: 133: 134: 135: 136: 137: 138: 139: 140: 141: 142: 143: 144: 145: 146: 147: 148: 149: 150: 151: 152: 153: 154: 155: 156: 157: 158: 159: 160: 161: 162: 163: 164: 165: 166: 167: 168: 169: 170: 171: 172: 173: 174: 175: 176: 177: 178: 179: 180: 181: 182: 183: 184: 185: 186: 187: 188: 189: 190: 191: 192: 193: 194: 195: 196: 197: 198: 199: 200: 201: 202: 203: 204: 205: 206: 207: 208: 209: 210: 211: 212: 213: 214: 215: 216: 217: 218: 219: 220: 221: 222: 223: 224: 225: 226: 227: 228: 229: 230: 231: 232: 233: 234: 235: 236: 237: 238: 239: 240: 241: 242: 243: 244: 245: 246: 247: 248: 249: 250: 251: 252: 253: 254: 255: 256: 257: 258: 259: 260: 261: 262: 263: 264: 265: 266: 267: 268: 269: 270: 271: 272: 273: 274: 275: 276: 277: 278: 279: 280: 281: 282: 283: 284: 285: 286: 287: 288: 289: 290: 291: 292: 293: 294: 295: 296: 297: 298: 299: 300: 301: 302: 303: 304: 305: 306: 307: 308: 309: 310: 311: 312:
| program FindeQuadrupel;
{$IFDEF FPC} {$MODE DELPHI} {$OPTIMIZATION ON,REGVAR,CSE,PEEPHOLE} {$ELSE} {$APPTYPE CONSOLE} {$ENDIF} uses sysutils; type tSieveElem = NativeUint;
tDelta30 = array[0..3] of NativeUint; tMulOfs = record moMul,moOfs: byte; end; tMulPosArr = array[0..3] of tMulOfs;
tPrimMod30 =packed record pm30Offset : LongWord; pmNextSivbNr : word; pm30AktIdx, pm30Delta : byte; end; tpPrimMod30 = ^tPrimMod30;
const cMulOfs : array [0..7]of tMulPosArr = (((moMul: 2;moOfs:0),(moMul: 4;moOfs: 0),(moMul: 2;moOfs:0),(moMul:22;moOfs: 1)), ((moMul: 4;moOfs:1),(moMul: 8;moOfs: 2),(moMul: 4;moOfs:1),(moMul:14;moOfs: 3)), ((moMul: 6;moOfs:2),(moMul:16;moOfs: 6),(moMul: 6;moOfs:2),(moMul: 2;moOfs: 1)), ((moMul:12;moOfs:5),(moMul: 4;moOfs: 2),(moMul:12;moOfs:5),(moMul: 2;moOfs: 1)), ((moMul:12;moOfs:7),(moMul: 4;moOfs: 2),(moMul:12;moOfs:7),(moMul: 2;moOfs: 1)), ((moMul: 6;moOfs:4),(moMul:16;moOfs:10),(moMul: 6;moOfs:4),(moMul: 2;moOfs: 1)), ((moMul: 4;moOfs:3),(moMul: 8;moOfs: 6),(moMul: 4;moOfs:3),(moMul:14;moOfs:11)), ((moMul: 2;moOfs:2),(moMul: 4;moOfs: 4),(moMul: 2;moOfs:2),(moMul:22;moOfs:21))); cMod30ToIdx : array[0..29] of byte = (111,0,111,111,111,111,111,1,111,111,111,2,111,3,111, 111,111,4,111,5,111,111,111,6,111,111,111,111,111,7);
cIdxToMod30 : array[0..7] of byte = (1,7,11,13,17,19,23,29);
cBitSize = SizeOf(tSieveElem)*8; cAndMask = cBitSize-1;
cSiebGroesse = 64*30*130208; cPrimeMax =63245;var SiebMod30 : array[0..(cSiebGroesse-1) DIV 30 DIV cBitSize] of tSieveElem; Prim30List :array[0..11895200] of tPrimMod30; PrimSieb : array of boolean; T0,T1: TDAteTime; gblP30, Prim30idx, LastPrime : longWord;
tmpDelta30:tDelta30;
function Auszaehlen:Longint; var i:NativeUInt; elem:tSieveElem; begin result := 0; Begin For i := Low(SiebMod30) to High(SiebMod30)-1 do Begin elem := NOT SiebMod30[i]; repeat inc(result,elem AND 1); elem := elem shr 1; until elem = 0; end; elem := NOT SiebMod30[High(SiebMod30)]; i := High(SiebMod30)*30*cBitsize; while i < cSiebGroesse do Begin inc(result,elem AND 1); elem := elem shr 1; inc(i,30); end; end; end;
procedure MulListErstellen(p30:LongWord); var pMulPos : ^tMulOfs; begin pMulPos := @cMulOfs[p30 AND 7][0]; p30 := p30 shr 3; with pMulPos^ do tmpDelta30[0] := moOfs+p30*moMul; inc(pMulPos); with pMulPos^ do tmpDelta30[1] := moOfs+p30*moMul; inc(pMulPos); with pMulPos^ do tmpDelta30[2] := moOfs+p30*moMul; inc(pMulPos); with pMulPos^ do tmpDelta30[3] := moOfs+p30*moMul; end; procedure PrimSieben; var i,p: NativeInt; Begin p := 2; repeat i := p*p; while i <= cPrimeMax do Begin PrimSieb[i] := true; inc(i,p); end; repeat inc(p); until NOT PrimSieb[p] until (p*p) >cPrimeMax; end;
procedure PrimListeErstellen; var i: NativeInt; p30,p30Idx,DIV30,Aktidx,Last30Prime: NativeUInt; Begin T0 := now; setlength(PrimSieb,cPrimeMax+1); PrimSieben;
Prim30idx := 0; LastPrime := 1; Last30Prime := 0; For i := 7 to cPrimeMax do IF Not PrimSieb[i] then Begin DIV30 := i DIV 30; p30Idx := cMod30ToIdx[i-30*DIV30]; p30 := DIV30 shl 3+p30Idx; MulListErstellen(p30); IF cMulOfs[p30Idx][3].moMul = 2 then Begin inc(DIV30,tmpDelta30[0]); Aktidx:= 1 end else Begin DIV30:= tmpDelta30[3] shr 1; Aktidx:= 0; end; with Prim30List[Prim30idx] do Begin pm30Offset:= Div30; pm30Delta := p30-Last30Prime; pm30AktIdx:= Aktidx; end; inc(Prim30idx); if Prim30idx>High(Prim30List) then Begin BREAK; end; Last30Prime:= p30; LastPrime := i; end; dec(Prim30idx); setlength(PrimSieb,0); T1 := now; writeln('Anzahl Primzahlen ',Prim30idx,' Letzte PrimZahl ', lastPrime); Writeln('Laufzeit sieben',FormatDateTime('S.ZZZ',T1-T0)); end;
procedure EinmalSieben(var Prim30:tPrimMod30); var p30,mytmp,AktIdx: NativeUInt; begin with Prim30 do Begin MulListErstellen(gblP30); p30 := pm30Offset; AktIdx := pm30AktIdx; end; while p30 < cSiebGroesse DIV 30 do Begin mytmp := p30 DIV cBitSize; SiebMod30[mytmp]:= SiebMod30[mytmp] OR (tSieveElem(1) shl (p30 AND cAndMask)); inc(p30,tmpDelta30[AktIdx]); AktIdx := (AktIdx + 1) AND 3; end; with Prim30 do Begin pm30Offset:= p30-cSiebGroesse DIV 30; pm30AktIdx := AktIdx; end;
end;
function AlleSieben:longint; var pPL : tpPrimMod30; i,k,cnt : NativeInt;
begin k := 0; cnt := 0; repeat fillchar(SiebMod30,SizeOf(SiebMod30),0); i := 0; pPL := @Prim30List[0]; gblP30 := 0; repeat inc(gblP30,pPL^.pm30Delta); If pPL^.pm30Offset < cSiebGroesse DIV 30 then EinmalSieben(pPl^) else dec(pPl^.pm30Offset,cSiebGroesse DIV 30); inc(pPL); inc(i); until i > Prim30idx; inc(cnt,Auszaehlen); inc(k); until k >=8; result := cnt; end;
var cnt:NativeUInt; BEGIN PrimListeErstellen; cnt := AlleSieben;
writeln('Limit : ',cSiebGroesse); writeln('Suchfeldlimit : ',(High(SiebMod30)+1)*30*cBitSize); writeln('Anzahl : ',cnt); end. |
Jetzt muss nur noch eine clevere Lösung gefunden werden, dass für die Quadrupelsuche zu nutzen.
Die Platzersparnis für das Sieb ist ja enorm.Wenn man auf Bytebene bleibt ist es ein Faktor 30 auf Bitebene nochmals 8.
Bei 1MB levelII-Cache bei mir könnten da jetzt um 240 Mio Zahlen passen.
AMD-Rechner vor Ryzen sind leider im Speicherzugriff relativ lahm.Je "näher" an der CPU, desto besser.
Für jede Streichprimzahl mir auch noch OffsetMod30[0..3] und den momentanen Index [0..3] zu merken bläht die Primzahlliste auf, aber die wird ja sequentiell und damit schnell gelesen.
Vielleicht wieder holt sich das Muster wieder alle 30 0R1(=1),1R1(=31),2R1(=61)..30R1(=901)
Mal schauen
Gruß Horst
Edit:
Das Bitfeld ist jetzt implementiert.Jetzt fehlt die Berechnung der Überträge.
Edit2->3:
Die Uebtraege habe ich immer noch nicht.Aber ich kämpfe mit einer kompakten Speicherung der Siebprimzahlen.
Jetzt 8 Byte,weil ich die Differenz zum Vorgänger speichere.pm30Delta als Byte entspricht maximal 959 als Abstand.
Das ist irgendwo bei 1e15 der Fall...
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8:
| type tPrimMod30 =packed record pm30Offset : LongWord; pmNextSivbNr : word; pm30AktIdx, pm30Delta : byte; end; |
EDIT3: Es geht einfacher, siehe Programm.
Mathematiker - So 03.09.17 22:03
Hallo,
ich habe die Primzahlvierlingssuche jetzt auf 2 Threads aufgeteilt.
Der erste siebt jeweils einen Bereich von 500000 mit 10 Millionen Primzahlen vor und ermittelt die "Kandidaten" für einen Vierling, d.h. in dem Zehner dürfen die auf 1,3,7,9 endenden Zahlen nicht ausgesiebt sein.
Die Kandidaten werden über eine threadsichere Stringliste an den 2.Thread übergeben.
Dieser testet nun die 4 Zahlen eines Kandidaten auf Primzahleigenschaft und entfernt den getesteten Kandidaten aus der Stringliste.
Es funktioniert eigentlich ganz gut.
Leider ist der 2.Thread deutlich langsamer als der erste. Damit es nicht zu einem Stau in der Stringliste kommt, prüfe ich im ersten Thread mit
Delphi-Quelltext
1: 2:
| while liste.count>50 do begin end; |
die Listeneinträge und bremse den 1.Thread bei mehr als 50 Kandidaten.
Wichtig ist das vor allem, wenn die Berechnung abgebrochen wird, da dann erst alle Kandidaten abgearbeitet werden müssen, d.h. der Hauptthread wartet bis der 2. fertig ist.
Schön ist das nicht.
Meine Frage nun: Seht ihr eine andere Möglichkeit, beide Threads auf etwa gleiche Geschwindigkeit zu bringen? Gibt es eine andere Möglichkeit, den ersten Thread mit dem 2. zu synchonisieren?
Der angehängte Quelltext ist Lazarus-64-Bit. Diese Exen sind deutlich schneller als bei meinem Delphi 5.
Danke
Steffen
Nachtrag: Nach 19 min Laufzeit stürzt es jetzt auch noch ab. Warum? Ich weiß es nicht.
Nebenbei: Unsere kleine Gruppe, die erfolgreich nach Primzahlvierlingen sucht, benötigt noch Rechenleistung. Mitstreiter sind herzlich willkommen. :wink:
siehe:
http://matheplanet.com/matheplanet/nuke/html/viewtopic.php?topic=230446&start=120&lps=1680408#v1680408
bzw.
http://mathematikalpha.de/primzahlvierlinge
Delphi-Laie - Mo 04.09.17 01:48
Statt Polling mit der while-Schleife sind Botschaften auf der Sendeseite und deren ressourcenschonender Empfang mit Getmessage ratsam. So programmierte ich einige parallele Sortieralgorithmen.
Ansonsten kannst Du es mit vertauschter Reihenfolge der Threaderstellung und / oder mit Änderung ihrer versuchen.
Generell läßt sich Windows aber in bezug auf die Abarbeitung der Threads und Tasks kaum bis gar nicht hineinreden, und dementsprechend sind die Möglichkeit, da einzugreifen, äußerst begrenzt und nur "pseudo".
pzktupel - Mo 04.09.17 06:17
Hallo,
ich bin neu hier und habe mich mal hier angemeldet.
Durch eine Anfrage mit meinem kleinsten 1000-stelligen Primzahl-4-Tupel , hatte ich mir
2 Tage mühe gemacht um was zu programmieren, um bis n=999 alle zu finden.
Im Moment schafft mein Programm für jeden Exponenten in derselben Zeit ca. k= 300 000 000 000 / Stunde für 10^n + k abzusieben.... und das bei nur 1 Kern einer modernen CPU. Bei RYZEN wahrscheinlich bis 1 Billion pro Stunde.
Wollte ich nur mal erwähnen...
Gruß
cryptnex - Mo 04.09.17 11:55
pzktupel hat folgendes geschrieben : |
Durch eine Anfrage mit meinem kleinsten 1000-stelligen Primzahl-4-Tupel , hatte ich mir
2 Tage mühe gemacht um was zu programmieren, um bis n=999 alle zu finden.
Wollte ich nur mal erwähnen... |
Würdest Du den Quellcode zum Studieren hier veröffentlichen? Ich führe nur ungern Programme aus unbekannten Quellen auf meinem Rechner aus.
Viele Grüße
pzktupel - Mo 04.09.17 12:56
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.
Letzte Fassung:
FreeBASIC
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41: 42: 43: 44: 45: 46: 47: 48: 49: 50: 51: 52: 53: 54: 55: 56: 57: 58: 59: 60: 61: 62: 63: 64: 65: 66: 67: 68: 69: 70: 71: 72: 73: 74: 75: 76: 77: 78: 79: 80: 81: 82: 83: 84: 85: 86: 87: 88: 89: 90: 91: 92: 93: 94: 95: 96: 97: 98: 99: 100: 101: 102: 103: 104: 105: 106: 107: 108: 109: 110: 111: 112: 113: 114: 115: 116: 117: 118: 119: 120: 121: 122: 123: 124: 125: 126: 127: 128: 129: 130: 131: 132: 133: 134: 135: 136: 137: 138: 139: 140: 141: 142: 143: 144: 145: 146: 147: 148: 149: 150: 151: 152: 153: 154: 155: 156: 157: 158: 159: 160: 161: 162: 163: 164: 165:
| #INCLUDE "windows.bi" #INCLUDE "vbcompat.bi"
DIM AS INTEGER i,j,C,COUNT,XX,TT,A,PP,QZ,U,RR ,CON , n ,maxP , STC DIM AS LONGINT Start,ST,STT DIM AS STRING FF,FF1,FF2,FF3 DIM AS BYTE zaehler FF=CURDIR FF2=FF+"\primes.txt" FF3=FF+"\QuadR.txt" //Quelldatei der 4Tupel 101 bis 9699690 , welche ab 23 erst Teiler haben, sind 36855 Stück
REDIM Q(36855) AS INTEGER REDIM QC(36855) AS INTEGER INPUT " - 10^n+.... - Exponent n";n INPUT "Start Milliarden";Start:Start=Start*1000000000 INPUT "Stop Milliarde ";ST:St=St*1000000000 INPUT "Primzahlen ins Sieb ab 100000 bis 80 M";maxP maxP=INT (maxP/log(maxP)) // Abschätzung der Anzahl für maxP RR=1 FOR J=1 TO n RR=(RR*10) MOD 96996900 // 10 ^ n MOD 96996900 = 10 Block a 9699690 wegen Rasterversatz NEXT J Start= (Start \ 96996900) * 96996900 - RR <- siehe hier OPEN FF3 FOR INPUT AS #1 //einlesen der 4Tupel FOR C=1 TO 36855 INPUT #1,A:Q(C)=A+8 NEXT C CLOSE #1
REDIM P(maxP) AS INTEGER // einlesen der Primteiler bis maxP OPEN FF2 FOR INPUT AS #2 FOR C=1 TO maxP INPUT #2,A P(C)=A NEXT C CLOSE #2 REM Erstellung der RESTTABELLE REDIM R(maxP) AS INTEGER FOR I=1 TO maxP // ermitteln der Resttabelle aller Primteiler für 10^n+Startwert, für Verschiebungsstart des Blockes nötig RR=1 FOR J=1 TO n RR=(RR*10) MOD P(I) NEXT J R(i)=(RR+Start) MOD P(I) // Der Restwert für 10^n+Start MOD Primteiler NEXT I REDIM R2(maxP) AS INTEGER // ersten 3000 Teiler Restwert für 96996900 Primteiler für die Unterblockverschiebung 9699690 FOR I=1 TO 3000 R2(I)=9699690 MOD P(I) NEXT I FOR I=3001 TO maxP // ab 3001 Teiler Restwert für 96996900 Primteiler für die Unterblockverschiebung 96996900 R2(I)=96996900 MOD P(I) NEXT I REM ENDE REM Erstellung der RESTTABELLE 2 - 9699690 MOD P REM BEGIN SIEBEN CLS B0: STC=INT(Start/10^11) // Schnitt volle 100 Mrd Blöcke für paralelles PRPing mit PFGW.exe FF1=FF+"\"+STR(n)+"."+STR(STC) // Datei PFGW Style erstellung
IF FILEEXISTS(FF1) THEN OPEN FF1 FOR APPEND AS #9 ELSE OPEN FF1 FOR OUTPUT AS #9 PRINT #9,"ABC 10^";n;"+$a & 10^";n;"+$a+2 & 10^";n;"+$a+6 & 10^";n;"+$a+8" BEGIN: LOCATE 1,1:PRINT "10^";n;"+";Start REDIM F(96996900) AS BYTE
FOR zaehler=0 TO 9 // 10 mal 9699690 Block FOR I=1 TO 36855 //Konstantes Feld Q - Feld für jeden Blockdurchlauf in QC kopiert, weil im QC Feld hier reduziert wird QC(I)=Q(I) NEXT I
count=36855 FOR i=1 TO 3000 U=1 XX=R(I) PP=P(i) WHILE u<count // und das hier ist das Meisterstück ! REST (Primzahl bzgl Block ) MOD Primzahl soll hier 0,2,6, oder 8 sein, damit der 4er ungültig wird bei einer Bedingung QZ=(QC(u) + XX ) MOD PP IF QZ>8 THEN GOTO WEITER IF QZ MOD 2 = 1 OR QZ=4 THEN GOTO WEITER // <10 und ungerade fallen auch raus QC(u)=QC(COUNT):COUNT-=1:u-=1 // Primärsieb ! Hole das letzte 4Tupel ins erste, wenn das 1. rausfällt, reduziere Anzahl der 4er im Block um 1 WEITER: u+=1 WEND R(I)=(R(I)+R2(I)) MOD PP // Errechne neuen Rest bei Blockverschiebung 9699690 NEXT i
// kopiere die übrigen in ein BYTE Feld der Größe 96996900 für weiteres Sieben, weil hier erstmals die 96996900 / Primteiler die Anzahl der Restkandidaten unterschreitet F() ist das neue Siebfeld, der Endblock als Raster
FOR j=1 TO count F(QC(j)+zaehler*9699690)=1 F(QC(j)-2+zaehler*9699690)=1 F(QC(j)-6+zaehler*9699690)=1 F(QC(j)-8+zaehler*9699690)=1 NEXT j
NEXT zaehler
// Siebe alle Primteiler ab der 3001. bis maxP wie gewohnt durch FOR i=3001 TO maxP U=1 RR=P(i)-R(i) IF RR MOD 2= 0 THEN RR+=P(i) FOR j=RR TO 96996900 STEP P(i)*2 F(j)=0 NEXT j R(I)=(R(I)+R2(I)) MOD P(i) // Auch hier die Restblock bzgl Primteiler bei Verschiebung Block 96996900 NEXT i // Ausgabe aller übrigen 4er ab 41 in 30er Block aussuchen und in Datei fürs PRPing schreiben FOR i=41 TO 96996900 STEP 30 IF F(i)=1 AND F(i+2)=1 AND F(i+6)=1 AND F(i+8 )=1 THEN PRINT #9,I+Start NEXT i STC=INT(Start/10^11) Start+=96996900 IF START>ST THEN CLOSE #9:STOP // Prüft ob Datei abgeschlossen wird bei volle 100 Mrd IF INT(Start/10^11)>STC THEN CLOSE #9:GOTO B0 GOTO BEGIN |
Zusatz: Die Zahl 36855 ist die Anzahl aller 4 Tupel von 41+30k bis 96996900 , die Teiler ab 23 erst haben.
Diese werden aus einer fertigen Datei eingelesen.
Primzahlen bis 80 Mio werden auch eingelesen.
--------------
Baller gerade an 665 herum. Nach 8 Stunden 10^665+ ( 2 000 000 000 000 ) fast abgeschlossen, ohne Fund. Denke heute Abend wirds bei 2-5 Billionen was sein.
Moderiert von
Th69: Code-Tags hinzugefügt
Gammatester - Mo 04.09.17 15:52
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
Mathematiker und
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 - Mo 04.09.17 16:21
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 - Mo 04.09.17 17:05
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 - Mo 04.09.17 17:12
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 - Mo 04.09.17 17:20
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 - Mo 04.09.17 17:21
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 - Mo 04.09.17 17:28
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 - Mo 04.09.17 17:34
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 - Mo 04.09.17 19: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 [
https://www.entwickler-ecke.de/viewtopic.php?t=116550&postorder=asc&start=94] saust in 3 Sekunden durch 4e9 , aber die Übertragsbestimmung stimmt noch nicht, damit ich bei 10^1000 anfangen kann.
Gruß Horst
Mathematiker - Mo 04.09.17 19:57
Hallo,
darf ich noch einmal auf mein Problem
https://www.entwickler-ecke.de/viewtopic.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
pzktupel - Mo 04.09.17 20:01
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 - Mo 04.09.17 20:38
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
pzktupel - Mo 04.09.17 21:04
Nehme ( nur zur Information ) n=999, 10^998+...
Mathematiker - Mo 04.09.17 21:17
Hallo Horst,
Danke, das ist es.
LG Steffen
Delphi-Laie - Mo 04.09.17 22:12
Mathematiker hat folgendes geschrieben : |
Hallo Horst,
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 - Mo 04.09.17 22: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
Delphi-Laie - Mo 04.09.17 22: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 - Di 05.09.17 09: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.
Delphi-Laie - Di 05.09.17 10: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.
Gammatester - Di 05.09.17 20:55
Zur Abwechselung mal wieder etwas zu Quadrupeln:
Mit der Pinch-Liste der Carmichael-Zahlen bis 10^16 (Link:
http://ftp.gwdg.de/pub/math/funet/misc/RichardPinch/Carmichael/carmichael-16.gz , 4066449 Bytes) habe ich folgende Tabelle berechnet. Sie enthält Fermat-Pseudoprimzahl-Quadrupel mit einer Carmichael-Zahl. (Hinweis: Zitat von
https://de.wikipedia.org/wiki/Carmichael-Zahl Eine natürliche Zahl heißt Carmichael-Zahl, benannt nach dem Mathematiker Robert Daniel Carmichael, wenn sie eine fermatsche Pseudoprimzahl bezüglich aller zu ihr teilerfremden Basen ist.)
Interessanterweise tritt nur die Konstellation
x-8, x-6, x-2, x auf, wobei
x die Carmichael-Zahl ist und
x-8, x-6, x-2 Fermat-Pseudoprimzahlen zur Basis 2.
Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20:
| x Faktorisierung 1033669 7 13 37 307 8719309 19 37 79 157 9558334369 67 109 199 6577 107023329865 5 19 23 103 307 1549 317868427009 7 19 109 769 28513 1826363517265 5 7 53 79 157 163 487 2687463022465 5 13 17 19 67 1153 1657 3718714500865 5 7 13 19 397 769 1409 144692588218465 5 7 23 89 439 1237 3719 448933306317769 7 13 607 1213 6700249 637070091543865 5 7 107 397 8963 47807 842033901223945 5 53 109 313 937 99397 859152343812049 7 283 2179 7129 27919 1114610512354465 5 7 17 823 35117 64817 1206125685237889 13 59 73 929 1033 22447 2190392507242369 19 37 109 157 199 433 2113 4921398310999105 5 13 17 19 67 89 193 353 577 7248575534632705 5 7 13 17 37 97 433 523 1153 7459104727653085 5 13 37 67 199 277 829 1013 |
Ich habe schon auf
https://math.stackexchange.com/questions/2417565/ eine entprechende Frage zu dieser Beobachtung gestellt, aber noch keine Antwort erhalten.
Für das Prim-Vierlings-Projekt haben diese Zahlen keine
direkte Relevanz, die obigen Carmichael-Zahlen würden durch das Sieben ausgeschlossen werden. Es zeigt aber, daß ein Basis-2-Fermattest nicht ausreichend ist (wahrscheinlich gilt ähnliches für Basis-3-Fermattest, daß habe ich aber noch nicht durchgerechnet).
Delphi-Laie - Di 05.09.17 21:01
Danke! Tue ich ohnehin nicht, weil ich die beiden Befehle bis heute nicht verstehe. Ich wollte sie nur der Vollständigkeit halber als Edit erwähnen, weil ich vorher noch falsch behauptete, daß man in die Threadablaufsteuerung kaum eingreifen kann.
Horst_H - Mi 06.09.17 08:00
Hallo,
@
Gammatester
Ich hätte nicht ein so große Häufigkeit erwartet.( 6 von 1e15..1e16 == 6 aus 9e15 Zahlen )
Letztendlich ist der Fermattest, wie dass sieben, nur eine schnelle Vorauswahl, um die richtig aufwendigen Tests darauf los zu lassen.
Jetzt wäre doch die Frage, ob ein Kandidat, der sieben und Fermat überstanden hat, bei einem starkes Primtest durchgefallen ist.Das weiß sicher
Mathematiker, dass wäre ja gefühlt eine Mini-Nadel im Heuhaufen.
Gruß Horst
OlafSt - Mi 06.09.17 11:08
Delphi-Laie hat folgendes geschrieben : |
Danke! Tue ich ohnehin nicht, weil ich die beiden Befehle bis heute nicht verstehe. Ich wollte sie nur der Vollständigkeit halber als Edit erwähnen, weil ich vorher noch falsch behauptete, daß man in die Threadablaufsteuerung kaum eingreifen kann. |
Nun, Suspend hält den Thread an. Der Thread bleibt augenblicklich stehen, egal was er auch immer gerade tun mag. Resume läßt einen mit Suspend angehaltenen Thread weiterlaufen.
Das Problem an Suspend ist, das der Thread
irgendwo anhält. Das kann auch genauso gut mitten in einem
inc(MyLongInt); sein, wo das Lo-Word bereits um eins hochgezählt ist, das Hi-Word aber noch nicht bearbeitet wurde. Man hat also überhaupt keine Kontrolle darüber,
wie und wo der Thread zum Stillstand kommt.
Darum wurden Suspend und Resume auch mit deprecated markiert, so das man seine eigenen Anhalte- und Weiterlauf-Funktionen implementiert.
Dies nur als Hintergrund-Infos. Multithreading ist gar nicht so kompliziert, wie immer gesagt wird :wink: Man muß nur ein paar extra-Regeln beachten. Oh, und nachdem ich gestern Delphi Tokyo installieren und benutzen durfte, ist die Multithread-Unterstützung dort inzwischen ähnlich gut wie in C#. Wenn ich auch nur im Ansatz verstehen würde, was ihr da macht, würde ich da einsteigen und mal was mehrkerniges basteln 8) Einfach nur um zu sehen, ob es was bringt.
Delphi-Laie - Mi 06.09.17 11:25
OlafSt hat folgendes geschrieben : |
Delphi-Laie hat folgendes geschrieben : | Danke! Tue ich ohnehin nicht, weil ich die beiden Befehle bis heute nicht verstehe. Ich wollte sie nur der Vollständigkeit halber als Edit erwähnen, weil ich vorher noch falsch behauptete, daß man in die Threadablaufsteuerung kaum eingreifen kann. |
Nun, Suspend hält den Thread an. Der Thread bleibt augenblicklich stehen, egal was er auch immer gerade tun mag. Resume läßt einen mit Suspend angehaltenen Thread weiterlaufen. |
Soweit war ich auch schon, konnte das aber nie bis zu funktionierendem, gar produktivem Code weiterentwickeln. Was ich am wenigsten verstand: Wie soll sich ein angehaltener Thread "selbst am Schopfe aus dem Sumpfe ziehend" mit Suspend ein Weiterlaufen verpassen? Muß wohl von außerhalb passieren.
OlafSt hat folgendes geschrieben : |
Multithreading ist gar nicht so kompliziert, wie immer gesagt wird :wink: Man muß nur ein paar extra-Regeln beachten. |
Naja, man muß sich schon damit beschäftigen, hinterher ist man immer schlauer, und was man weiß, ist einfach (alles Binsensweisheiten).
OlafSt hat folgendes geschrieben : |
Wenn ich auch nur im Ansatz verstehen würde, was ihr da macht, würde ich da einsteigen und mal was mehrkerniges basteln 8) Einfach nur um zu sehen, ob es was bringt. |
Nun, da gibt es eine einfache Faustregel, auf die ich selbst stieß, die aber eigentlich auch offensichtlich ist: Dinge, deren Abarbeitungsreihenfolge vertauscht werden kann oder gar egal ist (im Notfalle sogar ausprobierbar), können prinzipiell auch gleichzeitig bzw. simultan geschehen.
Einfaches Beispiel aus der Mathematik, eher noch dem Rechnen der unteren Schulklassen; erinnern wir uns daran, wie das abläuft:
- Bei der schriftlichen Addition, Subtraktion und Division (die eigentlich auch nur eine "gestaffelte" Subtraktion ist), ist die Abarbeitungsreihenfolge festgelegt (bei den ersteren von hinten / klein nach vorn / groß, bei letzterem umgekehrt), weil die Zwischenergebnisse benötigt und benutzt, also weiterverarbeitet werden. Sieht eher nicht nach Parallelisierbarkeit aus.
- Bei der schriftlichen Multiplikation hingegen sind die Teilmultiplikationen völlig unabhängig voneinander, keine Zwischenergebnisse werden für eine andere Teilmultiplikation benötigt. Also können diese Schritte auch parallisiert werden. Auch die Addition der erhaltenen Summanden kann "balanciert", also parallel erfolgen (wobei aber jede diese Addition intern dann wieder nichtparallel erfolgt).
OlafSt - Mi 06.09.17 14:42
Delphi-Laie hat folgendes geschrieben : |
Soweit war ich auch schon, konnte das aber nie bis zu funktionierendem, gar produktiven Code weiterentwickeln. Was ich am wenigsten verstand: Wie soll sich ein angehaltener Thread "selbst am Schopfe aus dem Sumpfe ziehend" mit Suspend ein Weiterlaufen verpassen? Muß wohl von außerhalb passieren.
|
Absolut richtig erkannt. Ein mit Suspend "eingeschläferter" Thread kann nur per Resume wieder zum Leben erweckt werden - oder eben gekillt werden. Durch ein Suspend bekommt der Thread keinerlei Rechenzeit mehr seitens des Betriebssystems zugewiesen, er kann sich also auch nicht "selbst an den Haaren aus dem Sumpf ziehen". Somit kann ein Suspended Thread auch nicht korrekt "aufgeräumt" werden, wenn das erstellende Programm terminiert.
Gammatester - Do 07.09.17 17:36
Hier neue Ergebnisse zum diesem
Beitrag [
https://www.entwickler-ecke.de/viewtopic.php?p=708490#708490]:
Nachdem ich für mehrere Basen gerechnet und keine neuen Quadrupel mit Carmichael-Zahlen befunden habe, stellte sich heraus, daß die
x-8, x-6, x-2 alles Primzahlen sind (im Sinne von mp_is_pprime). Die Tabelle für die Basis
b erhält man, wenn man aus Liste alle Zahlen streicht, die durch
b teilbar sind.
Es bleibt weiterhin die offene Frage, warum die Carmichael-Zahl
immer am Ende eines Quadrupels steht.
Gruß Gammatester
pzktupel - Di 12.09.17 23:02
Gammatester hat folgendes geschrieben : |
Zur Abwechselung mal wieder etwas zu Quadrupeln:
Mit der Pinch-Liste der Carmichael-Zahlen bis 10^16 (Link: http://ftp.gwdg.de/pub/math/funet/misc/RichardPinch/Carmichael/carmichael-16.gz , 4066449 Bytes) habe ich folgende Tabelle berechnet. Sie enthält Fermat-Pseudoprimzahl-Quadrupel mit einer Carmichael-Zahl. (Hinweis: Zitat von https://de.wikipedia.org/wiki/Carmichael-Zahl Eine natürliche Zahl heißt Carmichael-Zahl, benannt nach dem Mathematiker Robert Daniel Carmichael, wenn sie eine fermatsche Pseudoprimzahl bezüglich aller zu ihr teilerfremden Basen ist.)
Interessanterweise tritt nur die Konstellation x-8, x-6, x-2, x auf, wobei x die Carmichael-Zahl ist und x-8, x-6, x-2 Fermat-Pseudoprimzahlen zur Basis 2.
Quelltext 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20:
| x Faktorisierung 1033669 7 13 37 307 8719309 19 37 79 157 9558334369 67 109 199 6577 107023329865 5 19 23 103 307 1549 317868427009 7 19 109 769 28513 1826363517265 5 7 53 79 157 163 487 2687463022465 5 13 17 19 67 1153 1657 3718714500865 5 7 13 19 397 769 1409 144692588218465 5 7 23 89 439 1237 3719 448933306317769 7 13 607 1213 6700249 637070091543865 5 7 107 397 8963 47807 842033901223945 5 53 109 313 937 99397 859152343812049 7 283 2179 7129 27919 1114610512354465 5 7 17 823 35117 64817 1206125685237889 13 59 73 929 1033 22447 2190392507242369 19 37 109 157 199 433 2113 4921398310999105 5 13 17 19 67 89 193 353 577 7248575534632705 5 7 13 17 37 97 433 523 1153 7459104727653085 5 13 37 67 199 277 829 1013 |
Ich habe schon auf https://math.stackexchange.com/questions/2417565/ eine entprechende Frage zu dieser Beobachtung gestellt, aber noch keine Antwort erhalten.
Für das Prim-Vierlings-Projekt haben diese Zahlen keine direkte Relevanz, die obigen Carmichael-Zahlen würden durch das Sieben ausgeschlossen werden. Es zeigt aber, daß ein Basis-2-Fermattest nicht ausreichend ist (wahrscheinlich gilt ähnliches für Basis-3-Fermattest, daß habe ich aber noch nicht durchgerechnet). |
Interessant. Die obige Zahl erfüllt für alle Basen den Fermattest, jedoch fallen die beim verschärften Test durch und die Teiler liegen sofort auf der Hand.
(1033669-1)/4=258417
2^258147 MOD 1033669 = 276606. 276607=17x53x307 , 307 ist Teiler.
3^258147 MOD 1033669 = 238538. 238539=3x7x37x307 ggT(238539,1033669)=7x37x307
Gammatester - Di 12.09.17 23:51
pzktupel hat folgendes geschrieben : |
Interessant. Die obige Zahl erfüllt für alle Basen den Fermattest, jedoch fallen die beim verschärften Test durch und die Teiler liegen sofort auf der Hand. |
Vorsicht, nicht verallgemeinern! Es gibt nämlich jede Menge Basen, für die 1033669 eine starke Pseudo-Primzahl ist. Die kleinsten 20 sind:
Quelltext
1:
| 9 16 53 81 100 107 144 173 256 363 374 381 386 417 456 465 477 517 534 545 ... |
pzktupel - Mi 13.09.17 05:59
Moment, ich meine, das für alle Basen a von 2 bis 1000 erstmal erfüllt ist:
a^1033669=a MOD 1033669.
Quelle Derive: VECTOR(MOD(a^1033669,1033669),a,2,1000)
Ausgabe: [2,3,4,5,6,7,8.....]
Gammatester - Mi 13.09.17 10:12
pzktupel hat folgendes geschrieben : |
Moment, ich meine, das für alle Basen a von 2 bis 1000 erstmal erfüllt ist:
a^1033669=a MOD 1033669.
Quelle Derive: VECTOR(MOD(a^1033669,1033669),a,2,1000)
Ausgabe: [2,3,4,5,6,7,8.....] |
Das ist trivial für Carmichael-Zahlen, hier gilt ja
a^(n-1) = 1 mod n (
https://de.wikipedia.org/wiki/Carmichael-Zahl#Definition ) und damit
a^n = a mod n.
Normalerweise ist n eine starke Pseudo-Primzahl zur Basis a, wenn mit
n=d*2^s +1 gilt (vgl.
https://de.wikipedia.org/wiki/Starke_Pseudoprimzahl )
1.
a^d = 1 mod, oder
2.
a^(d*2^r) = -1 mod n für ein r mit 0 <= r < s
Ich weiß jetzt nicht, was Du unter
'verschärften Test' verstehst. Ich hatte angenommen, Du meinst einen starken Pseudo-Primzahltest.
Wie Du schon geschrieben hast, hat man zB 2^258417 mod 1033669 = 276606 <> 1, und da 2^(2^1*258417) mod 1033669 = 986049 <> -1 gilt, ist 1033669
keine starke Pseudoprimzahl zur Basis 2. Aber wegen 9^258417 mod 1033669 = 1 ist es eine starke Pseudoprimzahl zur Basis 9.
pzktupel - Mi 13.09.17 11:24
Für alle Interessenten.
Habe eben das kleinste 100-stellige Primzahl - Quadrupel - Pärchen mit Abstand 30 gefunden.
Es lautet:
10^99+5'294'137'569'927'811 +d,d=0,2,6,8,30,32,36,38
LG
Norman
Horst_H - Do 14.09.17 21:10
Hallo,
anbei meine neueste Version, die gmp nutzt.Schafft einen Bereich von etwa 310e6 Zahlen in einer Stunde.
954 lag bei 7,5e12.Das dauert etwas ;-) ( 26 Stunden mit einer älteren Version 288e6/h )
Da ich mit Lazarus unter Linux 64 Bit arbeite, brauche ich keine gmp.dll für Windows.
Dafür habe ich nur eine alte 32-Bit Version von 2014, was sehr langsam war.
Wenn jemand eine sehr neue, am liebsten Win64 Version zur Verfügung stellen könnte, wäre das sicher hilfreich,
Gruß Horst
pzktupel - Do 14.09.17 23:21
Horst_H hat folgendes geschrieben : |
Hallo,
anbei meine neueste Version, die gmp nutzt.Schafft einen Bereich von etwa 310e6 Zahlen in einer Stunde.
954 lag bei 7,5e12.Das dauert etwas ;-) ( 26 Stunden mit einer älteren Version 288e6/h )
Da ich mit Lazarus unter Linux 64 Bit arbeite, brauche ich keine gmp.dll für Windows.
Dafür habe ich nur eine alte 32-Bit Version von 2014, was sehr langsam war.
Wenn jemand eine sehr neue, am liebsten Win64 Version zur Verfügung stellen könnte, wäre das sicher hilfreich,
Gruß Horst |
Horst , du meinst doch immer e9,oder ? :roll:
Horst_H - Fr 15.09.17 06:58
Hallo,
ja natürlich e9 bei Stunden, das wäre ja sonst zu traurig.
7.5e12 in 26 Stunden sind ja 288e9
Gruß Horst
Horst_H - Di 19.09.17 16:47
Hallo,
ich habe mal eine Version ohne Threads und mit etwas verbessertem Sieb.
Ich passe jetzt die Anzahl der verwendeten Siebprimzahlen an.
Zudem nutze ich jetzt Siebnr für große Siebprimzahlen.2e9 streicht im besten Fall nach 70 Sieben und dann nach 6.
Das bedeutet, eine kleine Ersparnis.
620Mio werden bei 998 in 773 ms gesiebt, also ein Bereich 0,8e9/s
bei 430 Stellen sind es schon 620e6/0,5 = 1,24e9/s.
Dort werden die Kandidaten auch 10-mal schneller getestet.
Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41: 42: 43: 44: 45: 46: 47: 48: 49: 50: 51: 52: 53: 54: 55: 56: 57: 58: 59: 60: 61: 62: 63: 64: 65: 66: 67: 68: 69: 70: 71: 72: 73: 74: 75: 76: 77: 78: 79: 80: 81: 82: 83: 84: 85: 86: 87: 88: 89: 90: 91: 92: 93: 94: 95: 96: 97: 98: 99: 100: 101:
| Siebgroesse 2586584 Byte // jedes Bit entspricht einem k aus 30*k+11-> 620.780.160 Start-Potenz 998 Start-Offset 0 //Zu Beginne werden alle Siebprimzahlen "ersiebt" Anzahl Siebprimzahlen 98222284 bis 1999999973 //Die Anzahl der verwendeten Siebprimzahlen Maximaler SiebprimIndex: 97930762 //inclusive Primzahlen ersieben und Übertrag berechnen für SiebprimIndex Siebzeit 00:00:21.674 Testzeit 00:00:18.886 Testzeit pro Kandidat 15.218 ms Siebzeit 00:00:00.773 Testzeit 00:00:17.744 Testzeit pro Kandidat 14.961 ms Siebzeit 00:00:00.771 Testzeit 00:00:16.967 Testzeit pro Kandidat 14.589 ms Siebzeit 00:00:00.795 Testzeit 00:00:17.689 Testzeit pro Kandidat 14.231 ms //Loesung gefunden, deshalb etwas weniger Zeit 998 1970797081 00:01:35.309 Gesamtzeit: 00:01:35.310 ---------- Start-Potenz 598 Start-Offset 0 Maximaler SiebprimIndex: 45959098 Siebzeit 00:00:04.617 //hier nur inclusive Übertrag berechnen für SiebprimIndex Testzeit 00:00:04.902 Testzeit pro Kandidat 3.494 ms Siebzeit 00:00:00.588 Testzeit 00:00:04.888 Testzeit pro Kandidat 3.409 ms Siebzeit 00:00:00.596 Testzeit 00:00:04.954 Testzeit pro Kandidat 3.452 ms Siebzeit 00:00:00.589 Testzeit 00:00:05.056 Testzeit pro Kandidat 3.451 ms Siebzeit 00:00:00.587 Testzeit 00:00:04.622 Testzeit pro Kandidat 3.470 ms Siebzeit 00:00:00.585 Testzeit 00:00:04.791 Testzeit pro Kandidat 3.417 ms Siebzeit 00:00:00.583 Testzeit 00:00:04.730 Testzeit pro Kandidat 3.433 ms Siebzeit 00:00:00.583 Testzeit 00:00:04.923 Testzeit pro Kandidat 3.435 ms Siebzeit 00:00:00.585 Testzeit 00:00:04.949 Testzeit pro Kandidat 3.420 ms Siebzeit 00:00:00.584 Testzeit 00:00:04.952 Testzeit pro Kandidat 3.441 ms Siebzeit 00:00:00.584 Testzeit 00:00:00.050 Testzeit pro Kandidat 0.035 ms //Loesung gefunden, deshalb weniger Zeit 598 6011086471 00:00:59.367
Start-Potenz 430 Start-Offset 0 Maximaler SiebprimIndex: 28413753 Siebzeit 00:00:02.713 Testzeit 00:00:02.320 Testzeit pro Kandidat 1.456 ms Siebzeit 00:00:00.504 Testzeit 00:00:02.337 Testzeit pro Kandidat 1.457 ms Siebzeit 00:00:00.505 Testzeit 00:00:02.189 Testzeit pro Kandidat 1.416 ms Siebzeit 00:00:00.504 Testzeit 00:00:02.340 Testzeit pro Kandidat 1.485 ms Siebzeit 00:00:00.503 Testzeit 00:00:02.184 Testzeit pro Kandidat 1.418 ms Siebzeit 00:00:00.502 Testzeit 00:00:02.262 Testzeit pro Kandidat 1.468 ms Siebzeit 00:00:00.503 Testzeit 00:00:02.274 Testzeit pro Kandidat 1.421 ms Siebzeit 00:00:00.513 Testzeit 00:00:02.339 Testzeit pro Kandidat 1.480 ms Siebzeit 00:00:00.503 Testzeit 00:00:02.206 Testzeit pro Kandidat 1.424 ms Siebzeit 00:00:00.502 Testzeit 00:00:02.370 Testzeit pro Kandidat 1.470 ms Siebzeit 00:00:00.504 Testzeit 00:00:02.140 Testzeit pro Kandidat 1.427 ms Siebzeit 00:00:00.503 Testzeit 00:00:01.572 Testzeit pro Kandidat 0.994 ms //Loesung gefunden, deshalb weniger Zeit 430 6969624301 00:00:34.836 |
Um alle Siebprimzahlen einmal nur abzuklappern, ohne was anderes zu tun ausser p-> p +deltaP ,dauert schon 0,1 Sekunden für die 98.222.284 Primzahlen.Irgendwie lahm.
Gruß Horst
Edit:
Unter wine als Win32 Programm braucht das Programm bei n= 998 für die ersten Kandidaten für den Test eines Kandidaten sage und schreibe 263 ms statt 15,2 ms unter Linux64 mit neuester gmp.so.
32-Bit siebt ein wenig schneller.Das hilft nur nichts.
Horst_H - Fr 03.11.17 10:46
Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2024 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!