Fastprime Quadrupel und Primzahlvierlinge

Horst_H · Verfasst: Do 10.08.17 08:53

Hallo,

Zitat:

Ziel erreicht: 1000stellige SemiPrimeQuadrupel gefunden!

matheplanet.com/math...mp;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 · Beiträge: 328 Erhaltene Danke: 101

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 · Verfasst: 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 · Verfasst: 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

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

Horst_H · Verfasst: 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 user profile icon

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

, vielleicht auch wegen cmem?

markieren

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.

user profile icon

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

markieren

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

Einloggen, um Attachments anzusehen!

Mathematiker · Verfasst: 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

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

OlafSt · Verfasst: 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.

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

Horst_H · Verfasst: 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 )

markieren

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 user profile icon

Mathematiker mal vorhatte.

Gruß Horst

Delphi-Laie · Verfasst: Di 15.08.17 10:52

Horst_H hat folgendes geschrieben :

Man kann wohl die threads an Kerne binden, aber ich hatte jetzt keine Lust dazu, das Wie heraus zu finden

SetThreadAffinityMask

Ist allerdings ein ziemlich undankbares Gefummel. Nach einer halben Ewigkeit ist es mir in diesem Programm gelungen.

Mathematiker · Verfasst: 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

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

Horst_H · Verfasst: 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:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:

 tChkListItem = record
    clSiebNr,     // Anzahl die Siebe seit Startzahl // also ist wahre Zahl Startzahl +clSiebNr*2*groesse
    clOffset  : LongWord; // ins aktuelle Sieb
    clquadTeil:tquadTeiler; // die 4 kleinen Teiler
  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 · Verfasst: 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

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

Horst_H · Verfasst: Mi 16.08.17 18:52

Hallo,

jetzt mal für Win32 ( kann nur 3 GB ) kompiliert unter wine:

markieren

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

Einloggen, um Attachments anzusehen!

Mathematiker · Verfasst: 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

markieren

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

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

Delphi-Laie · Verfasst: 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 · Verfasst: Mi 16.08.17 21:26

Hallo,

wahrscheinlicher liegt es an der Compilereinstellungen
wiki.freepascal.org/...termen.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, user profile icon

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 · Verfasst: 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 mathematikalpha.de/primzahlvierlinge
und matheplanet.com/math...&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.

Einloggen, um Attachments anzusehen!

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

Horst_H · Verfasst: 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 · Beiträge: 328 Erhaltene Danke: 101

Hallo

Mathematiker, user profile icon

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

markieren

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 mathworld.wolfram.com/PrimeQuadruplet.html gesehen.

Horst_H · Verfasst: Fr 18.08.17 14:00

Hallo,

ich habe mal bis 4000 Kandidaten ( ohne anschliessenden test) für verschiedene Stellenzahlen zählen lassen.

markieren

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 )

markieren

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.

markieren

Quelltext

1:	400 34993836001 0, 0, 0, 0 00:13:21.804

Also am besten ein Bit-Sieb wie bei user profile icon

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

markieren

Quelltext

1:	400 34993836001 0, 0, 0, 0 00:12:30.458

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme