Autor |
Beitrag |
Mathematiker
![Mathematiker hat insgesamt 81.3% On-Topic und 18.7% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Mathematiker hat insgesamt 81.3% On-Topic und 18.7% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Mathematiker hat insgesamt 81.3% On-Topic und 18.7% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Mathematiker hat insgesamt 81.3% On-Topic und 18.7% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Mathematiker hat insgesamt 81.3% On-Topic und 18.7% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Mathematiker hat insgesamt 81.3% On-Topic und 18.7% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Mathematiker hat insgesamt 81.3% On-Topic und 18.7% Off-Topic Beiträge geschrieben. half ontopic star](./graphics/ranks/star_onofftopic.png)
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
Verfasst: Mo 31.07.17 14:50
Hallo,
ich bin im Moment im Matheforum Matroids Matheplanet 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.
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 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
Einloggen, um Attachments anzusehen!
_________________ Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
Zuletzt bearbeitet von Mathematiker am Fr 18.08.17 14:22, insgesamt 10-mal bearbeitet
Für diesen Beitrag haben gedankt: cryptnex, Horst_H
|
|
Gammatester
![Gammatester hat insgesamt 93.6% On-Topic und 6.4% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Gammatester hat insgesamt 93.6% On-Topic und 6.4% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Gammatester hat insgesamt 93.6% On-Topic und 6.4% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Gammatester hat insgesamt 93.6% On-Topic und 6.4% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Gammatester hat insgesamt 93.6% On-Topic und 6.4% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Gammatester hat insgesamt 93.6% On-Topic und 6.4% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Gammatester hat insgesamt 93.6% On-Topic und 6.4% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png)
Beiträge: 328
Erhaltene Danke: 101
|
Verfasst: 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
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?
Für diesen Beitrag haben gedankt: Mathematiker
|
|
Mathematiker ![Threadstarter Threadstarter](./graphics/viewtopic/threadstarter.png)
![Mathematiker hat insgesamt 81.3% On-Topic und 18.7% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Mathematiker hat insgesamt 81.3% On-Topic und 18.7% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Mathematiker hat insgesamt 81.3% On-Topic und 18.7% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Mathematiker hat insgesamt 81.3% On-Topic und 18.7% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Mathematiker hat insgesamt 81.3% On-Topic und 18.7% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Mathematiker hat insgesamt 81.3% On-Topic und 18.7% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Mathematiker hat insgesamt 81.3% On-Topic und 18.7% Off-Topic Beiträge geschrieben. half ontopic star](./graphics/ranks/star_onofftopic.png)
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
Verfasst: 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.
Ich werde jetzt erst einmal dein isprime32 einbauen.
Vielen Dank
Steffen
_________________ Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
|
|
Gammatester
![Gammatester hat insgesamt 93.6% On-Topic und 6.4% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Gammatester hat insgesamt 93.6% On-Topic und 6.4% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Gammatester hat insgesamt 93.6% On-Topic und 6.4% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Gammatester hat insgesamt 93.6% On-Topic und 6.4% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Gammatester hat insgesamt 93.6% On-Topic und 6.4% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Gammatester hat insgesamt 93.6% On-Topic und 6.4% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Gammatester hat insgesamt 93.6% On-Topic und 6.4% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png)
Beiträge: 328
Erhaltene Danke: 101
|
Verfasst: 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.
Für diesen Beitrag haben gedankt: Mathematiker
|
|
Mathematiker ![Threadstarter Threadstarter](./graphics/viewtopic/threadstarter.png)
![Mathematiker hat insgesamt 81.3% On-Topic und 18.7% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Mathematiker hat insgesamt 81.3% On-Topic und 18.7% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Mathematiker hat insgesamt 81.3% On-Topic und 18.7% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Mathematiker hat insgesamt 81.3% On-Topic und 18.7% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Mathematiker hat insgesamt 81.3% On-Topic und 18.7% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Mathematiker hat insgesamt 81.3% On-Topic und 18.7% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Mathematiker hat insgesamt 81.3% On-Topic und 18.7% Off-Topic Beiträge geschrieben. half ontopic star](./graphics/ranks/star_onofftopic.png)
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
Verfasst: Mo 31.07.17 16:34
_________________ Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
|
|
Mathematiker ![Threadstarter Threadstarter](./graphics/viewtopic/threadstarter.png)
![Mathematiker hat insgesamt 81.3% On-Topic und 18.7% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Mathematiker hat insgesamt 81.3% On-Topic und 18.7% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Mathematiker hat insgesamt 81.3% On-Topic und 18.7% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Mathematiker hat insgesamt 81.3% On-Topic und 18.7% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Mathematiker hat insgesamt 81.3% On-Topic und 18.7% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Mathematiker hat insgesamt 81.3% On-Topic und 18.7% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Mathematiker hat insgesamt 81.3% On-Topic und 18.7% Off-Topic Beiträge geschrieben. half ontopic star](./graphics/ranks/star_onofftopic.png)
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
Verfasst: 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
_________________ Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
|
|
Gammatester
![Gammatester hat insgesamt 93.6% On-Topic und 6.4% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Gammatester hat insgesamt 93.6% On-Topic und 6.4% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Gammatester hat insgesamt 93.6% On-Topic und 6.4% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Gammatester hat insgesamt 93.6% On-Topic und 6.4% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Gammatester hat insgesamt 93.6% On-Topic und 6.4% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Gammatester hat insgesamt 93.6% On-Topic und 6.4% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Gammatester hat insgesamt 93.6% On-Topic und 6.4% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png)
Beiträge: 328
Erhaltene Danke: 101
|
Verfasst: 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.
Für diesen Beitrag haben gedankt: Mathematiker
|
|
Mathematiker ![Threadstarter Threadstarter](./graphics/viewtopic/threadstarter.png)
![Mathematiker hat insgesamt 81.3% On-Topic und 18.7% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Mathematiker hat insgesamt 81.3% On-Topic und 18.7% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Mathematiker hat insgesamt 81.3% On-Topic und 18.7% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Mathematiker hat insgesamt 81.3% On-Topic und 18.7% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Mathematiker hat insgesamt 81.3% On-Topic und 18.7% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Mathematiker hat insgesamt 81.3% On-Topic und 18.7% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Mathematiker hat insgesamt 81.3% On-Topic und 18.7% Off-Topic Beiträge geschrieben. half ontopic star](./graphics/ranks/star_onofftopic.png)
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
Verfasst: 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
_________________ Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
|
|
Frühlingsrolle
Ehemaliges Mitglied
Erhaltene Danke: 1
|
Verfasst: Mo 31.07.17 17:56
- Nachträglich durch die Entwickler-Ecke gelöscht -
|
|
Mathematiker ![Threadstarter Threadstarter](./graphics/viewtopic/threadstarter.png)
![Mathematiker hat insgesamt 81.3% On-Topic und 18.7% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Mathematiker hat insgesamt 81.3% On-Topic und 18.7% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Mathematiker hat insgesamt 81.3% On-Topic und 18.7% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Mathematiker hat insgesamt 81.3% On-Topic und 18.7% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Mathematiker hat insgesamt 81.3% On-Topic und 18.7% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Mathematiker hat insgesamt 81.3% On-Topic und 18.7% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Mathematiker hat insgesamt 81.3% On-Topic und 18.7% Off-Topic Beiträge geschrieben. half ontopic star](./graphics/ranks/star_onofftopic.png)
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
Verfasst: 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:](images/smiles/icon_wink.gif) ) der Algorithmus ist, desto besser.
Steffen
_________________ Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
|
|
Frühlingsrolle
Ehemaliges Mitglied
Erhaltene Danke: 1
|
Verfasst: Mo 31.07.17 18:05
- Nachträglich durch die Entwickler-Ecke gelöscht -
|
|
Mathematiker ![Threadstarter Threadstarter](./graphics/viewtopic/threadstarter.png)
![Mathematiker hat insgesamt 81.3% On-Topic und 18.7% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Mathematiker hat insgesamt 81.3% On-Topic und 18.7% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Mathematiker hat insgesamt 81.3% On-Topic und 18.7% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Mathematiker hat insgesamt 81.3% On-Topic und 18.7% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Mathematiker hat insgesamt 81.3% On-Topic und 18.7% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Mathematiker hat insgesamt 81.3% On-Topic und 18.7% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Mathematiker hat insgesamt 81.3% On-Topic und 18.7% Off-Topic Beiträge geschrieben. half ontopic star](./graphics/ranks/star_onofftopic.png)
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
Verfasst: 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](images/smiles/icon_biggrin.gif) |
Richtig.
Schau dir den Quelltext an. Dort wird erst die Startzeit ermittelt und danach gesiebt.
Also ist es korrekt.
Steffen
_________________ Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
|
|
Gammatester
![Gammatester hat insgesamt 93.6% On-Topic und 6.4% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Gammatester hat insgesamt 93.6% On-Topic und 6.4% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Gammatester hat insgesamt 93.6% On-Topic und 6.4% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Gammatester hat insgesamt 93.6% On-Topic und 6.4% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Gammatester hat insgesamt 93.6% On-Topic und 6.4% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Gammatester hat insgesamt 93.6% On-Topic und 6.4% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Gammatester hat insgesamt 93.6% On-Topic und 6.4% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png)
Beiträge: 328
Erhaltene Danke: 101
|
Verfasst: 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)
Für diesen Beitrag haben gedankt: Mathematiker
|
|
Mathematiker ![Threadstarter Threadstarter](./graphics/viewtopic/threadstarter.png)
![Mathematiker hat insgesamt 81.3% On-Topic und 18.7% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Mathematiker hat insgesamt 81.3% On-Topic und 18.7% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Mathematiker hat insgesamt 81.3% On-Topic und 18.7% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Mathematiker hat insgesamt 81.3% On-Topic und 18.7% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Mathematiker hat insgesamt 81.3% On-Topic und 18.7% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Mathematiker hat insgesamt 81.3% On-Topic und 18.7% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Mathematiker hat insgesamt 81.3% On-Topic und 18.7% Off-Topic Beiträge geschrieben. half ontopic star](./graphics/ranks/star_onofftopic.png)
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
Verfasst: 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
_________________ Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
|
|
Horst_H
![Horst_H hat insgesamt 85.2% On-Topic und 14.8% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Horst_H hat insgesamt 85.2% On-Topic und 14.8% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Horst_H hat insgesamt 85.2% On-Topic und 14.8% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Horst_H hat insgesamt 85.2% On-Topic und 14.8% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Horst_H hat insgesamt 85.2% On-Topic und 14.8% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Horst_H hat insgesamt 85.2% On-Topic und 14.8% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Horst_H hat insgesamt 85.2% On-Topic und 14.8% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png)
Beiträge: 1652
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: 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 rosettacode.org/wiki...ernative_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.
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
Für diesen Beitrag haben gedankt: Mathematiker
|
|
Holgerx
![Holgerx hat insgesamt 100.0% On-Topic und 0.0% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Holgerx hat insgesamt 100.0% On-Topic und 0.0% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Holgerx hat insgesamt 100.0% On-Topic und 0.0% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Holgerx hat insgesamt 100.0% On-Topic und 0.0% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Holgerx hat insgesamt 100.0% On-Topic und 0.0% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Holgerx hat insgesamt 100.0% On-Topic und 0.0% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Holgerx hat insgesamt 100.0% On-Topic und 0.0% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png)
Beiträge: 62
Erhaltene Danke: 27
Win95 - Win11 / MSServer2000 - MSServer2019
Delphi 6pro / XE4
|
Verfasst: 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ß?
Für diesen Beitrag haben gedankt: Mathematiker
|
|
Gammatester
![Gammatester hat insgesamt 93.6% On-Topic und 6.4% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Gammatester hat insgesamt 93.6% On-Topic und 6.4% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Gammatester hat insgesamt 93.6% On-Topic und 6.4% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Gammatester hat insgesamt 93.6% On-Topic und 6.4% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Gammatester hat insgesamt 93.6% On-Topic und 6.4% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Gammatester hat insgesamt 93.6% On-Topic und 6.4% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Gammatester hat insgesamt 93.6% On-Topic und 6.4% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png)
Beiträge: 328
Erhaltene Danke: 101
|
Verfasst: 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
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.
Für diesen Beitrag haben gedankt: Mathematiker
|
|
Mathematiker ![Threadstarter Threadstarter](./graphics/viewtopic/threadstarter.png)
![Mathematiker hat insgesamt 81.3% On-Topic und 18.7% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Mathematiker hat insgesamt 81.3% On-Topic und 18.7% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Mathematiker hat insgesamt 81.3% On-Topic und 18.7% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Mathematiker hat insgesamt 81.3% On-Topic und 18.7% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Mathematiker hat insgesamt 81.3% On-Topic und 18.7% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Mathematiker hat insgesamt 81.3% On-Topic und 18.7% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Mathematiker hat insgesamt 81.3% On-Topic und 18.7% Off-Topic Beiträge geschrieben. half ontopic star](./graphics/ranks/star_onofftopic.png)
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
Verfasst: 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
_________________ Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
|
|
Gammatester
![Gammatester hat insgesamt 93.6% On-Topic und 6.4% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Gammatester hat insgesamt 93.6% On-Topic und 6.4% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Gammatester hat insgesamt 93.6% On-Topic und 6.4% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Gammatester hat insgesamt 93.6% On-Topic und 6.4% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Gammatester hat insgesamt 93.6% On-Topic und 6.4% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Gammatester hat insgesamt 93.6% On-Topic und 6.4% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png) ![Gammatester hat insgesamt 93.6% On-Topic und 6.4% Off-Topic Beiträge geschrieben. ontopic star](./graphics/ranks/star_ontopic_full.png)
Beiträge: 328
Erhaltene Danke: 101
|
Verfasst: 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 |
Für diesen Beitrag haben gedankt: Mathematiker
|
|
Frühlingsrolle
Ehemaliges Mitglied
Erhaltene Danke: 1
|
Verfasst: Mo 31.07.17 20:28
- Nachträglich durch die Entwickler-Ecke gelöscht -
Für diesen Beitrag haben gedankt: Mathematiker
|
|
|