Autor |
Beitrag |
Mathematiker
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
Verfasst: Mi 08.08.12 23:04
Hallo,
wieder einmal ein neues Problem meinerseits. Diese Mal geht es um Primzahlfolgen, konkret um umkehrbare Primzahlfolgen.
1998 wurde eine Folge zehn unmittelbar aufeinanderfolgender Primzahlen veröffentlicht, die alle umkehrbar sind, d.h. dreht man die Ziffern der Zahlen, so entstehen ebenfalls Primzahlen: 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259
Derartige Folgen mit zehn oder mehr Gliedern sind relativ selten. Im Internet habe ich bis jetzt nur von Felice Russo (Mai 1999): {91528739, ..., 91528939} ; 10 Glieder und von Jud McCranie (Mai 1999, im Klammern Startzahl): {302706311} 10 Glieder | {1477271183} 11 Glieder | {1801280717} 10 Glieder | {1811906567} 10 Glieder | {7060718569} 10 Glieder | {9338212141} 10 Glieder | {9387802769} 12 Glieder | {9427522387} 11 Glieder gefunden.
Mein Computer hat bis jetzt neue 10gliedrige Folgen ab {777528457}, {778286917}, {924408493} und {1177842077} ermittelt und dabei alle Zahlen bis 1,4 Milliarden getestet.
Nach 1999 hat sich scheinbar niemand mehr mit dem Problem befasst, zumindest habe ich nichts gefunden. Eine umkehrbare Primzahlfolge mit 13 Gliedern ist wahrscheinlich noch nicht bekannt.
Obwohl ich Gammatesters MP_Arith verwende, ist mein Programm ziemlich langsam. Der Test von 100 Millionen Zahlen größer als 1 Milliarde benötigt mehr als 30 Minuten. Ich vermute, dass das Umkehren der Ziffernfolgen, d.h. die Stringoperationen, am stärksten bremst. Irgendwie mache ich wieder etwas falsch, habe aber im Moment keine Lösungsidee.
Vielleicht findet von Euch jemand eine schnellere Lösung, evtl. sogar eine 13gliedrige Folge.
Der mathematische Ruhm ist Ihm dann sicher!
Beste Grüße
Mathematiker
Einloggen, um Attachments anzusehen!
_________________ Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
|
|
Gammatester
Beiträge: 328
Erhaltene Danke: 101
|
Verfasst: Do 09.08.12 10:08
Es gibt mehre Möglichkeiten, Deinen Code zu beschleunigen. Am wichtigsten: Wenn Du nur bis 1 Milliarde plus ein paar 100 Mio arbeiten willst, solltest Du ganz auf die mp_int verzichten und nur mit mp_prime arbeiten.
Wenn's aber etwas größer sein muß: Im Anhang eine aufgebohrte Unit, die nur ca 30% der Zeit benötigt. Darin zwei Änderungen: while not mp_is_pprime(wx) do mp_add_d(wx,2,wx) wird durch mp_nextprime(wx) ersetzt, und das Umdrehen erfolgt durch Rückwärtseinlesen der Ziffern:
Delphi-Quelltext 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18:
| procedure mp_readrev(const a: ansistring; var b: mp_int); var k: integer; d: mp_digit; begin mp_zero(b); for k:=length(a) downto 1 do begin case a[k] of '0'..'9': begin mp_mul_d(b,10,b); mp_add_d(b,ord(a[k])-ord('0'),b); end; else exit; end; end; end; |
In der Unit selbst ist noch die procedure mp_rev10, die ein mp_int direkt umdreht. Aber da Du eh immer den String erzeugst, ist es mit readrev etwas schneller.
Gruß Gammatester
PS: Seit Montag gibt's die neue MPArith V1.21.35! Nochmals Dank an Mathematiker, Delphi-Laie, und Horst_H für die Anregungen.
Einloggen, um Attachments anzusehen!
Für diesen Beitrag haben gedankt: Mathematiker
|
|
Horst_H
Beiträge: 1653
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Do 09.08.12 11:29
Hallo,
bremst wirklich mp_readrev so stark?
Dann würde ich doch mp_digit voll ausnutzen wollen.
UNGETESTET:
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:
| procedure mp_readrev(const a: ansistring; var b: mp_int); var i, k: integer; d: mp_digit; begin mp_zero(b); i := a; k := a div 9; for k:=k downto 1 do begin d := (ord(a[i ])-ord('0')); d := 10*d+(ord(a[i-1])-ord('0')); d := 10*d+(ord(a[i-2])-ord('0')); d := 10*d+(ord(a[i-3])-ord('0')); d := 10*d+(ord(a[i-4])-ord('0')); d := 10*d+(ord(a[i-5])-ord('0')); d := 10*d+(ord(a[i-6])-ord('0')); d := 10*d+(ord(a[i-7])-ord('0')); d := 10*d+(ord(a[i-8])-ord('0')); mp_mul_d(b,1000000000,b); mp_ad_d(b,d,b); dec(i,9); end; k := 1; d := 0; For i := i downto 0 do begin d := 10*d + (ord(a[i])-ord('0')); k := k*10; end; mp_mul_d(b,k,b); mp_ad_d(b,d,b); end; |
Gruß Horst
|
|
Gammatester
Beiträge: 328
Erhaltene Danke: 101
|
Verfasst: Do 09.08.12 12:18
Horst_H hat folgendes geschrieben : | Hallo, bremst wirklich mp_readrev so stark?
|
Nein eigentlich nicht, es beschleunigt doch. Das Bremsen bezog sich auf die Situation ohne Stringumwandlung. Deine Idee in lauffähigen Code umgesetzt braucht ca 6% weniger Zeit als mp_readrev:
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:
| procedure mp_readrev2(const a: ansistring; var b: mp_int); var k: integer; d,s: mp_digit; const dm = MP_DIGIT_MAX div 10; begin mp_zero(b); d := 0; s := 1; for k:=length(a) downto 1 do begin case a[k] of '0'..'9': begin if s>dm then begin mp_mul_d(b,s,b); mp_add_d(b,d,b); d := 0; s := 1; end; d := d*10 + ord(a[k])-ord('0'); s := s*10; end; else exit; end; end; if d>0 then begin mp_mul_d(b,s,b); mp_add_d(b,d,b) end; end; |
Gruß Gammatester
|
|
Mathematiker
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
Verfasst: Do 09.08.12 13:38
Hallo Gammatester,
Gammatester hat folgendes geschrieben : | In der Unit selbst ist noch die procedure mp_rev10, die ein mp_int direkt umdreht. Aber da Du eh immer den String erzeugst, ist es mit readrev etwas schneller. |
Mit Deiner Routine und einer neuen Idee habe ich einen deutlichen Geschwindigkeitsgewinn erzielt.
Zum einen bilde ich erst im Erfolgsfall den Ausgabestring, d.h. procedure mp_rev10 ist jetzt optimal.
Zum anderen: Wenn ich nach einer 10gliedrigen Kette suche, teste ich ab der 10.Primzahl rückwärts die gedrehte Zahl. Ergibt sich eine zusammengesetzte Zahl, rechne ich in der nächsten Runde ab der kleinsten gefundenen umkehrbaren Primzahl.
Wunderbar. Damit werden viele, viele Algorithmen noch schneller ablaufen.
Einen "unverschämten" Wunsch habe ich aber noch: Faktorisierung mit einem Zahlkörpersieb wäre wunderschön.
Beste Grüße
Mathematiker
Einloggen, um Attachments anzusehen!
_________________ Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
|
|
Horst_H
Beiträge: 1653
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Do 09.08.12 14:38
Hallo,
was mir noch aufgefallen ist
Delphi-Quelltext 1: 2: 3: 4: 5:
| mp_miller_rabin(wx,1,prim); while not prim do begin mp_add_d(wx,2,wx); mp_miller_rabin(wx,1,prim); end; |
Wieder wird jede 2.te Zahl auf prim getestet.
Das muss nicht sein, siehe Primvierer.( hoffe ich zumindest )
Die Stringumwandlung mp_decimal kann man sich in der Schleife sparen.
Delphi-Quelltext
"an" ist ja edit1.text
Man kann auch auf Ziffernstrings die Addtion implementieren.Es werden ja nur kleine Zahlen addiert.
Zusätzlich zu mp_add_d müsste parallel StrAdd durchgeführt werden.
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:
| {$IFDEF FPC} {$MODE DELPHI} {$ENDIF}
procedure StrAdd(var K: AnsiString;kleineZahl:integer); var i,r,ziffer : integer; begin IF KleineZahl <= 0 then begin IF K ='' then k := '0'; Exit; end; i := length(k); IF i = 0 then begin k := '0'; i :=1; end; while (KleineZahl > 0) do begin r := KleineZahl div 10; Ziffer := kleineZahl - 10*r; KleineZahl := r; Ziffer := Ord(k[i])+Ziffer; If Ziffer > Ord('9') then begin inc(KleineZahl); dec(Ziffer,10); end; k[i] := chr(Ziffer); dec(i); IF (KleineZahl<>0) AND (i = 0) then begin k := '0'+k; inc(i); end; end; end;
var z : Ansistring; i: integer; Begin z := '9999999999999444444445'; For i := 1 to 11 do begin StrAdd(z,555555555); writeln(i:4,' ',z); end; end. |
Gruß Horst
Für diesen Beitrag haben gedankt: Mathematiker
|
|
Gammatester
Beiträge: 328
Erhaltene Danke: 101
|
Verfasst: Do 09.08.12 14:50
Mathematiker hat folgendes geschrieben : |
Zum einen bilde ich erst im Erfolgsfall den Ausgabestring, d.h. procedure mp_rev10 ist jetzt optimal.
Zum anderen: Wenn ich nach einer 10gliedrigen Kette suche, teste ich ab der 10.Primzahl rückwärts die gedrehte Zahl. Ergibt sich eine zusammengesetzte Zahl, rechne ich in der nächsten Runde ab der kleinsten gefundenen umkehrbaren Primzahl. |
Sinnvoll, dann werden einige Ketten auch nicht mehrfach ausgegeben wie in der ersten Version (ich dachte schon, mein D6 hat falsch übersetzt, weil weniger gelistet wurde).
Im Anhang noch eine kleine Verbesserung von ca 15%: Wenn a in mp_rev10 im Longintbereich ist, wird die Reverse schnell berechnet. Außerdem habe ich mp_miller_rabin(wx2,1,prim) durch prim := mp_is_pprime(wx2) ersetzt; das bringt zwar nicht viel, aber Miller/Rabin sollte nur in begründeten Ausnahmefällen benutzt werden (zB wenn man schon weiß, daß die Zahl keine kleinen Primfaktoren hat).
Gruß Gammatester
Einloggen, um Attachments anzusehen!
Für diesen Beitrag haben gedankt: Mathematiker
|
|
Mathematiker
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
Verfasst: Do 09.08.12 15:12
Hallo Horst_H,
Horst_H hat folgendes geschrieben : | Wieder wird jede 2.te Zahl auf prim getestet. Das muss nicht sein, siehe Primvierer.( hoffe ich zumindest ) |
Deinen Hinweis zu Primzahlvierlingen habe ich schon getestet. Ich dachte zuerst, ein schnelles Primzahlsieb würde die Zeit erheblich verringern. Es klappte nicht. Warum, kann ich noch nicht sagen, mal sehen ob ich noch eine gute Idee habe.
Beste Grüße
Mathematiker
_________________ Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
|
|
Gammatester
Beiträge: 328
Erhaltene Danke: 101
|
Verfasst: Do 09.08.12 15:39
Noch ein kleiner Bugfix. Beim Longint-Rev10 kann es leider für a > 1000000000 passieren, daß die Reverse kein gültiges Longint ist (habe ich bemerkt als eine Deiner 10-Ketten nicht gefunden wurde). Mit dem Fix wird sie gefunden, außerdem (angeblich) noch weitere 10-Ketten: bei {147727118}, {1801280717}, {1811906567}.
Gruß Gammatester
Einloggen, um Attachments anzusehen!
|
|
Mathematiker
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
Verfasst: Do 09.08.12 16:16
Hallo Gammatester,
Gammatester hat folgendes geschrieben : | Mit dem Fix wird sie gefunden, außerdem (angeblich) noch weitere 10-Ketten: bei {147727118}, {1801280717}, {1811906567}. |
Diese sind vollkommen korrekt. Das sind die von Jud McCraine 1999 veröffentlichten.
Mein (langsamer) Computer hat im Moment alle Zahlen bis 3,2 Milliarden getestet. Eigentlich will ich noch bis mindestens 10 Milliarden kommen, was allerdings Tage dauern würde.
Beste Grüße
Mathematiker
_________________ Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
|
|
Gammatester
Beiträge: 328
Erhaltene Danke: 101
|
Verfasst: Do 09.08.12 16:27
Habe jetzt mal nach "9427522387" "Jud" gesucht und folgende Seite gefunden, wo auch 13-Ketten beschrieben werden: www.primepuzzles.net/problems/prob_017.htm
Gruß Gammatester
|
|
Mathematiker
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
Verfasst: Do 09.08.12 16:48
Hallo Gammatester,
Nun gut, in die Bereiche der 13gliedrigen Folgen werde ich dann mit meinem Programm nicht vorstoßen können.
Programmtechnisch bleibt es aber immer noch eine Herausforderung.
Die Seite www.primepuzzles.net ist sehr interessant; kannte ich noch nicht. Nach dem ersten Überblick gibt es dort viele schöne Aufgabenstellungen.
Beste Grüße
Mathematiker
_________________ Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
|
|
Horst_H
Beiträge: 1653
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Do 09.08.12 17:17
Hallo,
hat jemand schon herausbekommen, was denn besonders bremst.
Wie ich schon geschrieben habe kann man mp_decimal durch StrAdd gut ersetzt werden.
100Mio mal 2 addiert dauert bei mir 2,6 Sekunden auf dem Notebook-> 60 CPU-Takte für eine Addition.Wenn man 99 addiert, sind es auch nur 5,15 Sekunden -> 118 Takte
Und das Beste: Diese Zahlen sind unabhängig vor der Gesamtlänge des Strings, denn es wirkt selten bis in die Spitze, sprich das überall 9en vorne stehen.
Die erste und die 13.te Primzahl sind nur 296 auseinander
1 15423094826093 39062849032451
...
13 15423094826389 98362849032451
Also die Ersetzung sähe so aus:
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:
| k := edit1.text; mp_mod_int(wx,2,rest); if rest=0 then begin mp_add_d(wx,1,wx); StrAdd(k,1); end; repeat mp_miller_rabin(wx,1,prim); while not prim do begin mp_add_d(wx,2,wx); StrAdd(k,2); mp_miller_rabin(wx,1,prim); end; mp_copy(wx,wx3); q:=0;
mp_readrev(k,??); ... |
Gruß Horst
|
|
Mathematiker
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
Verfasst: Do 09.08.12 17:42
Hallo Horst_H
Horst_H hat folgendes geschrieben : | hat jemand schon herausbekommen, was denn besonders bremst.
Wie ich schon geschrieben habe kann man mp_decimal durch StrAdd gut ersetzt werden. |
Das mp_decimal/StrAdd ist es nicht mehr, das bremst, da in der Variante upfolge2, bzw. in der durch Gammatester veränderten Variante upfolge2_we, die Umwandlung in Strings nur noch erfolgt, wenn eine Primzahlfolge gefunden wurde.
Scheinbar bremst der Primzahlnachweis am stärksten. Genau weiß ich es aber nicht.
Beste Grüße
Mathematiker
_________________ Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
Zuletzt bearbeitet von Mathematiker am Do 18.10.12 21:45, insgesamt 1-mal bearbeitet
|
|
Delphi-Laie
Beiträge: 1600
Erhaltene Danke: 232
Delphi 2 - RAD-Studio 10.1 Berlin
|
Verfasst: Do 09.08.12 22:22
Horst_H hat folgendes geschrieben : |
Wieder wird jede 2.te Zahl auf prim getestet.
Das muss nicht sein, siehe Primvierer.( hoffe ich zumindest ) |
Anscheinend funktioniert es auch im Wechsel der Differenz 2 und 4, s. den zweiten Algorithmus unter
www.swissdelphicente.../showcode.php?id=914.
Allerdings muß der Divisor mit 5 anfangen, nicht mit 3, dann stimmt es. Ich probierte es mit niedrigen Zahlen aus, es scheint korrekt zu sein (ja, das ist kein Beweis). Keine Ahnung, woher Hagen das hat. Es offenbart jedenfalls zudem eine weitere interessante Gesetzmäßigkeit in der Primzahlverteilung.
Zuletzt bearbeitet von Delphi-Laie am Do 09.08.12 22:46, insgesamt 1-mal bearbeitet
|
|
Mathematiker
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
Verfasst: Do 09.08.12 22:29
Hallo Delphi-Laie
Besten Dank für den Hinweis. Der Primzahltest von Hagen Reddmann ist sehr schnell und korrekt! Ich kenne ihn schon, habe ihn schon verwendet, aber hier darauf verzichtet, da ich eigentlich den Int64-Bereich überschreiten wollte; d.h. auf eine Langzahlarithmetik kann ich nicht verzichten.
Da es im Moment so aussieht, als ob ich die 1 Billion niemals(?) überschreiten kann, werde ich morgen testen, wie schnell es ohne Langarithmetik geht.
Beste Grüße
Mathematiker
_________________ Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
|
|
Horst_H
Beiträge: 1653
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Do 09.08.12 22:35
Hallo,
NextPrime nutzt sogar eine Folge von Zahlen, die Teilerfremd zu 2,3,5,7 sind, da bleiben von 210=2*3*5*7 nur mehr 48= (2-1)*(3-1)*(5-1)*(7-1) übrig.
Ich habe mal Ticks gestoppt:
Also nextprim und MillerRabin sind die Bremsen.
Da muss was schnelleres her
Gruß Horst
Edit
StrAdd hat zwischendurch 2*Runden addiert, deshalb ist die 3 eine 5 geworden.
Edit2:
Man müßte für nextprim doch ein Sieb nutzen können, wenn dieses gespeichert wäre.in mp_arith sind doch die kleinen Primzahlen bis 16-Bit enthalten.
Das müßte dann in mp-arith stecken und verwaltet werden.
In der Art
procedure mp_sieve_init(const mp:mp-variable);
procedure get_next_sieveprime(out mp:mp-Variable):boolean;//falls vorher free
procedure mp_sieve_free;
Einloggen, um Attachments anzusehen!
|
|
Gammatester
Beiträge: 328
Erhaltene Danke: 101
|
Verfasst: Fr 10.08.12 09:18
Nur zwei Bemerkungen zu der Diskussion, immer vorausgesetzt wird betrachten Zahlen > 2^31-1:
1. Ich weiß nicht wie oft ich es jetzt schon gesagt habe: Miller-Rabin sollte nur in begründeten Ausnahmefällen benutzt werden! Es wird immer ein starker Pseudoprimzahltest mit Zufallsbasis gemacht, auch wenn die Zahl zB durch 7 teilbar ist. Und weil es relativ langsam ist, nehmt ihr dann nur eine Basis, das ist wiederum schlecht für den (wahrscheinlichen) Nachweis der Primzahleigenschaft. Also: Normalerweise immer mp_is_pprime verwenden.
2. Primzahlenfinden ist langsam! Sieben bringt etwas, aber nicht soviel wie man vielleicht denkt. Vor 6 Jahren habe ich das mal gezeitet und mich dann für mp_nextprime als Standard entschieden: Hier ein paar Zeiten für die ersten 6 (sechs!) Primzahlen mit 1024 Bit:
Quelltext 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11:
| Test of MP library V1.22.03 (31/32 bit) (c) W.Ehrhardt 2006 nextsievex: ......Time [s]: 6.851 mp_Prime_Next_Prime: ......Time [s]: 12.428 mp_nexxxt: ......Time [s]: 8.281 mp_nextprime: ......Time [s]: 7.797 nextprime: ......Time [s]: 6.329 nextsieve: ......Time [s]: 6.939 nextsievew2: ......Time [s]: 6.932 nextsievew3: ......Time [s]: 6.932 nextsievew4: ......Time [s]: 6.038 nextsievew6: ......Time [s]: 6.040 | Der genaue Code ist nicht sonderlich interessant (zB verwenden die Siebversionen nextsievew4/6 Primzahlen bis 818143).
Gruß Gammatester Moderiert von Narses: Beiträge zusammengefasst Delphi-Laie hat folgendes geschrieben : | Keine Ahnung, woher Hagen das hat. Es offenbart jedenfalls zudem eine weitere interessante Gesetzmäßigkeit in der Primzahlverteilung. |
Wenn sich jemand wundert, woher die magischen Zahlen 31, 61, 73, 9080191 usw. in Hagens Code stammen: Sie kommen aus einem Artikel von Gerhard Jaeschke aus dem Jahre 1993 (On strong pseudoprimes to several bases, Abschnitt 5. Other bases than the first primes). Der Test (und weitere) werden zB beschrieben auf primes.utm.edu/prove/prove2_3.html
Mathematiker hat folgendes geschrieben : | Der Primzahltest von Hagen Reddmann ist sehr schnell und korrekt! Ich kenne ihn schon, habe ihn schon verwendet, aber hier darauf verzichtet, da ich eigentlich den Int64-Bereich überschreiten wollte; d.h. auf eine Langzahlarithmetik kann ich nicht verzichten.
Da es im Moment so aussieht, als ob ich die 1 Billion niemals(?) überschreiten kann, werde ich morgen testen, wie schnell es ohne Langarithmetik geht. |
Hagens Test ist nur gültig für Zahlen < 4759123141, reicht also für UInt32 = 32Bit-Cardinal. Für größere Zahlen kann man einen anderen Mehrfach-SPSP-Test nehmen. Für die Grenze 1 Billion reichen vier SPSP-Tests: If n < 21,652,684,502,221 is a 2, 1215, 34862, and 574237825-SPRP, then n is prime.. Dann allerdings sinnvollerweise mit Int64-Arithmetik, wobei die grundlegenden Sachen neu zu schreiben sind; besondere Vorsicht ist dabei für expmod geboten, dabei muß man Zahlen der Größenodnung n^2 verarbeiten (im Extremfall braucht man also 128-Bit-Arithmetik oder muß sich mit langsamen Shiftschleifen durchhangeln).
Gruß Gammatester
Für diesen Beitrag haben gedankt: Delphi-Laie
|
|
Mathematiker
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
Verfasst: Sa 11.08.12 13:03
Gammatester hat folgendes geschrieben : | Miller-Rabin sollte nur in begründeten Ausnahmefällen benutzt werden! |
Verstehe ich. Deshalb ist im letzten veröffentlichten upfolge2.pas auch mp_is_pprime drin.
Gammatester hat folgendes geschrieben : | Primzahlenfinden ist langsam[/b]! Sieben bringt etwas, aber nicht soviel wie man vielleicht denkt. |
Ein Primzahlsieb, wie ich es bei den Vierlingen genutzt habe, bringt hier nichts. Das habe ich schon getestet.
Zwar kann man die Primzahlen der Folge ermitteln, aber die umgekehrten Zahlen sind immer noch mit einem Primzahltest zu prüfen.
Im Moment denke ich, dass mit Gammatesters mp_rev10, vorerst die "schnellste" Variante in upfolge2.pas gefunden ist.
Irgendwie fehlt eine neue, zündende Idee.
Beste Grüße
Mathematiker
_________________ Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
|
|
Horst_H
Beiträge: 1653
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Sa 11.08.12 13:33
Hallo,
selbst bei 1 Billionen bewegen sich die Zahlen doch in einem kleinen Bereich, deshalb denke ich, das sieben den Prozess von Nextprime beschleunigt.
Mal als Modell mit sieben aller Primzahlen P16 < 65536.
Ein Bitfeld der Länge 510510 Bit erstellen Bit 0 entspricht der Startzahl mod 510510 . Den Offset jeder P16 in dieses Feld. p16_Ofs = Startzahl mod P16.
Mit der Zahl P16 ab p16_Ofs in Schrittweite P16 sieben bis der wert > 510510 ist und den Übertrag als neuen Ofs Speichern.
Das 6542 mal machen und man hat für die nächsten 510509 Zahlen ab Startzahl diese schon durch alle Primzahlen < 65536 probedividiert.
Nur wenn eine Zahl/ Bit in diesem Sieb noch als vielleichtprim übrigbleibt und damit teilerfremd zu den P16 ist, wird diese mit mp_is_pprime getestet.
Das Sieb kann man ja beliebig verbessern indem nur zu 2,3,5,7.. teilerfremde Zahlen gespeichert werden, oder ein Sieb, indem alle vielfachen von 2,3,5,7,11,13,17 ausgestrichen sind etc pp.
Das man die umgekehrte Folge sind mit sieben erfassen kann ist einleuchtend.
|
|
|