Autor Beitrag
Mathematiker
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 2281
Erhaltene Danke: 1039

Win 8.1
Delphi 5, 7, 10.1
BeitragVerfasst: 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
ausblenden 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 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: Horst_H
Gammatester
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 293
Erhaltene Danke: 88



BeitragVerfasst: 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
ausblenden volle Höhe 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?

Für diesen Beitrag haben gedankt: Mathematiker
Mathematiker Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 2281
Erhaltene Danke: 1039

Win 8.1
Delphi 5, 7, 10.1
BeitragVerfasst: 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

_________________
Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
Gammatester
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 293
Erhaltene Danke: 88



BeitragVerfasst: 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:
ausblenden 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

ausblenden Delphi-Quelltext
1:
2:
procedure s_mp_nextprime_sieve(safe: boolean; var n: mp_int);
  {-Compute the next prime >= n using a segmented sieve, safe prime if safe=true}

statt Deiner Kandidatenwahl.

Für diesen Beitrag haben gedankt: Mathematiker
Mathematiker Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 2281
Erhaltene Danke: 1039

Win 8.1
Delphi 5, 7, 10.1
BeitragVerfasst: Mo 31.07.17 16:34 
Hallo,
user profile iconGammatester hat folgendes geschrieben Zum zitierten Posting springen:
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.
user profile iconGammatester hat folgendes geschrieben Zum zitierten Posting springen:
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.
user profile iconGammatester hat folgendes geschrieben Zum zitierten Posting springen:
Vielleicht hilf auch ein aufgebohrtes
ausblenden Delphi-Quelltext
1:
2:
procedure s_mp_nextprime_sieve(safe: boolean; var n: mp_int);
  {-Compute the next prime >= n using a segmented sieve, safe prime if safe=true}

statt Deiner Kandidatenwahl.

Danke für den Hinweis. Sehe ich mir gleich an.

Steffen

_________________
Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
Mathematiker Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 2281
Erhaltene Danke: 1039

Win 8.1
Delphi 5, 7, 10.1
BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 293
Erhaltene Danke: 88



BeitragVerfasst: Mo 31.07.17 17:08 
user profile iconMathematiker hat folgendes geschrieben Zum zitierten Posting springen:
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
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 2281
Erhaltene Danke: 1039

Win 8.1
Delphi 5, 7, 10.1
BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 1578
Erhaltene Danke: 286

[Win NT] 5.1 x86 6.1 x64
[Delphi] 7 PE, 2006, 10.1 Starter, Lazarus - [C#] VS Exp 2012 - [Android API 15] VS Com 2015, Eclipse, AIDE - [C++] Builder 10.1
BeitragVerfasst: Mo 31.07.17 17:56 
Zitat:
Die jetzt 800000 Primzahlen berechne ich am Anfang mit einem Sieb, statt einer Funktion.

Wäre das nicht gleichgesetzt mit Schummeln?

_________________
„Wo andere blind der Wahrheit folgen, denk daran ... Nichts ist wahr!" (Assassin's Creed I-II)
Mathematiker Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 2281
Erhaltene Danke: 1039

Win 8.1
Delphi 5, 7, 10.1
BeitragVerfasst: Mo 31.07.17 18:01 
user profile iconFrühlingsrolle hat folgendes geschrieben Zum zitierten Posting springen:
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

_________________
Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
Frühlingsrolle
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 1578
Erhaltene Danke: 286

[Win NT] 5.1 x86 6.1 x64
[Delphi] 7 PE, 2006, 10.1 Starter, Lazarus - [C#] VS Exp 2012 - [Android API 15] VS Com 2015, Eclipse, AIDE - [C++] Builder 10.1
BeitragVerfasst: Mo 31.07.17 18:05 
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

_________________
„Wo andere blind der Wahrheit folgen, denk daran ... Nichts ist wahr!" (Assassin's Creed I-II)
Mathematiker Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 2281
Erhaltene Danke: 1039

Win 8.1
Delphi 5, 7, 10.1
BeitragVerfasst: Mo 31.07.17 18:24 
user profile iconFrühlingsrolle hat folgendes geschrieben Zum zitierten Posting springen:
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

_________________
Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
Gammatester
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 293
Erhaltene Danke: 88



BeitragVerfasst: Mo 31.07.17 18:25 
user profile iconMathematiker hat folgendes geschrieben Zum zitierten Posting springen:
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
ausblenden 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
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 2281
Erhaltene Danke: 1039

Win 8.1
Delphi 5, 7, 10.1
BeitragVerfasst: Mo 31.07.17 18:28 
user profile iconGammatester hat folgendes geschrieben Zum zitierten Posting springen:

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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1581
Erhaltene Danke: 210

WIN7,PuppyLinux
FreePascal,Lazarus,TurboDelphi
BeitragVerfasst: 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
ausblenden 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Beiträge: 29
Erhaltene Danke: 11

Win95 - Win8.1 / MSServer2000 - MSServer2012
Delphi 6pro / XE4
BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 293
Erhaltene Danke: 88



BeitragVerfasst: Mo 31.07.17 19:37 
user profile iconHorst_H hat folgendes geschrieben Zum zitierten Posting springen:
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
ausblenden volle Höhe 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.

Für diesen Beitrag haben gedankt: Mathematiker
Mathematiker Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 2281
Erhaltene Danke: 1039

Win 8.1
Delphi 5, 7, 10.1
BeitragVerfasst: Mo 31.07.17 19:43 
Hallo,
user profile iconGammatester hat folgendes geschrieben Zum zitierten Posting springen:

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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 293
Erhaltene Danke: 88



BeitragVerfasst: Mo 31.07.17 20:07 
user profile iconMathematiker hat folgendes geschrieben Zum zitierten Posting springen:
Hallo,
...
Die Frage ist jetzt nur, wie ich auf die einzelnen Primzahlen im Sieb zugreife.

ausblenden 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..63951of longint; { primepi(800000) = 63951}
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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 1578
Erhaltene Danke: 286

[Win NT] 5.1 x86 6.1 x64
[Delphi] 7 PE, 2006, 10.1 Starter, Lazarus - [C#] VS Exp 2012 - [Android API 15] VS Com 2015, Eclipse, AIDE - [C++] Builder 10.1
BeitragVerfasst: Mo 31.07.17 20:28 
@ Mathematiker

Wenn du die Zeiger-Arithmetik anwendest, könntest du auch etwas an Zeit gut machen. Macht Sinn, wenn man langwierige Grundrechenarten mit Bitverschiebung realisiert, oder auf ein Array zugreift. Beim Array wärst du nicht mehr auf einen Index angewiesen, sondern könntest von Adresse zu Adresse (im Abstand/Größe des Datentyps) springen. Das erspart durchaus Zeit.

_________________
„Wo andere blind der Wahrheit folgen, denk daran ... Nichts ist wahr!" (Assassin's Creed I-II)

Für diesen Beitrag haben gedankt: Mathematiker