Entwickler-Ecke
Algorithmen, Optimierung und Assembler - Einsame Primzahlen
Mathematiker - Mo 22.04.13 10:42
Titel: Einsame Primzahlen
Hallo,
angeregt durch
IhopeonlyReaders Beitrag zu riesigen Boolean-Feldern
http://www.entwickler-ecke.de/viewtopic.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
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
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.
Tranx - 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! ;)
Mathematiker - 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
http://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.
IhopeonlyReader - Mo 22.04.13 17:43
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")
Mathematiker - 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
IhopeonlyReader - Mo 22.04.13 17:51
| Mathematiker hat folgendes geschrieben : |
Ich kann Dir aber nicht mehr sagen, wo ich den Begriff "einsame Primzahl" erstmals gelesen habe
|
Noch eine neue Aufgabe :D
Delphi-Laie - 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 - 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
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]
Horst_H - 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.
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
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
Gammatester - Fr 26.04.13 10:11
| Horst_H hat folgendes geschrieben : |
| Das Programm kann vielleicht auch für 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:
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).
Mathematiker - 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
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:
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
Mathematiker - Sa 27.04.13 09:07
Hallo,
da es mir keine Ruhe gelassen hat, bin ich heute früh halb 6 aufgestanden :P und habe versucht die guten Ideen von
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
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.
Mathematiker - 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
Horst_H - So 28.04.13 17:01
Hallo,
@
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.
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:
|
|
@
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 - Mo 29.04.13 09:45
| 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 - Mo 29.04.13 12:37
@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 - Mo 29.04.13 14:13
| 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 - Mo 29.04.13 17:00
Gammatester: Die Korrelation zwischen den Zeitergebnissen udn den Differenzen ist sehr gut (siehe Bild):
Horst_H - Mo 29.04.13 18:09
Hallo,
@
Gammatester und
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 - 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
Lelf - Mo 29.04.13 19:49
| Horst_H hat folgendes geschrieben : |
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" ;-) |
Du hast schon recht. Wir sind etwas vom Weg abgekommen. Es waren eben verschiedene Fragen, die aufgetaucht sind und die sollten beantwortet werden. Soll ich mit Miller-Rabin weitermachen?
Gruß Lelf
Mathematiker - So 05.05.13 10:06
Hallo,
das Thema hat sich zwar erledigt, aber vielleicht interessiert es jemanden:
Aktueller Stand (11.5.13): gerechnet bis 42 Billionen
Stand der Berechnung einsame Primzahlen
900 / 21185697626267 / [21185697626083;21185697626983]
Stand der Berechnung lonely primes (vor 5 Minuten gefunden)
426,348 / 26459479056379 / [26459479055953;26459479056727]
Beste Grüße
Mathematiker
Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!