Einsame Primzahlen

Mathematiker · Verfasst: Mo 22.04.13 10:42

Hallo,
angeregt durch user profile icon

IhopeonlyReaders Beitrag zu riesigen Boolean-Feldern www.entwickler-ecke....ewtopic.php?t=111430 habe ich mein Primzahlsieb wieder aktiviert und suche nun "einsame Primzahlen".
Das soll keine Konkurrenz zu IhopeonlyReader sein! Nur in seinem Beitrag geht es vorwiegend um das Feld und möglichst effektive Berechnung großer Primzahlmengen, mir geht es um eine spezielle Primzahlart.

Unter einer einsamen Primzahl versteht man eine Primzahl p, deren Summe s der Abstände zur vorhergehenden und zur nachfolgenden Primzahl größer ist, als bei jeder vorhergehenden Primzahl.
Zum Beispiel ist die 211 eine einsame Primzahl. Die vorhergehende Primzahl ist 199, die nachfolgende 223. Deren Abstand ist mit 24 so groß, wie bei keiner Primzahl < 211.

In meinem Programm suche ich die jeweils kleinsten Primzahlen, für dich sich eine Summe s von 200, 202, ... ergibt. Die eigentlichen einsamen Primzahlen, d.h. mit einer neuen größten Summe, sind mit einem Stern * vor dem Intervall gekennzeichnet.
Markiert man "Weiterrechnen", so werden beim Abbruch die Ergebnisse gespeichert und bei Neustart an der entsprechenden Stelle weitergerechnet.

Zum Algorithmus: Jeweils 5 Millionen Zahlen werden mit allen notwendigen, ungeraden Primzahlen gesiebt. Danach werden im Sieb drei benachbarte Primzahlen auf einen noch nicht bekannten Abstand getestet. Anschließend folgt der nächste 5 Millionen-Bereich usw.
Jetzt geht's weiter bis 2 Billionen.
Gegenwärtig kann das Programm bis 1 Billion testen, da das Sieb mit den vordefinierten Primzahlen bis 1 Million arbeitet.
Der Versuch, mit weniger Zahlen zu sieben und anschließend die verbleibenden Zahlen mit einem Primzahltest zu kontrollieren, benötigte wesentlich mehr Zeit, ebenso größere Zahlbereiche als die gewählten 5 Millionen.
Wichtig ist noch, dass das Programm nur mit user profile icon

Gammatesters mp_arith funktioniert.

Im Moment bin ich bei 60 Milliarden, denke aber die 1 Billion heute noch zu schaffen. Ich schätze rund 6-7 Stunden Berechnungszeit. Mal sehen.
Die größte einsame Primzahl ist bis jetzt 50949283459 mit einem Abstand von 524 zwischen 50949283109 und 50949283633.

Beste Grüße
Mathematiker

Nachtrag: Nach knapp 5 Stunden ist die 1 Billion erreicht. Das Ergebnis hänge ich als Txt-Datei an.
Die größte bekannte(???), einsame Primzahl ist nun 929156727137 mit einer Abstandssumme von 624 ab 929156727013 bis 929156727637. Die kleinste Summe, für die ich noch keine Lösung habe, ist 556.

Rev 1/2: Die Anfangsprimzahlen werden berechnet und weitere kleinere Änderungen. Insgesamt kann jetzt bis 50 Billionen nach einsamen Primzahlen gesucht werden.
Rev 3: Durch Änderung der Siebgröße, der Datentypen und das Speichern von berechneten Resten ist das Programm mehr als 3mal so schnell. Dank an user profile icon

Horst_H!
Rev 4: Die Berechnung der einsamen Primzahlen und lonely primes ist jetzt in einem Programm zusammengefasst.
Rev 5: Weitere Beschleunigung durch 3 Ausgangssiebe für die Teilbarkeit mit 3 und 5.

Einloggen, um Attachments anzusehen!

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

Tranx · Verfasst: Mo 22.04.13 12:32

Edit: Ich habe bisher bis zu 1 Billion rechnen lassen (ca. 3 h). Größte Primzahldifferenz: 624

Was festzustellen ist, die Anzahl Lücken werden immer kleiner, bis neue Primzahldifferenzen belegt werden. Das liegt auch auf der Hand. Die Funktion ist Prim = 6*10^-16 * dPrim^(9,735), d.h. potential ansteigend, die Differenz von 2000 wird erst bei einer Primzahl in der Größenordnung von ca. 80.000.000.000.000.000 */ 3 (80 Brd.) erreicht. Da können wir noch lange rechnen lassen!

Einloggen, um Attachments anzusehen!

_________________
Toleranz ist eine Grundvoraussetzung für das Leben.

Mathematiker · Verfasst: Mo 22.04.13 17:20

Hallo,

Tranx hat folgendes geschrieben :

Edit: Ich habe bisher bis zu 1 Billion rechnen lassen (ca. 3 h). Größte Primzahldifferenz: 624

Sehr schön. Dein Programm ist offensichtlich schneller. Aber bis 80 Billiarden werden wir wohl nie kommen.

Ich habe im Netz etwas recherchiert und unter "lonely primes" eine etwas abweichende Definition gefunden.
Unter oeis.org/A087770 versteht man darunter eine Primzahl, deren Abstände zur vorhergehenden und nachfolgenden Primzahl streng monoton steigen.
Damit gibt es wesentlich weniger derartige Primzahlen, als die oben besprochenen einsamen Primzahlen.

Ich habe das Ausgangsprogramm modifiziert und lasse jetzt in diesem 2.Programm lonely primes suchen.
Zumindest habe ich schon drei gefunden, die in der "The On-Line Encyclopedia of Integer Sequences" nicht erwähnt werden, die 6613941601, 11179888193 und die 24016237123.

Für mich ist es immer wieder faszinierend, was man mit Zahlen und insbesondere Primzahlen so anstellen kann.
Noch verrückter finde ich, dass 2200 Jahre nach Eratosthenes dessen Grundidee des Primzahlsiebs immer noch die schnellsten Algorithmen ermöglicht.

Beste Grüße
Mathematiker

Nachtrag: Die Berechnung der lonely primes ist jetzt im ursprünglichen Programm zusätzlich enthalten. siehe 1.Beitrag.

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

IhopeonlyReader · Beiträge: 600 Erhaltene Danke: 23 Delphi 7 PE

Ich denke ich klinke mich auch mit ein

Welche "Art" willst du denn jetzt berechnen, bzw. nach welcher Definition?
lonely primes oder einsame Primzahlen (ja ich weiß ist dasselbe, aber für mich ist: einsame Primzahl, die nach Mathematiker benannten einsamen Primzahlen und die lonely primes die "neuen")

_________________
Sucht "neueres" Delphi

Wer nicht brauch was er hat, brauch auch nicht was er nicht hat!

Mathematiker · Verfasst: Mo 22.04.13 17:49

Hallo,

IhopeonlyReader hat folgendes geschrieben :

Welche "Art" willst du denn jetzt berechnen, bzw. nach welcher Definition?

Beide Arten. Bei den lonely primes habe ich 100 Milliarden getestet, mit der neuen lonely prime 96155166493.

IhopeonlyReader hat folgendes geschrieben :

... einsame Primzahl, die nach Mathematiker benannten einsamen Primzahlen

Vielen Dank. Aber diese Ehre kommt mir nicht zu. :wink:

Ich kann Dir aber nicht mehr sagen, wo ich den Begriff "einsame Primzahl" erstmals gelesen habe. Das ist schon lange her.

Beste Grüße
Mathematiker

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

IhopeonlyReader · Beiträge: 600 Erhaltene Danke: 23 Delphi 7 PE

Mathematiker hat folgendes geschrieben :

Ich kann Dir aber nicht mehr sagen, wo ich den Begriff "einsame Primzahl" erstmals gelesen habe

Noch eine neue Aufgabe

_________________
Sucht "neueres" Delphi

Wer nicht brauch was er hat, brauch auch nicht was er nicht hat!

Delphi-Laie · Verfasst: Mo 22.04.13 17:53

Mathematiker hat folgendes geschrieben :

Für mich ist es immer wieder faszinierend, was man mit Zahlen und insbesondere Primzahlen so anstellen kann.

Nun, das ist bei der zentralen Bedeutung der Primzahlen in der Mathematik im allgemeinen und in der Arithmetik im besonderen auch nicht verblüffend. Im letzteren sind sie die zentralen Elemente, so, wie die Elementarteilchen (oder der Quarks?) in der Quantenphysik oder der chemischen Elemente in der Chemie.

Letztlich liegt es nur an der Kreativität, irgendwelche neuen Gesetzmäßigkeiten zunächst einmal auszudenken, und seien es nur schnöde Differenzen. Allerdings gehorchen diese dann nicht mehr dem menschlichen Geist - ein sicheres Merkmal, daß das, was sich das "ausgedacht" wird, in Wirklichkeit ein Eigenleben jenseits des menschlichen Geistes führt.

Mathematiker hat folgendes geschrieben :

Noch verrückter finde ich, dass 2200 Jahre nach Eratosthenes dessen Grundidee des Primzahlsiebs immer noch die schnellsten Algorithmen ermöglicht.

Der Definition der Primzahlen gemäß sind Divisionen auch heute noch ein zentrales Element, um Zahlen auf ihre Primeigenschaft hin zu prüfen (auch wenn es wesentlich raffiniertere Methoden als die schnöden Probedivisionen inzwischen gibt). Das Sieb des Eratosthenes verzichtet darauf, es ist eher eine Art "Listenmanipulation", womit aber auch sein größter Nachteil schon in die Wiege gelegt ist: Die Endlichkeit der zu untersuchenden Menge und vor allem, sie vorher festlegen zu müssen. Insofern verblüfft mich die Geschwindigkeit nicht, aber sie fasziniert mich auch nicht.

Mathematiker · Verfasst: Mi 24.04.13 21:37

Hallo,
ich habe beide Programme für die "einsamen Primzahlen" und "lonely primes" überarbeitet. U.a. wird das Primzahlfeld zum Sieben jetzt berechnet. Dadurch wird jede Exe deutlich kleiner. Außerdem kann man nun auch wesentlich größere Bereiche testen.

Bei den einsamen Primzahlen habe ich 3,6 Billionen getestet und werde sicher noch bis 50 Billionen, evtl. noch höher, vordringen.
Die größte einsame Primzahl ist nun 3605572653889 mit einer Intervallbreite von 690 bei [3605572653481;3605572654171].
Die lonely primes sind im Moment bis 850 Milliarden kontrolliert. Die größte ist dort 633880576177.

Ob es schneller geht, kann ich nicht richtig abschätzen; trotz der Tatsache, dass user profile icon

Horst_H in anderen Primzahl-Beiträgen tolle Ideen hat. Irgendwie sind die hier nicht anwendbar. Glaube ich.

Beste Grüße
Mathematiker

Stand der Berechnung einsame Primzahlen
gerechnet bis 4,7 Billionen: 700 / 4079970755417 / [4079970755221-4079970755921]

Stand der Berechnung lonely primes
gerechnet bis 2,0 Billionen: 324,334 / 1480975873513 / [1480975873189;1480975873847]

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

Horst_H · Verfasst: Do 25.04.13 21:58

Hallo,

ich kann jetzt nicht feststellen, wieviel der Anteil des Siebens an der Laufzeit ist.Mir ist nur aufgefallen, dass Du bei jedem sieben erst den Uebertrag berechnest.Du musst auch nicht mit allen Primzahln immer sieben, manche sind ja noch gar nicht dran.
Mit einem segmentierten Sieb mit einem vorgesiebten Feld braucht man das nicht.Das macht die Sache schneller.
In 26 Sekunden siebe und zaehle ich die Primzahlen bis 1e10.Dein Programm in der gleichen Zeit etwa bis 2.7e9
Ich bin dabei davon ausgegangen, das Du nicht unbedingt über Maxint64 hinaus willst, somit kann ich mit Longword für Siebprimzahl und deren Uebertrag arbeiten.
Das Du am Ende des Siebfeldes bis n siebst aber beim neuen mit n-2000 wieder beginnst ist ja nicht so prickelnd, damit fällt ein vorgesiebtes Feld fast flach. aber auch das ginge
Du siebst 111111111111111_111 ab "_" sind die letzten 2000.
Das nächste Sieb muss einfach nur so kopiert werden
_11122222222222_222 und bei der Uebertrag Bestimmung beachtet werden.
Sodele ich hab bis 1e11 = 100 Milliarden sieben lassen, ein Glück dass ich primepi habe und diese krummen Zahlen kontrollieren kann.

markieren

Quelltext

1:
2:
3:

Siebe ab                  0
Gesiebt bis    100000230330      Anzahl 4118063959
real  4m42.330s

Die Sieblänge von 510510 div 2 Zahlen ist wichtig, denn diese passt in meinen Level-II Cache.
Deine 5 Mio bremsen enorm!
Probiere mal 250000 als Sieblänge und beobachte die Zeiten.

Das Programm kann vielleicht auch für user profile icon

Gammatester interessant sein, weil es exemplarisch zeigt, wie ich mir das mit dem Sieben für Primvierer in großen Dimensionen vorstellte.
Dabei würde man eben ein 510510 Sieb das nur mit Prime16 siebt implementieren und zuerst sieben und anschließend nur die verbliebenen Zahlen mittels Miller-Rabin ausführlich testen.Damit hat man auf einen Schlag 510510 Zahlen mit 6542 Primzaheln getestest und Next prime wird schneller.

Gruß Horst

Einloggen, um Attachments anzusehen!

Gammatester · Beiträge: 328 Erhaltene Danke: 101

Horst_H hat folgendes geschrieben :

Das Programm kann vielleicht auch für user profile icon

Gammatester interessant sein, weil es exemplarisch zeigt, wie ich mir das mit dem Sieben für Primvierer in großen Dimensionen vorstellte. Dabei würde man eben ein 510510 Sieb das nur mit Prime16 siebt implementieren und zuerst sieben und anschließend nur die verbliebenen Zahlen mittels Miller-Rabin ausführlich testen.Damit hat man auf einen Schlag 510510 Zahlen mit 6542 Primzaheln getestest und Next prime wird schneller.

Wie ich vor längerer Zeit schon einmal geschrieben hatte, ist es mir auch klar, daß durch Sieben nextprime (und Du meinst doch wohl mp_nextprime für mp_ints) schneller wird. Die Frage ist nur wieviel bei welchen Aufwand. Ich hänge jetzt mal das aktualisierte verwendete Testprogram von 2006 an (Code ist allerdings zT grausam und experimentell :oops:

). Es bestimmt die Zeit zur Ermittlung der ersten 6 Primzahlen > 2^1024, also ein Problem aus der RSA-Praxis; die Zeiten sind:

markieren

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:

X:\TMP>T_NEXTP9.EXE
Test of MP library V1.26.02 (31/32 bit)   (c) W.Ehrhardt 2013
Time for finding the first 6 primes after 2^1024
Standard mp_nextprime: ......Time [s]: 7.819
nextsievex: ......Time [s]: 6.477
mp_Prime_Next_Prime: ......Time [s]: 7.095
mp_nexxxt: ......Time [s]: 6.679
nextprimeNX: ......Time [s]: 6.316
nextsieve: ......Time [s]: 5.876
nextsievew2: ......Time [s]: 5.874
nextsievew3: ......Time [s]: 5.873
nextsievew4: ......Time [s]: 5.198
nextsievew6: ......Time [s]: 4.991

Es wäre also interessant zu wissen, wie sich Dein Vorschlag einpaßt.

Gruß Gammatester

(PS: Leider bin ich ab ca 14Uhr bis Montag offline).

Einloggen, um Attachments anzusehen!

Mathematiker · Verfasst: Fr 26.04.13 15:27

Hallo,
da ich im Moment wenig Zeit habe, konnte ich die ganzen guten Hinweise noch nicht einbeziehen. Nur eine Sache ging schnell.
Ich habe auf user profile icon

Horst_H's Hinweis mp_arith entfernt und auf int64 umgestellt. Beim ersten Test wurde ich schon stutzig und habe heute zwei (Schul)rechner gleichzeitig mit int64 bzw. mp_arith rechnen lassen. Und mein erster Eindruck war richtig: Gammatesters mp_arith ist schneller!

In knapp 7 Stunden (die Schulcomputer sind langsam) konnte mit mp_arith das Intervall [5,2 Billionen ; 6,243 Billionen] nach einsamen Primzahlen abgesucht werden, mit int64 als Datentyp nur bis 6,185 Billionen, d.h. rund 9 % weniger.
Das verstehe ich nun nicht mehr. Auf jeden Fall spricht es für Gammatester oder/aber gegen mein Delphi 5.
Ich habe einmal die wesentlichen Unterschiede herausgezogen:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:

...   mp_add_d(z,siebgroesse-laenge,a);  
      mp_sqrt(a,b);
      mp_is_longint(b,grenze);
bzw.
      a:=z+siebgroesse-laenge;
      grenze:=trunc(sqrt(1.0*a));
...
        mp_mod_int(z,primz[i],d);
bzw.
        d:=z mod primz[i];
...
      mp_add_d(z,siebgroesse-laenge,z);
bzw.
      z:=z+siebgroesse-laenge;

Fazit für mich: Int64 lieber durch mp_int als Datentyp ersetzen. Und meine Hochachtung vor Gammatesters Langarithmetik-Paket. :zustimm:

Nebenbei: Die größte einsame Primzahl ist nun 5061226833937 (760 / [5061226833427;5061226834187]). Eine neue lonely prime habe ich bis 3,05 Billionen nicht gefunden.

Beste Grüße
Mathematiker

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

Mathematiker · Verfasst: Sa 27.04.13 09:07

Hallo,
da es mir keine Ruhe gelassen hat, bin ich heute früh halb 6 aufgestanden

und habe versucht die guten Ideen von user profile icon

Horst_H umzusetzen. Das Ergebnis kann sich sehen lassen.

Zuerst habe ich die Überlappung der einzelnen Suchbereiche entfernt und anschließend die letzten berechneten Reste während des Siebverfahrens gespeichert.
Als ich dann noch den Siebbereich auf 500000 gesenkt habe, wurde es richtig schnell.
Und das anschließende Umstellen auf int64, statt mp_int, brachte nun auch den gewünschten Effekt. Es wurde nochmals schneller.
Insgesamt habe ich nun eine mehr als 3,5mal so schnelle Berechnung (Rev 3). Dank an user profile icon

Horst_H!

Die lonely primes bekommen die schnelle Berechnung auch noch, später.

Beste Grüße
Mathematiker

Nachtrag: Auch die lonely primes werden jetzt 3mal schneller berechnet.

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

Mathematiker · Verfasst: So 28.04.13 08:55

Hallo,
eigentlich war es ziemlich unsinnig die Berechnung der einsamen Primzahlen und lonely primes in getrennten Programmen ablaufen zu lassen.
Deshalb habe ich beide Ermittlungen nun in einem Programm zusammengefasst. (Rev 4)

Beste Grüße
Mathematiker

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

Horst_H · Verfasst: So 28.04.13 17:01

Hallo,

@ user profile icon

Gammatester
Ich ging davon aus, das hier auch riesege Bereiche abgegrast werden, aber es sind in Deinem Beispiel nur 43009-37216.
AMD mag wohl einfache boolean Siebe am liebsten. BitTest(Re)Set Memory,Register und solche Befehle brauchen ja 7..10 Takte und ein mov kann in 1/3 Takten erledigt sein.Und freepascal benutzt diese scheinbar gerne.

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:

(*
C:\TMP>T_NEXTP9.EXE
Test of MP library V1.26.02 (31/32 bit)   (c) W.Ehrhardt 2013
Time for finding the first 6 primes after 2^1024
Standard mp_nextprime: ......Time [s]: 7.837
nextsievex: ......Time [s]: 6.498
mp_Prime_Next_Prime: ......Time [s]: 7.116
mp_nexxxt: ......Time [s]: 6.702
nextprimeNX: ......Time [s]: 6.333
nextsieve: ......Time [s]: 5.880
nextsievew2: ......Time [s]: 5.893
nextsievew3: ......Time [s]: 5.892
nextsievew4: ......Time [s]: 5.209
nextsievew6: ......Time [s]: 4.998
17976931348623159077293051907890247336179769789423065727343008115773267580550096
31327084773224075360211201138798713933576587897688144166224928474306394741243777
67893424865485276302219601246094119453082952085005768838150682342462881473913110
540827237163350510684586298239947245938479716304835356329624224143009
*)
(* in std.inc dies fuer FPC eingebaut:
*   {$ifdef VER2}
    {$OPTIMIZATION ON}
    {$OPTIMIZATION REGVAR}
    {$OPTIMIZATION PEEPHOLE}
    {$OPTIMIZATION CSE}
    {$OPTIMIZATION ASMCSE}
*) 

(* freepascal 2.6.2 linux32 AMD Phenom II 955 X4 3.2 Ghz

Test of MP library V1.25.03 (31/32 bit)   (c) W.Ehrhardt 2013
Time for finding the first 6 primes after 2^1024
Erst einmal sehen, wie grosz 2^1024 ist:
17976931348623159077293051907890247336179769789423065727343008115773267580550096
31327084773224075360211201138798713933576587897688144166224928474306394741243777
67893424865485276302219601246094119453082952085005768838150682342462881473913110
5408272371633505106845862982399472459384797163048353563296242241 37216

Standard mp_nextprime: ......Time [s]: 4.870
nextsievex: ......Time [s]: 3.487
mp_Prime_Next_Prime: ......Time [s]: 4.181
mp_nexxxt: ......Time [s]: 3.839
nextprimeNX: ......Time [s]: 3.760
nextsieve: ......Time [s]: 3.137
nextsievew2: ......Time [s]: 3.146
nextsievew3: ......Time [s]: 3.145
nextsievew4: ......Time [s]: 3.048
nextsievew6: ......Time [s]: 2.946
17976931348623159077293051907890247336179769789423065727343008115773267580550096
31327084773224075360211201138798713933576587897688144166224928474306394741243777
67893424865485276302219601246094119453082952085005768838150682342462881473913110
5408272371633505106845862982399472459384797163048353563296242241 43009

real    0m37.368s
user    0m37.243s
sys 0m0.000s
*)

(* 64.Bit Linux
# time ./t_nextp9
Test of MP library V1.25.03 (31/32 bit)   (c) W.Ehrhardt 2013
Time for finding the first 6 primes after 2^1024
Standard mp_nextprime: ......Time [s]: 3.105
nextsievex: ......Time [s]: 2.071
mp_Prime_Next_Prime: ......Time [s]: 2.392
mp_nexxxt: ......Time [s]: 2.281
nextprimeNX: ......Time [s]: 2.165
nextsieve: ......Time [s]: 1.871
nextsievew2: ......Time [s]: 1.872
nextsievew3: ......Time [s]: 1.870
nextsievew4: ......Time [s]: 2.101
nextsievew6: ......Time [s]: 2.035
17976931348623159077293051907890247336179769789423065727343008115773267580550096
31327084773224075360211201138798713933576587897688144166224928474306394741243777
67893424865485276302219601246094119453082952085005768838150682342462881473913110
540827237163350510684586298239947245938479716304835356329624224143009

real  0m21.786s
user  0m21.700s
sys  0m0.010s
*)

@

Mathematiker
KimWalisch sein ECprime Version 4.2 braucht bei mir nur 7.4 Sekunden, um mit 4 Threads für 2..1e11 zu sieben. Bei einem thread 28. Sekunden und nicht 246.

Gruß Horst

Gammatester · Beiträge: 328 Erhaltene Danke: 101

Horst_H hat folgendes geschrieben :

Ich ging davon aus, das hier auch riesege Bereiche abgegrast werden, aber es sind in Deinem Beispiel nur 43009-37216.
AMD mag wohl einfache boolean Siebe am liebsten. BitTest(Re)Set Memory,Register und solche Befehle brauchen ja 7..10 Takte und ein mov kann in 1/3 Takten erledigt sein.Und freepascal benutzt diese scheinbar gerne.

Ja ein großes Sieb ist für eine Nextprime-Funktion in diesem Bereich nicht nötig. Es ist sinnvoll für viel größere Zahlen oder wenn man wirklich viele Zahlen in einem Bereich testen muß.

Aber immerhin habe ich ja durch Deine Zahlen einen Hinweis darauf, wie sich die Zeiten auf verschiedenen Systemen ändern können. Vielen Dank!

Gruß Gammatester

Lelf · Beiträge: 42 Erhaltene Danke: 21

@Gammatester
Ich habe mit einem anderen Programm nachgerechnet und bin zu diesem Ergebnis gekommen:

PrimListe Anfang: 2^1024 =
179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356329624224137216
(1.) 1797693134 ... 4224137859 Abstand: 643 time: 7,185 sec
(2.) 1797693134 ... 4224138297 Abstand: 438 time: 4,487 sec
(3.) 1797693134 ... 4224139329 Abstand: 1032 time: 10,504 sec
(4.) 1797693134 ... 4224139931 Abstand: 602 time: 7,110 sec
(5.) 1797693134 ... 4224140927 Abstand: 996 time: 10,505 sec
(6.) 1797693134 ... 4224142551 Abstand: 1624 time: 16,037 sec
(7.) 1797693134 ... 4224143009 Abstand: 458 time: 4,948 sec
PrimListe: 1min 0,8240sec Fertig! Gesamt-Abstand: (5793) grösster Abstand: (1624) bei Nr. 6

Die unterschiedlichen Primabstände (min.438, max.1624) müßten sich doch in der Berechnung-Zeit widerspiegeln. Auch hat das Programm in dem Bereich 7 Primzahlen gefunden.

Gruß Lelf

Gammatester · Beiträge: 328 Erhaltene Danke: 101

Lelf hat folgendes geschrieben :

@Gammatester
Ich habe mit einem anderen Programm nachgerechnet und bin zu diesem Ergebnis gekommen:

PrimListe Anfang: 2^1024 =
[...]
(1.) 1797693134 ... 4224137859 Abstand: 643 time: 7,185 sec
(2.) 1797693134 ... 4224138297 Abstand: 438 time: 4,487 sec
(3.) 1797693134 ... 4224139329 Abstand: 1032 time: 10,504 sec
(4.) 1797693134 ... 4224139931 Abstand: 602 time: 7,110 sec
(5.) 1797693134 ... 4224140927 Abstand: 996 time: 10,505 sec
(6.) 1797693134 ... 4224142551 Abstand: 1624 time: 16,037 sec
(7.) 1797693134 ... 4224143009 Abstand: 458 time: 4,948 sec
PrimListe: 1min 0,8240sec Fertig! Gesamt-Abstand: (5793) grösster Abstand: (1624) bei Nr. 6

Die unterschiedlichen Primabstände (min.438, max.1624) müßten sich doch in der Berechnung-Zeit widerspiegeln. Auch hat das Programm in dem Bereich 7 Primzahlen gefunden.

Lelf,
vielen vielen Dank für die unabhängige Rechnung. Ich habe jetzt mal alle erzeugten Zahlen ausgegeben und dabei festgestellt, daß ab nextsieve alle Siebprozeduren die ... 4224142551 auslassen! Deshalb findet Dein Programm auch 7 Primzahlen bis .. 4224143009.

Also ein echter Bug! :oops:

Woran's liegt, weiß ich noch nicht (ein Kandidat ist die Verwendung von word statt longint). Aber wenigstens rechnet das 'offizielle' mp_nextprime richtig.

Nochmals vielen Dank.

Gruß Gammatester

Edit (15:55): Der Verdacht mit word/longint hat sich bestätigt. Jetzt sind alle Prozeduren konsistent und am schnellsten ist nextsieve mit 4.719s. Nochmals Danke!

Tranx · Verfasst: Mo 29.04.13 17:00

Gammatester: Die Korrelation zwischen den Zeitergebnissen udn den Differenzen ist sehr gut (siehe Bild):

Einloggen, um Attachments anzusehen!

_________________
Toleranz ist eine Grundvoraussetzung für das Leben.

Horst_H · Verfasst: Mo 29.04.13 18:09

Hallo,

@ user profile icon

Gammatester und user profile icon

Lelf:
jetzt müßte man nur noch wissen, mit welchem Verfahren und wievielen Runden beim Miller-Rabin Test bei den veschiedenen Programmen gearbeitet wird, damit man die Zeiten auch einordnen kann.

Gruß Horst
P.S.:
Seit wann werden hier die Threads für andere Themen "gekapert" ;-)

Mathematiker · Verfasst: Mo 29.04.13 19:10

Hallo,

Horst_H hat folgendes geschrieben :

Seit wann werden hier die Threads für andere Themen "gekapert" ;-)

Das ist vollkommen ok. :zustimm:

Es ist sehr interessant. Leider kann ich nur wenig beitragen. :cry:

Nebenbei habe ich das Programm noch etwas beschleunigt. (Rev 5)
Zum einen habe ich die Siebgröße nochmals verkleinert, zum zweiten drei Grundsiebe eingeführt, in denen schon alle durch 3 und 5 teilbaren Zahlen ausgesiebt sind.
Auf meinem PC brauche ich jetzt für die Überprüfung von 1 Billion Zahlen etwa 1 Stunde. Ist zwar noch ganz schön viel, aber deutlich besser als am Anfang.
Im Moment habe ich bis 11 Billionen alles getestet und eine neue lonely prime mit 9156364643509 (Abstände 372,340; Intervall [9156364643137;9156364643849]) gefunden.

Beste Grüße
Mathematiker

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

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme