Autor |
Beitrag |
Horst_H
Beiträge: 1652
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
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
|
Verfasst: 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! 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
Beiträge: 1652
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
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
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
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
Beiträge: 1652
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
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 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?
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 |
Einloggen, um Attachments anzusehen!
Zuletzt bearbeitet von Horst_H am Mo 14.08.17 16:27, insgesamt 2-mal bearbeitet
Für diesen Beitrag haben gedankt: Mathematiker
|
|
Mathematiker
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
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
Beiträge: 486
Erhaltene Danke: 99
Win7, Win81, Win10
Tokyo, VS2017
|
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
Beiträge: 1652
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
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 )
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
|
|
Delphi-Laie
Beiträge: 1600
Erhaltene Danke: 232
Delphi 2 - RAD-Studio 10.1 Berlin
|
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
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
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
Beiträge: 1652
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
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:
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
Für diesen Beitrag haben gedankt: Mathematiker
|
|
Mathematiker
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
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
Beiträge: 1652
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: 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
Einloggen, um Attachments anzusehen!
Für diesen Beitrag haben gedankt: Mathematiker
|
|
Mathematiker
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
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
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
Beiträge: 1600
Erhaltene Danke: 232
Delphi 2 - RAD-Studio 10.1 Berlin
|
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
Beiträge: 1652
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
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, 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
Für diesen Beitrag haben gedankt: Mathematiker
|
|
Mathematiker
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
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".
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
Beiträge: 1652
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
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
Für diesen Beitrag haben gedankt: Mathematiker
|
|
Gammatester
Beiträge: 328
Erhaltene Danke: 101
|
Verfasst: 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 mathworld.wolfram.com/PrimeQuadruplet.html gesehen.
Für diesen Beitrag haben gedankt: Horst_H, Mathematiker
|
|
Horst_H
Beiträge: 1652
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: 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 |
Für diesen Beitrag haben gedankt: Mathematiker
|
|
|