| |
| Autor |
 Primzahleneigenschaften |
| | Folgende Antworten hat der Fragensteller vermutlich noch nicht gesehen. |
hyperG
Senior 
Dabei seit: 03.02.2017
Mitteilungen: 2158
 |  Beitrag No.213, eingetragen 2017-02-19
|
Wenn ich schon wieder höre "Wenn ...ehrlich gerechnet" und "Stützwerte"...
Na dann lasst uns doch mal alle 4 Sprachen vergleichen, ABER diesmal "oben herum",
also da, wo es (noch) keine Stützwerte gibt. :
\sourceon JAVA
...
bi3 = new BigInteger("58310039994836584070534263");
gegIndex=1000000000000000000000000L;
gesIndex=1000000000000000010000000L;
long offs=gesIndex-gegIndex;
for(c2 = 0; c2 < offs; c2++)
{ bi3 = bi3.nextProbablePrime();
}
System.out.println("Prime("+(gesIndex)+")="+bi3+" in "+(System.currentTimeMillis()-seed)+"ms");
Output:
Prime(1000000000000000010000000)=58310039994836584663869571 in 3843660 ms =64 min
\sourceoff
fehlen noch:
Maple\nextprime:
Mathematica:
c++\mpz_nextprime(p,p):
Sobald jemand was anderes herausbekommt, kann die Suche nach der Fehlerquote beginnen. Laut JAVA liegt sie bei nextProbablePrime unterhalb 2^(-100).
Und NEIN, ich bin eigentlich kein Fan von JAVA, aber nextProbablePrime scheint wirklich gut gelungen.
c# kann nur 2^(-60) -> könnte man auch vergleichen...
|
 Profil
|
matph
Senior 
Dabei seit: 20.11.2006
Mitteilungen: 5506
Wohnort: A
 | Beitrag No.214, eingetragen 2017-02-19
|
Hallo,
\sourceon GP/PARI
p()={r=58310039994836584070534263;for(i=0,9999999,r=nextprime(r+1));print(r)}
\sourceoff
58310039994836584663869571
time = 8min, 55,719 ms.
--
mfg
matph
|
Profil
|
weird
Senior 
Dabei seit: 16.10.2009
Mitteilungen: 5301
 | Beitrag No.215, eingetragen 2017-02-19
|
Ok, hier der Vollständigkeit halber auch noch die Rechnung in Maple, welche allerdings für das gleiche Resultat fast 97 min auf meinem Rechner benötigt:
\sourceon Maple 2015
p0:=58310039994836584070534263:
testprime:=proc(m:=10^4,a:=p0)
local k,p:=a;
for k to m do p:=nextprime(p) end do;
return p
end:
t:=time():testprime(10^7),(time()-t)*'s'
58310039994836584663869571, 5816.406 s
\sourceoff
Die Frage ist nur, was genau soll damit bewiesen werden? :-?
|
Profil
|
hyperG
Senior 
Dabei seit: 03.02.2017
Mitteilungen: 2158
| Beitrag No.216, eingetragen 2017-02-19
|
Hallo matph,
habe mir extra die Mühe gemacht und mich in c++ mit gmp.DLL eingearbeitet:
\sourceon c++32Bit
mpz_init_set_str (p, "58310039994836584070534263", 10);
begin = cputime();
for(i=0; i<10000000; ++i) mpz_nextprime(p,p);
mid0 = cputime();
printf("time = %7.3f s\nPrime(1000000000000000010000000)=", (double)(mid0-begin)/1000);
gmp_printf("%Zd\n",p);
Out:
time = 1877.607 s = 31 min Prime(1000000000000000010000000)=58310039994836584663869571
\sourceoff
Leider habe ich nur die fertige alte 32-Bit gmp.dll gefunden.
Zwar gibt es auch den gcc-Code, aber für Visual Studio 12 extrem aufwendig anzupassen.
Es gibt auch zig Seiten, die einem "Ihre DLL" andrehen wollen, aber da ist dann meist was anderes
"mit drin" was man nicht haben will (sieht man schon an der Größe).
Wo bekommt man eine neue (Version 6) seriöse gmp.DLL und lib Datei für x64 Windows her?
Das GP/PARI (oder Dein PC?) ist ja nochmal 3,5 mal schneller!
Werde ich mir mal ansehen...
[Die Antwort wurde nach Beitrag No.214 begonnen.]
|
Profil
|
matph
Senior
Dabei seit: 20.11.2006
Mitteilungen: 5506
Wohnort: A
| Beitrag No.217, eingetragen 2017-02-19
|
Hallo,
Für die GNU Multiple Precision Arithmetic Library würde ich empfehlen, den gcc zu verwenden, hier die entsprechenden Links: :-) --
mfg
matph
|
Profil
|
hyperG
Senior
Dabei seit: 03.02.2017
Mitteilungen: 2158
| Beitrag No.218, eingetragen 2017-02-19
|
Super: alle 4 das gleiche Ergebnis -> ein grober Fehler war also nicht dabei...
@weird:
Ich weiß, dass wir mit unseren Tests hier den Weg der "schönen Formeln" verlassen.
Zweifelst Du am Ergebnis Prime(1000000000000000010000000)=58310039994836584663869571
? Vermutest Du doch noch Pseudoprimzahlen, also Fehler?
Kennst Du Programme oder Internetseiten, wo jemals so ein großer Wert der Funktion Prime(x)
veröffentlicht oder berechnet wurde?
Ich habe keine teuren Programme wie maple oder Mathematica... und selbst die brauchen meist mehr Zeit als c optimierte Programme.
Außerdem ist dieser Geschwindigkeitsvergleich schon sehr interessant:
\sourceon Tabelle
GP/pari 8,9 min
c++GMPx32 31,3 min
JAVA 64,0 min
maple 96,9 min
\sourceoff
Wenn man sich schon auf lange Wartezeiten einstellt, dann doch wenigstens die kürzesten...
@matph: Danke für die LINKs.
[Die Antwort wurde nach Beitrag No.216 begonnen.]
|
Profil
|
weird
Senior
Dabei seit: 16.10.2009
Mitteilungen: 5301
| Beitrag No.219, eingetragen 2017-02-20
|
\quoteon(2017-02-19 19:01 - hyperG in Beitrag No. 218)
\sourceon Tabelle
GP/pari 8,9 min
c++GMPx32 31,3 min
JAVA 64,0 min
maple 96,9 min
\sourceoff
\quoteoff
LOL, eine Tabelle mit Rechenzeiten und mein Programm Schlusslicht, davon hast du wohl schon immer geträumt, was? :-D
Aber wie schon bei unseren Primzahlformeln vergleichst du halt wieder einmal "Äpfel mit Birnen". Es ist dir egal, welche Programmiersprache verwendet wurde, es ist dir egal, wie schnell die Rechner sind, auf denen die Programme laufen, es ist dir vor allem egal, wie stark die intern verwendeten Primzahltests sind, Hauptsache man kann am Ende eine so schöne Tabelle wie die obige produzieren. :-(
Aber ok, weißt du was, ich schreib jetzt das Ganze mal schnell ein bißchen um, und zwar wie folgt:
\sourceon Maple 2015
p0:=58310039994836584070534263:
testprime:=proc(n,p0,b:=100000)
local a:=p0,k:=n,p:=a,d:=2,m:=102481630431415235;
if a1 then next end if;
if 2&^(p-1) mod p=1 then
k:=k-1; if k=0 then return p end if
end if
end do;
end:
t:=time():testprime(10^7,p0),(time()-t)*'s'
58310039994836584663869571, 562.547 s
\sourceoff
Unter 10 min, also dann nur wenig schlechter wie das Pari-Programm, und das, obwohl ich da noch nicht einmal tief in meine Trickkiste greifen musste! Du siehst also hoffentlich selbst, wie lächerlich deine Geschwindigkeitsvergleiche sind, wenn einfach alles erlaubt ist, solange nur am Ende das "Richtige" dabei herauskommt! :-o
Edit: Hab das Programm zu Kontrollzwecken mit copy-paste auf eine ganz neue Seite kopiert und nochmals laufen lassen, wodurch sich die Rechenzeit noch einmal auf 518.797s verringert hat, d.h., das Programm hat sich damit sogar an die Spitze obiger Liste gesetzt, falls man diese jetzt wirklich ernst nehmen würde. :-D
|
Profil
|
Primentus
Senior
Dabei seit: 18.02.2016
Mitteilungen: 2179
Wohnort: Deutschland
 | Beitrag No.220, eingetragen 2017-02-20
|
\quoteon(2017-02-19 08:44 - weird in Beitrag No. 212)
Da bin ich aber froh, denn Goto-Befehle sind eigentlich unter Programmierern ein absolutes No-Go. :-D
\quoteoff
Ja, ich weiß, Goto-Befehle sind schlechter Programmierstil, aber das Continue macht ja eigentlich sinngemäß auch nichts anderes (nämlich zum Ende einer Schleife zu springen). Aber an der Stelle braucht man es halt wohl.
\quoteon(2017-02-19 08:44 - weird in Beitrag No. 212)
Das hängt aber wirklich nur mit der Syntax dieser Sprache zusammen, die für mich extrem "antiintuitiv" ist, ansonsten ist sie natürlich sehr mächtig. Und ja, was jetzt die Liebe zum jeweiligen CAS betrifft, da haben wir ja echt was gemeinsam. ;-)
\quoteoff
Bei mir war Mathematica das erste CAS, mit dem ich in Berührung gekommen bin. Von daher hab ich die Syntax von Anfang an so hingenommen wie sie war und habe damit nie Probleme gehabt. Etwas ungewöhnlich sind vielleicht die eckigen statt runden Klammern, aber ansonsten finde ich das allermeiste dort schon recht intuitiv. Aber was die Liebe zum jeweiligen CAS betrifft - da haben wir wohl wirklich was gemeinsam, ja. :-) Aber auch allgemein finde ich das Konzept eines CAS sehr interessant. Das sind schon sehr mächtige Programme.
\quoteon(2017-02-20 08:40 - weird in Beitrag No. 219)
\quoteon(2017-02-19 19:01 - hyperG in Beitrag No. 218)
\sourceon Tabelle
GP/pari 8,9 min
c++GMPx32 31,3 min
JAVA 64,0 min
maple 96,9 min
\sourceoff
\quoteoff
LOL, eine Tabelle mit Rechenzeiten und mein Programm Schlusslicht, davon hast du wohl schon immer geträumt, was? :-D
Aber wie schon bei unseren Primzahlformeln vergleichst du halt wieder einmal "Äpfel mit Birnen". Es ist dir egal, welche Programmiersprache verwendet wurde, es ist dir egal, wie schnell die Rechner sind, auf denen die Programme laufen, es ist dir vor allem egal, wie stark die intern verwendeten Primzahltests sind, Hauptsache man kann am Ende eine so schöne Tabelle wie die obige produzieren. :-(
\quoteoff
Das kann ich nur absolut unterstreichen, was die "Äpfel mit Birnen" betrifft. Eigentlich müsste man solche Tests an ein- und demselben Rechner durchführen und die Algorithmen müssten alle so gleich bzw. ähnlich wie möglich geschrieben sein. Teilweise ist es aber schwer, unterschiedliche Programmiersprachen miteinander zu vergleichen, weil man einfach nicht weiß, welche Algorithmen hinter den Standardfunktionen stecken, und nicht jede Funktion gibt es in jeder Sprache.
Nichtsdestotrotz hab ich aber auch mal eine Zeitmessung in obigem Sinne gemacht. Ich nutze allerdings eine schon ältere Version von Mathematica, in der es noch keine NextPrime[]-Funktion gibt. Insofern hinkt der Vergleich natürlich gewaltig. Aber ich habe die Funktion mal mit Hilfe der PrimeQ[]-Funktion nachprogrammiert, was aber sicherlich nicht so effizient ist, wie eine Standardfunktion NextPrime[] es wäre. Keine Sorge, weird, jetzt bin ich das neue Schlusslicht, da Mathematica hier doch gehörige Zeit rechnete:
\sourceon Mathematica
NextPrime[n_] :=
Module[{i}, i = n + 1; While[PrimeQ[i] === False, i = i + 1]; Return[i]]
TestPrime[n_] :=
Module[{r = n}, For[i = 1, i <= 10^7, i++, r = NextPrime[r]]; Return[r]]
Timing[TestPrime[58310039994836584070534263]]
\sourceoff
Ergebnis:
\sourceon Mathematica
{32250.8 Second, 58310039994836584663869571}
\sourceoff
Wie man sieht, dauerte es ca. 537,5 Minuten.
Aber ich hab auch noch eine alte MuPAD-Version, in der ich auch mal die Berechnung durchgeführt habe. Hier gibt es sogar eine nextprime()-Funktion.
\sourceon MuPAD
t1:=time(); r:=58310039994836584070534263; for i from 1 to 10^7 do r:=nextprime(r+1) end_for; t2:=time(); print(t2-t1);
\sourceoff
Hier dauerte es ca. 23940 Sekunden, was 399,0 Minuten entspricht, und es wurde auch das richtige Ergebnis ausgegeben (58310039994836584663869571).
Auf einem aktuellen schnellen Rechner dürften beide Zeiten jedoch ca. 30 % schneller sein.
LG Primentus
|
Profil
|
hyperG
Senior
Dabei seit: 03.02.2017
Mitteilungen: 2158
| Beitrag No.221, eingetragen 2017-02-20
|
\quoteon(weird - Beitrag No.219, eingetragen 2017-02-20 08:40)
"davon hast du wohl schon immer geträumt" ...
"egal, wie schnell die Rechner sind, auf denen die Programme laufen, es ist dir vor allem egal, wie stark die intern verwendeten Primzahltests sind, Hauptsache man kann am Ende eine so schöne Tabelle wie die obige produzieren"
\quoteoff
Das geht ja schon unter die Gürtellinie!
Natürlich sind die PCs alle unterschiedlich schnell - ABER nicht FAKTOR 10 sondern nur ein paar Prozente!
Natürlich schnitt das GP/pari extrem gut ab. -> das werde ich noch genauer untersuchen...
ABER für das c++GMPx32 mit mpz_nextprime kann ich folgende Fakten benennen:
- es liefert um 189452997113368438678230 und um 3317044064679887385961980 richtige Werte!
- mit einer neueren GMP.dll konnte ich die Zeit noch von 31 min auf 18,2 min verbessern!!
- es kann durch Umstieg auf 64 Bit und weitere Optimierungen noch verbessert werden
Damit man Deinen GCD-Algorithmus objektiv vergleichen kann, habe ich ihn auf die Schnelle ohne große Optimierung
mit GMP umgesetzt:
\sourceon c++ GMP
mpz_init_set_str (mpzI, "1000000000000000000000000", 10);mpz_init_set_str (p, "58310039994836584070534263", 10);
unsigned long int k=10000000;
mpz_init_set_str (m, "102481630431415235", 10);mpz_init_set_ui(mpz2,2);mpz_init_set_ui(mpzH,0);
unsigned long int d=2,mod6=6;mpz_add_ui(mpzI,mpzI,k);begin = cputime();
mpz_mod_ui(mpzH, p, mod6);
while((mpz_cmp_ui(mpzH,1)!=0)&&(mpz_cmp_ui(mpzH,5)!=0)){mpz_sub_ui(p,p,1);mpz_mod_ui(mpzH, p,mod6);};
if(mpz_cmp_ui(mpzH,1)==0) {d=4;}
while(true){
mpz_add_ui(p,p,d);d=6-d;mpz_gcd(mpzH,p, m);
if(mpz_cmp_ui(mpzH,1)<=0)
{ mpz_sub_ui(mpzH,p,1);mpz_powm(mpzH,mpz2,mpzH,p);
if(mpz_cmp_ui(mpzH,1)==0) {k--;if(k==0) break; }
}
}
mid0 = cputime();printf("time = %7.3f s\n", (double)(mid0-begin)/1000);
gmp_printf("Prime(%Zd)=%Zd\n",mpzI,p);
Output: time = 680 s Prime(1000000000000000010000000)=58310039994836584663869571
\sourceoff
Also grob 11 min ohne jegliche Optimierung - also nur minimal langsamer als Dein PC, was an meinen 9 Jahre alten PC liegen kann.
Dieser GCD-Abkürzungs-Algorithmus liefert jedoch schon bei 3317044064679887385961980
das falsche Ergebnis 3317044064679887385961981=1287836182261 * 2575672364521 !!
Er trickst so enorm, dass man damit nicht in "unbekannte Bereiche" vorstoßen sollte -> und man kann ihn damit NICHT in den NextPrime-Geschwindigkeitsvergleich mit aufnehmen!
Es gibt also 2 Geschwindigkeitsvergleichs-Tabellen, die man natürlich noch auf den selben PC relativieren müsste:
\sourceon Tabelle NextPrime 10^7 mal um 10^24
GP/pari 8,9 min
c++GMPx32 18,2 min {neuere DLL}
JAVA 64,0 min
maple 96,9 min
mathematica 500 min {grob abgerundet, da alter PC)
\sourceoff
\sourceon Tabelle GCD-Abkürzung 10^7 mal um 10^24
maple 9,4 min
c++GMPx32 11 min {ohne Optimierung}
\sourceoff
Ich bin auch der festen Meinung, dass Mathematica in einer neuen Version oder mit Abstrichen (denn wir wollen hier ja nicht die absolute Sicherheit von 20000stelligen Zahlen haben) schneller werden kann.
Um objektiv vergleichen zu können, ob ein Programm bei NextPrime intern abkürzt, brauchen wir größere Zahlen, mit denen man ein falsches Ergebnis
aufdecken kann...
Vorschläge?
|
Profil
|
Primentus
Senior
Dabei seit: 18.02.2016
Mitteilungen: 2179
Wohnort: Deutschland
| Beitrag No.222, eingetragen 2017-02-21
|
\quoteon(2017-02-19 17:32 - matph in Beitrag No. 214)
\sourceon GP/PARI
p()={r=58310039994836584070534263;for(i=0,9999999,r=nextprime(r+1));print(r)}
\sourceoff
58310039994836584663869571
time = 8min, 55,719 ms.
\quoteoff
Du scheinst einen sehr schnellen Rechner zu haben.
Ich habe den gleichen Code bei mir auch mal in PARI/GP ausgeführt und es dauerte ca. 36 min (also in etwa Faktor 4). Um meine Mathematica-Zeit von 537,5 min neben die von PARI/GP zu stellen, müsste man also durch 4 dividieren, dann wären es ca. 134,4 min. Die rote Laterne bei den nextprime-Geschwindigkeitstests behalte ich damit aber immer noch. ;-)
Warum Mathematica berechnungszeittechnisch bei mir so schlecht abschneidet, dürfte wie gesagt an meinem schon älteren Rechner liegen und an der schon älteren Mathematica-Version, die auch noch eine 32bit-Variante ist und vermutlich nur auf einen CPU-Kern zugreift. Das nur nochmal der Vollständigkeit halber, damit es nicht heißt, Mathematica wäre das langsamste System unter allen CAS. Eine aktuelle 64bit-Version mit Zugriff auf 4 CPU-Kerne und eingebauter NextPrime[]-Funktion liefert da mit Sicherheit viel viel bessere Werte. Vielleicht hat ja jemand ein Mathematica zur Verfügung mit diesen Eigenschaften und kann noch eine Berechnungszeit dazu beitragen. Aber das Ganze zeigt eben auch nochmal, wie schwierig es ist, verschiedene Programme und Programmiersprachen auf unterschiedlichen Rechnern miteinander zu vergleichen.
LG Primentus
|
Profil
|
matph
Senior
Dabei seit: 20.11.2006
Mitteilungen: 5506
Wohnort: A
| Beitrag No.223, eingetragen 2017-02-21
|
Hallo,
\quoteon(2017-02-21 00:18 - Primentus in Beitrag No. 222)
Du scheinst einen sehr schnellen Rechner zu haben.
\quoteoff
Naja, mein Rechner auf dem ich dies getestet habe (und gerade noch einmal den Test wiederholt habe) ist schon etwas über sechs Jahre alt ;-)
Während der Berechnung hat dieser nur etwa 13% CPU-Auslastung, allerdings scheint pari/gp (gp64-readline-2-9-1) die Last schön auf alle 8 Kerne (4 physische / 4 HTT) zu verteilen, welche während der Berechnung bei 3.4GHz-3.7GHz getaktet sind.
Wenn man sich Bencharks ansieht, sind die neuen CPUs allerdings fast alle mehr als doppelt so leistungsfähig, und die aktuellen High End CPUs schneiden mehr als drei mal besser ab als meine...
--
mfg
matph
|
Profil
|
Slash
Aktiv
Dabei seit: 23.03.2005
Mitteilungen: 9212
Wohnort: Pferdehof
 | Beitrag No.224, eingetragen 2017-02-21
|
\quoteon(2017-02-21 02:46 - matph in Beitrag No. 223)
allerdings scheint pari/gp (gp64-readline-2-9-1) die Last schön auf alle 8 Kerne (4 physische / 4 HTT) zu verteilen,
\quoteoff
Bist du da sicher? Ich dachte PARI rechnet grundsätzlich nur auf einem Kern. Deshalb teile ich mir Suchalgorithmen oft auf vier Programme auf, um diese zu parallelisieren.
Mein MEDION PC von 2011 mit i3 3.1 GHz brauchte mit PARI 2.9.0 64bit 13 Minuten bei 25% CPU Auslastung.
|
Profil
|
matph
Senior
Dabei seit: 20.11.2006
Mitteilungen: 5506
Wohnort: A
| Beitrag No.225, eingetragen 2017-02-21
|
Hallo,
Es läuft schon auf mehr als einem Kern, allerdings nur im Sinne der Verteilung der Rechenzeit, doch du möchtest vermutlich auf Parallelisierung hinaus, dies mach es nur, falls entsprechend kompiliert via POSIX threads oder MPI, und Einsatz der entsprechenden Funktionen wie parapply oder parfor,... was hier natürlich nicht der Fall ist, auch daran zu sehen, dass diese 100% auf einem Prozessor entsprechen würde :-)
--
mfg
matph
|
Profil
|
hyperG
Senior
Dabei seit: 03.02.2017
Mitteilungen: 2158
| Beitrag No.226, eingetragen 2017-02-21
|
\quoteon(2017-02-21 00:18 - Primentus in Beitrag No. 222)
... bei mir auch mal in PARI/GP ausgeführt und es dauerte ca. 36 min
\quoteoff
Hallo Primentus,
36 min ist für Pari aber wirklich sehr langsam!
Pari64-2-9-1.exe also die neuste 64 Bit Variante: bei mir 8 min 11 s
Damit bestätigen sich die ersten 3 Zeilen aus "Tabelle NextPrime 10^7 mal um 10^24",
die alle auf dem selben PC liefen.
Die Anzahl der Kerne spielt hier keine Rolle, da bei allen von mir getesteten Programmen nur mit 1 Kern gerechnet wird!
(Parallelisierung ist bei diesem Algorithmus auch schwer; höchstens FFT-Multiplikation denkbar)
@matph: bin voll Deiner Meinung. Oft verteilt das Betriebssystem die Last auf andere Kerne um eine gleichmäßige Temperatur zu bekommen. Da von den 8 logischen Kernen aber nur 12 ... 13 % Last insges. -> entspricht das genau 1 logischen Kern (ab Win7 funktioniert Hyperthreading sehr gut, oft sogar besser als eine echte 8-Kern-CPU von AMD)
Da die 8 min Pari/GP_x64 zu den 18 min c++x32 auf dem selben PC aber sehr viel schneller sind,
könnte man einen Abkürzungs-Algorithmus entlarven, wenn man in Ergebnissen Pseudoprimzahlen findet.
Liste Pseudoprimzahlen (also dort, wo bei nextprime falsche Ergebnisse denkbar sind):
\sourceon Pseudoprimzahlen
318665857834031151167461 denn 399165290221×798330580441
360681321802296925566181
2995741773170734841812261
3317044064679887385961981
3404730287403079539471001=1304747157001×2609494314001
59276361075595573263446330101=172157429516701*344314859033401
564132928021909221014087501701=531099297693901*1062198595387801
1543267864443420616877677640751301=27778299663977101*55556599327954201
\sourceoff
\sourceon Pari/GP
(10:45) gp > nextprime(318665857834031151167460)
%1 = 318665857834031151167483
(10:46) gp > nextprime(360681321802296925566180)
%2 = 360681321802296925566203
(10:47) gp > nextprime(2995741773170734841812260)
%3 = 2995741773170734841812283
(10:48) gp > nextprime(3317044064679887385961980)
%4 = 3317044064679887385962123
(10:48) gp > nextprime(3404730287403079539471000)
%5 = 3404730287403079539471029
(10:49) gp > nextprime(59276361075595573263446330100)
%6 = 59276361075595573263446330191
(10:49) gp > nextprime(564132928021909221014087501700)
%7 = 564132928021909221014087501743
(10:50) gp > nextprime(1543267864443420616877677640751300)
%8 = 1543267864443420616877677640751439
nextprime((5046458256311598437^17-1)/5046458256311598436-1)
(10:50) gp > nextprime((5046458256311598437^17-1)/5046458256311598436-1)
%9 = 176924086845583440385029334601048289986353369440246000750532226754500026319951640496425779810208698465451686727745819241565554798064944563042537011741517885299258945019915429722063128800896908162091301455986370569209019152627236204062052357707047774692045517704738837002516485434899113643087475234481
(10:58) gp > nextprime((3^1000*2+2^1000*3+1)/373-1)
%10 = 7088851578985558374747749382049031452897705269448515644315926907382458967006460587350017768635968160664395590867949503249066780601075704621261891288246400396930939545299307259485723342288251212271403623879295684716085898076172110186154541547503230248603474614066788346600455368959565627778887778191545927647265304116651199207915702971633992274289023497139468338889704852486743341384800156784942908789314808390552211034743684644542522065828306077754740555555547898255824972247
\sourceoff
http://www.wolframalpha.com bestätigt alle Ergebnisse!
Also noch kein Beweis für mögliche Abkürzung gefunden.
Ich werde mal Pari/GP auf SSE2 und AVX-Befehle untersuchen...
Kennt jemand noch schöne Pseudoprimzahlen unter 300 Stellen?
|
Profil
|
weird
Senior
Dabei seit: 16.10.2009
Mitteilungen: 5301
| Beitrag No.227, eingetragen 2017-02-21
|
\quoteon(2017-02-20 22:21 - hyperG in Beitrag No. 221)
Natürlich sind die PCs alle unterschiedlich schnell - ABER nicht FAKTOR 10 sondern nur ein paar Prozente!
\quoteoff
Hast du dir inzwischen die Zeiten von Primentus angesehen, vor allem zum Pari-Programm, wo ja objektive Vergleichswerte existieren? Glaubst du danach immer noch, es ging nur um "ein paar Prozente", oder nicht eher doch ein bißchen mehr? :-D
\quoteon
ABER für das c++GMPx32 mit mpz_nextprime kann ich folgende Fakten benennen:
- es liefert um 189452997113368438678230 und um 3317044064679887385961980 richtige Werte!
- mit einer neueren GMP.dll konnte ich die Zeit noch von 31 min auf 18,2 min verbessern!!
- es kann durch Umstieg auf 64 Bit und weitere Optimierungen noch verbessert werden
Damit man Deinen GCD-Algorithmus objektiv vergleichen kann, habe ich ihn auf die Schnelle ohne große Optimierung
mit GMP umgesetzt:[...]
Also grob 11 min ohne jegliche Optimierung - also nur minimal langsamer als Dein PC, was an meinen 9 Jahre alten PC liegen kann.
\quoteoff
Das klingt für mich alles sehr seltsam, wo du doch eben noch eben behauptest hast, es ginge da in Sachen PC nur "um ein paar Prozente". Ist dir dafür dieser oben beschriebene Aufwand denn nicht zu schade? :-D
\quoteon
Dieser GCD-Abkürzungs-Algorithmus liefert jedoch schon bei 3317044064679887385961980
das falsche Ergebnis 3317044064679887385961981=1287836182261 * 2575672364521 !!
Er trickst so enorm, dass man damit nicht in "unbekannte Bereiche" vorstoßen sollte -> und man kann ihn damit NICHT in den NextPrime-Geschwindigkeitsvergleich mit aufnehmen!
\quoteoff
Bisher konnte ich ja das alles noch mit sehr viel Sinn für Humor ertragen, aber das schlägt nun echt dem Fass den Boden aus! Du hast also für den hier eingesetzten probabilistischen Primzahltest ein Beispiel entdeckt, wo er nicht funktionieren würde - surprise, surprise! - wobei du dir dir nicht einmal die Mühe gemacht hast, eines jenseits unserer "Startprimzahl" zu suchen, und lehnst ihn daher ab, weil er dir zu "probabilistisch" ist, obwohl es hier ja nur um probabilistische Primzahltests geht und meiner hier immerhin in geschätzt ca. 180 Millionen Aufrufen bestanden hat und am Ende auch das richtige Ergebnis liefert? Ist das echt dein Ernst? Das ist ja, das ist ja ..., ne, ich sag jetzt gar nichts mehr dazu, denn das wäre dann wirklich schon "unter der Gürtellinie", um mit deinen Worten zu sprechen. :-o
Tatsächlich hatte ich eigentlich vor, noch ein wirklich professionelles Programm dazu zu schreiben, und nachdem die algorithmische Zahlentheorie zu jenen Kerngebieten der Mathematik zählt, in denen ich selber schon geforscht habe, hätte dabei vielleicht auch was Interessantes herauskommen können. Aber jetzt ist mir ehrlich gesagt die Lust dazu gründlich vergangen! :-(
|
Profil
|
Primentus
Senior
Dabei seit: 18.02.2016
Mitteilungen: 2179
Wohnort: Deutschland
| Beitrag No.228, eingetragen 2017-02-21
|
\quoteon(2017-02-21 02:46 - matph in Beitrag No. 223)
Während der Berechnung hat dieser nur etwa 13% CPU-Auslastung, allerdings scheint pari/gp (gp64-readline-2-9-1) die Last schön auf alle 8 Kerne (4 physische / 4 HTT) zu verteilen, welche während der Berechnung bei 3.4GHz-3.7GHz getaktet sind.
\quoteoff
Das hab ich fast schon vermutet, dass es bei Dir 8 CPU-Kerne sind. Bei mir sind es nämlich 2 CPU-Kerne, was ganz gut den Faktor 4 erklärt.
\quoteon(2017-02-21 11:42 - hyperG in Beitrag No. 226)
36 min ist für Pari aber wirklich sehr langsam!
Pari64-2-9-1.exe also die neuste 64 Bit Variante: bei mir 8 min 11 s
\quoteoff
\quoteon(2017-02-21 11:42 - hyperG in Beitrag No. 226)
Die Anzahl der Kerne spielt hier keine Rolle, da bei allen von mir getesteten Programmen nur mit 1 Kern gerechnet wird!
(Parallelisierung ist bei diesem Algorithmus auch schwer; höchstens FFT-Multiplikation denkbar)
\quoteoff
Bei mir ist es die 32 Bit Variante, und anscheinend nutzt PARI/GP schon alle CPU-Kerne aus, denn sonst wäre es nicht Faktor 4 zwischen matph's und meiner Berechnung (8 Kerne vs. 2 Kerne).
\quoteon(2017-02-21 13:37 - weird in Beitrag No. 227)
\quoteon(2017-02-20 22:21 - hyperG in Beitrag No. 221)
Dieser GCD-Abkürzungs-Algorithmus liefert jedoch schon bei 3317044064679887385961980
das falsche Ergebnis 3317044064679887385961981=1287836182261 * 2575672364521 !!
Er trickst so enorm, dass man damit nicht in "unbekannte Bereiche" vorstoßen sollte -> und man kann ihn damit NICHT in den NextPrime-Geschwindigkeitsvergleich mit aufnehmen!
\quoteoff
[...] Du hast also für den hier eingesetzten probabilistischen Primzahltest ein Beispiel entdeckt, wo er nicht funktionieren würde - surprise, surprise! - wobei du dir dir nicht einmal die Mühe gemacht hast, eines jenseits unserer "Startprimzahl" zu suchen, und lehnst ihn daher ab, weil er dir zu "probabilistisch" ist, obwohl es hier ja nur um probabilistische Primzahltests geht [...]
\quoteoff
Das finde ich jetzt schon auch sehr bemerkenswert. hyperG war der erste, der hier alle möglichen Methoden und "Tricks" zulassen wollte, um möglichst schnell Primzahlen zu finden, und wenn andere ihre Optimierungsmethoden einbauen, wäre es auf einmal zu viel getrickst? Das ist schon starker Tobak! Wenn man schon von probabilistischen Primzahltests spricht, ist es doch klar, dass diese irgendwann Fehler liefern, also verstehe ich nicht so ganz, worum es hyperG hier geht. hyperG war doch derjenige, der diese fehlerbehafteten Algorithmen überhaupt erst ins Spiel gebracht hat (siehe Fibonacci-Methode). Ich habe immer mehr den Eindruck, wie wenn hyperG hier mit unfairen Mitteln arbeiten will, nur um selbst den schnellsten Algorithmus präsentieren zu können. Leider entfernen wir uns hiermit wirklich immer weiter von der ursprünglichen Intention dieses Threads.
\quoteon(2017-02-21 13:37 - weird in Beitrag No. 227)
Tatsächlich hatte ich eigentlich vor, noch ein wirklich professionelles Programm dazu zu schreiben, und nachdem die algorithmische Zahlentheorie zu jenen Kerngebieten der Mathematik zählt, in denen ich selber schon geforscht habe, hätte dabei vielleicht auch was Interessantes herauskommen können. Aber jetzt ist mir ehrlich gesagt die Lust dazu gründlich vergangen! :-(
\quoteoff
Ich kann es zwar absolut verstehen, finde es aber sehr schade, denn mich würde es schon interessieren, was dabei herauskommen würde.
Nochmal ein paar Worte an hyperG:
Wenn Du schon von probabilistischen Methoden sprichst und selber Methoden nutzt, die scheinbar keine Grenzen hinsichtlich ihrer Zulässigkeit kennen (sogar AVX-Befehle willst Du noch untersuchen, um sogar hardwarenah noch irgendwas rauszuholen, usw.), dann musst Du anderen schon auch beliebige Methoden zubilligen, denn sonst wird das hier wirklich kein fairer Vergleich. Da kann ich dann schon verstehen, dass weird die Lust vergeht, bei diesem Vorhaben noch weiter mitzumachen. Ich selbst kann ohnehin nicht viel zu probabilistischen Methoden beitragen, da ich zu wenig darüber weiß.
LG Primentus
|
Profil
|
hyperG
Senior
Dabei seit: 03.02.2017
Mitteilungen: 2158
| Beitrag No.229, eingetragen 2017-02-22
|
\quoteon(2017-02-21 13:37 - weird in Beitrag No. 227)
Hast du dir inzwischen die Zeiten von Primentus angesehen, vor allem zum Pari-Programm, wo ja objektive Vergleichswerte existieren? Glaubst du danach immer noch, es ging nur um "ein paar Prozente", oder nicht eher doch ein bißchen mehr?
\quoteoff
Nein, dass ist logisch, wenn er die alte 32 Bit Variante nimmt,
und ich die neue 64 Bit Variante mit SSE2 (internen 128 Bit)!
(natürlich spielen da noch zig andere Faktoren eine Rolle, denn die i7 CPU ist ja auch schneller als eine AMD mit gleicher Kernanzahl und gleicher Taktfrequenz)
Wie versprochen hier die Analyse der GP.exe (Pari... ohne DLLs):
SSE-Befehle: 197
SSE2-Befehle: 1740 {d.h. intern mit 128 Bit !!)
SSE3 & 4: 0
AVX: 0
FPU: 67
benutzte CPU-Kerne: 1 (kein messbares Multithreading!)
(Ihr könnt matph und mir glauben: mehr Kerne zu haben bedeutet nicht automatisch, dass jede Software diese auch nutzt!
Ich kann sogar ohne Geschwindigkeitsverluste mehrere dieser 1-Kern-Software parallel laufen lassen ohne merkliche Verluste)
@matph:
Nochmals danke für diese SUPER-Software!!
Dieses Programm ist wirklich der Hammer! Dort, wo ich 3 Tage eine komplizierte Iteration mit 100000
Nachkommastellen realisierte (bc), bekomme ich heute mit einer ausgelagerten gp-Konfigurationsdatei in etwa 8 Sekunden
3 200000 Stellige Ergebnisse!!! Unglaublich! Habe vor lauter Misstrauen noch einen anderen Algorithmus zur Validierung verwendet: es stimmte alles!
\quoteon
Das klingt für mich alles sehr seltsam, wo du doch eben noch eben behauptest hast, es ginge da in Sachen PC nur "um ein paar Prozente". Ist dir dafür dieser oben beschriebene Aufwand denn nicht zu schade?
...
\quoteoff
Ich bin leider nicht richtig verstanden worden:
Am Anfang ging es um die Formel und um den "unteren Bereich", den man leicht und schnell mit jeder beliebigen Software nachprüfen kann.
Dann hatte ich vorgeschlagen, mal in die Ferne zu schauen und den "oberen Bereich" zu vergleichen (also da weiterzumachen, wo der letzte bekannte Wert zu finden ist). Da gibt es keine Überprüfung, ob das Ergebnis noch stimmt! Ein Fehler und alle weiteren Folgerechnungen, die auf Zwischenergebnisse aufbauen, wären FALSCH!!
Alle diese Tests/Programme weit oben funktionieren mit probabilistischen Algorithmen! Also habe ich ganz objektiv 3 Programme auf meinem PC mit dem Befehl Next...Prime verglichen.
Ich habe ja nicht ahnen können, dass sich da 2 Vertreter von teurer Software auf den Schlips getreten fühlen...
Natürlich wird die Software schneller, wenn man bei probabilistischen Algorithmen die "Schärfe" herausnimmt! Und genau deshalb habe ich:
1. das mit GMP nachvollzogen
2. jede Software immer kritisch untersucht
Natürlich ist der GCD-Abkürzungsalgorithmus nicht schlecht, aber wenn er bereits bei 25stelligen Zahlen Fehler erzeugt, kann man damit keine Suche von 26stelligen Zahlen beginnen, die nicht überprüfbar sind.
Daher meine Aufspaltung in 2 Vergleichstabellen.
Da der Test von JAVA mit die kleinste Fehlerquote hat (und auch mit am langsamsten ist), könnte man ihn sogar in eine 3. Kategorie einstufen. ABER dazu brauchen wir große Pseudoprimzahlen um sagen zu können, bis welchen Bereich noch sicher...
|
Profil
|
weird
Senior
Dabei seit: 16.10.2009
Mitteilungen: 5301
| Beitrag No.230, eingetragen 2017-02-22
|
\quoteon(2017-02-22 00:22 - hyperG in Beitrag No. 229)
\quoteon(2017-02-21 13:37 - weird in Beitrag No. 227)
Hast du dir inzwischen die Zeiten von Primentus angesehen, vor allem zum Pari-Programm, wo ja objektive Vergleichswerte existieren? Glaubst du danach immer noch, es ging nur um "ein paar Prozente", oder nicht eher doch ein bißchen mehr?
\quoteoff
Nein, dass ist logisch, wenn er die alte 32 Bit Variante nimmt,
und ich die neue 64 Bit Variante mit SSE2 (internen 128 Bit)!
(natürlich spielen da noch zig andere Faktoren eine Rolle, denn die i7 CPU ist ja auch schneller als eine AMD mit gleicher Kernanzahl und gleicher Taktfrequenz)
\quoteoff
Du redest dich da gerade selber um Kopf und Kragen und das Lustige dabei ist, du merkst es nicht einmal! Was du sagst von wegen 32 Bit bzw. 64 Bit Variante, Art der CPU, Anzahl der Kerne etc. ist ja genau das was ich die ganze Zeit behaupte, nämlich dass es bei diesen ganzen Geschwindigkeitsvergleichen sehr wohl auch und jetzt nicht nur marginal (von wegen "ein paar Prozente"!) auf den PC ankommt, auf dem das Ganze läuft!!!
\quoteonIch bin leider nicht richtig verstanden worden:
Am Anfang ging es um die Formel und um den "unteren Bereich", den man leicht und schnell mit jeder beliebigen Software nachprüfen kann.
Dann hatte ich vorgeschlagen, mal in die Ferne zu schauen und den "oberen Bereich" zu vergleichen (also da weiterzumachen, wo der letzte bekannte Wert zu finden ist). Da gibt es keine Überprüfung, ob das Ergebnis noch stimmt! Ein Fehler und alle weiteren Folgerechnungen, die auf Zwischenergebnisse aufbauen, wären FALSCH!!
\quoteoff
Dir ist aber schon klar, dass das, was du da schreibst, prinzipiell auf alle Programme zutrifft, welche intern probalistische Primzahltests verwenden, insbesondere auch auf deine! Bei dem einen kommen diese Fehler früher, bei dem anderen später, das ist also nur ein gradueller und kein prinzipieller Unterschied. So what?! :-?
\quoteonAlle diese Tests/Programme weit oben funktionieren mit probabilistischen Algorithmen! Also habe ich ganz objektiv 3 Programme auf meinem PC mit dem Befehl Next...Prime verglichen.
Ich habe ja nicht ahnen können, dass sich da 2 Vertreter von teurer Software auf den Schlips getreten fühlen...
\quoteoff
Ja, weil du da, um es noch einmal zu sagen, auch wenn es wieder nichts nützt, "Äpfel mit Birnen" vergleichst. Dass es auf die verwendete Hard- und Software eben auch ankommt, darüber haben wir schon gesprochen, aber dann eben auch auf die "Stärke" der intern verwendeten Primzahltests, oder wie du ja selber auch sagst:
\quoteonNatürlich wird die Software schneller, wenn man bei probabilistischen Algorithmen die "Schärfe" herausnimmt!
\quoteoff
Eigentlich ging es mir bei meinem letzten Programm im Grunde nur darum, genau dies aufzuzeigen, aber das hast du halt leider nicht verstanden, wie vieles andere hier auch. Irgendwie schade, dass bei einem Thema, das mir doch irgendwie sehr am Herzen liegt und wo ich auch durchaus aus eigener Erfahrung einiges dazu beitragen könnte, alles so schief läuft! :-(
|
Profil
|
Primentus
Senior
Dabei seit: 18.02.2016
Mitteilungen: 2179
Wohnort: Deutschland
| Beitrag No.231, eingetragen 2017-02-22
|
\quoteon(2017-02-22 00:22 - hyperG in Beitrag No. 229)
Ich habe ja nicht ahnen können, dass sich da 2 Vertreter von teurer Software auf den Schlips getreten fühlen...
\quoteoff
Darum geht es gar nicht. Ich bin auch ein Anhänger von Open Source Software, so ist es nicht. Aber man muss wie gesagt schon darauf achten, was man miteinander vergleicht und darf dabei nicht solche Startbedingungen wie Hardware-Ausstattung, Anzahl CPU-Kerne, 32bit vs. 64 bit, usw. außer Acht lassen. Und dabei kann es wirklich um deutliche Unterschiede gehen, wie man gesehen hat, das sind keinesfalls nur ein paar Prozent wie von Dir behauptet. Ich bin halt noch auf die 32bit Programme angewiesen, weil mein Betriebssystem noch eine 32bit Version ist.
Und was Deinen Rechner betrifft, so müsstest Du eigentlich auch die neueste Maple-Version und neueste Mathematica-Version bei Dir laufen lassen, dann hätte man wirklich belastbare Vergleichszahlen. Bis jetzt hast Du ja abgesehen von PARI/GP nur Nicht-CAS-Systeme auf demselben Rechner untersucht.
\quoteon(2017-02-19 12:23 - hyperG in Beitrag No. 213)
\sourceon JAVA
...
bi3 = new BigInteger("58310039994836584070534263");
gegIndex=1000000000000000000000000L;
gesIndex=1000000000000000010000000L;
long offs=gesIndex-gegIndex;
for(c2 = 0; c2 < offs; c2++)
{ bi3 = bi3.nextProbablePrime();
}
System.out.println("Prime("+(gesIndex)+")="+bi3+" in "+(System.currentTimeMillis()-seed)+"ms");
Output:
Prime(1000000000000000010000000)=58310039994836584663869571 in 3843660 ms =64 min
\sourceoff
\quoteoff
Außerdem möchte ich noch anmerken, dass Du z. B. bei Deinem JAVA-Programm die Funktion nextProbablePrime() verwendet hast, welche eine probabilistische Methode darstellt und damit natürlich vergleichsweise schnell arbeitet (soweit so gut). Gleichzeitig hast Du aber Berechnungszeiten anderer Systeme daneben gestellt, wo lediglich eine NextPrime-Funktion verwendet wurde, wo meines Erachtens keinesfalls sichergestellt ist, dass diese auch auf einer probabilistischen Methode beruht, sondern eher mit 100%iger Sicherheit die richtige Primzahl liefert und damit natürlich von Haus aus deutlich langsamer arbeitet. Also dieser Vergleich hinkt auch schon wieder.
Wenn PARI/GP dann am schnellsten abschneidet, liegt das wohl weniger an dem schnellen dortigen NextPrime-Algorithmus, als vielmehr daran, dass offenbar wirklich mit einer internen 128bit-Variante gerechnet wird, wie von Dir selbst untersucht wurde. Und dann ist es ja schon mal klar, dass alle Programme und Programmiersprachen, die das nicht nutzen, schon mal deutlich im Nachteil sind.
Und ansonsten ist auch klar, dass C++ generell sehr gut abschneidet, denn diese Programmiersprache ist nun mal bekannt für ihre sehr gute Performance. Dass Java im Vergleich dazu deutlich schlechter abschneidet, war nicht anders zu erwarten (und das sogar trotz dessen, dass dort nextProbablePrime() verwendet wurde).
So viel noch zum Thema Geschwindigkeitsvergleiche.
LG Primentus
|
Profil
|
hyperG
Senior
Dabei seit: 03.02.2017
Mitteilungen: 2158
| Beitrag No.232, eingetragen 2017-02-22
|
Wie ich selbst in Beitrag No.221, eingetragen 2017-02-20 22:21
geschrieben habe "natürlich noch auf den selben PC relativieren müsste"
nur der selbe PC:
\sourceon Tabelle NextPrime 10^7 mal um 10^24 mit i7 3770K 3.50GHz (4GHz Turbo)
GP/pari_x64 8,18 min
c++GMPx32 18,20 min {neuere DLL}
JAVAx64 64,00 min
\sourceoff
Habe nun ein extra langsames Notebook mit 2 Kernen herausgesucht:
\sourceon Tabelle GCD-Abkürzung 10^7 mal um 10^24
i7 3770K 3.50GHz (4GHz Turbo) | Intel Core2 T9300 2.50GHz
---------------------------------------------------------------
GP/pari 8,18 min | -
c++GMPx32 11,38 min | 23,46 min {neue DLL}
\sourceoff
\sourceon Faktorenvergleiche:
Taktfrequenz & logische Kerne : 4/1,44*8/4 = 5,55
CPU Mark ist etwas realistischer: 9549/1670 = 5,71
32Bit-1-Kern-Software nachgemessen: 23,46/11,38 = 2
\sourceoff
Was ich also die ganze Zeit versuche zu erklären:
Wenn man eine 5,7 mal schnellere CPU nimmt, diese aber mit alter 32Bit Software
nur auf 1 Kern laufen lässt, ist man nur etwa 2 mal schneller.
In Summe also 5,7/2 = 2,85 mal langsamer als erwartet.
Da hier aber keiner so ein langsames Notebook hat, nehmen wir mal CPU-Mark Faktor 2 mal langsamer als meine CPU an.
Die identische Software auf dem angeblich so langsamen Primentus-PC dürfte mit 1-Kern-Technik
nicht 2 mal so langsam laufen, sondern nur etwa 1,5 mal -> was ich mit "paar Prozente" beschrieb.
Wie sich dann herausstellte, wurde ja bei GP/pari eine ältere Version verwendet,
was den Faktor 36/8,18=4,4 erklärt.
Habe nun auch die DLL von GP/pari untersucht: über 12000 SSE2 Befehle.
Und eine neue Pseudoprimzahl ausfindig gemacht:
2447952037112100847479213118326022843437705003126289=74168110994901817×148336221989803633×222504332984705449
- GCD-Abkürzung gibt sie fälschlicherweise als Primzahl aus.
- GP/pari\nextprime, JAVA und GMP\mpz_nextprime
überspringen sie korrekt.
|
Profil
|
weird
Senior
Dabei seit: 16.10.2009
Mitteilungen: 5301
| Beitrag No.233, eingetragen 2017-02-24
|
\quoteon(2017-02-22 17:20 - Primentus in Beitrag No. 231)
Außerdem möchte ich noch anmerken, dass Du z. B. bei Deinem JAVA-Programm die Funktion nextProbablePrime() verwendet hast, welche eine probabilistische Methode darstellt und damit natürlich vergleichsweise schnell arbeitet (soweit so gut). Gleichzeitig hast Du aber Berechnungszeiten anderer Systeme daneben gestellt, wo lediglich eine NextPrime-Funktion verwendet wurde, wo meines Erachtens keinesfalls sichergestellt ist, dass diese auch auf einer probabilistischen Methode beruht, sondern eher mit 100%iger Sicherheit die richtige Primzahl liefert und damit natürlich von Haus aus deutlich langsamer arbeitet. Also dieser Vergleich hinkt auch schon wieder.
\quoteoff
Zwar bin ich mir ziemlich sicher, dass alle gängigen CAS intern für ihre nextprime-Variante probabilistische Primzahltests nutzen - für Maple gilt dies z.B. jedenfalls - da andernfalls die Rechenzeiten deutlich höher ausfallen müssten, aber man kann darauf aufbauend trotzdem ein interessantes Gedankenexperiment anstellen: Was wäre eigentlich, wenn jemand hier für die Rechnung Primzahltests verwendet, welcher für Zahlen der Größenordnung, um die es hier geht noch beweisbar(!) sicher ist? Sein Programm würde natürlich ob des hohen Aufwands weit abgeschlagen in hyperG's Tabelle auf dem letzten Platz rangieren, obwohl es als einziges(!) ein beweisbar richtiges Resultat liefert, wenn wir davon ausgehen, dass die verwendete Hard- und Software korrekt arbeitet. Soviel also noch einmal zur "Vergleichbarkeit" der Rechenzeiten seiner Tabelle. :-o
|
Profil
|
Primentus
Senior
Dabei seit: 18.02.2016
Mitteilungen: 2179
Wohnort: Deutschland
| Beitrag No.234, eingetragen 2017-02-24
|
@hyperG:
Wie dem auch immer sei - eine besonders alte Version von PARI/GP war es jetzt auch nicht, die ich für die Berechnung genutzt habe. Es war die Version 2.7.6 vom Juni 2016 und das halt in der 32bit Variante. Jetzt hab ich mir extra nochmal die neueste Version 2.9.1 installiert (32bit), und siehe da, die Berechnung dauert noch immer ca. 36 Minuten. Mag ja sein, dass die 64bit-Variante gleich um den Faktor 4 schneller ist, aber dann halt in Kombination mit einem ebenfalls schnelleren Prozessor.
@weird:
Ok, mag sein, dass bei den NextPrime-Algorithmen vielleicht doch probabilistische Methoden verwendet werden, aber bei Mathematica kann ich es mir irgendwie nicht vorstellen, dass das System ein unzuverlässiges Ergebnis ausgibt. Leider hab ich hier die NextPrime-Funktion noch nicht zur Verfügung, denn dann könnte man vielleicht anhand der Berechnungszeit darauf schließen, ob es probabilistisch ist oder nicht.
Was die Primzahlalgorithmen betrifft - mir ist ja ehrlich gesagt schon ein Algorithmus lieber, der ein 100% sicheres Ergebnis liefert, aber dafür länger rechnet, als wenn ich in Windeseile ein Ergebnis habe, auf das ich mich gar nicht verlassen kann. Aber gut, man könnte dafür zumindest im Anschluss eine Primfaktorzerlegung für die entsprechende vermeintliche Primzahl machen, um auf Nummer sicher zu gehen. Ist dann nur die Frage, wie lange das dann wiederum dauert.
LG Primentus
|
Profil
|
Kay_S
Senior
Dabei seit: 06.03.2007
Mitteilungen: 1445
Wohnort: Koblenz (früher: Berlin)
 | Beitrag No.235, eingetragen 2017-02-24
|
Es ist gut möglich, dass eine 64-Bit-Version um Faktor 3-4 schneller ist als die 32-bittige.
Langzahlmultiplikationen werden auf die Multiplikationen von Worten zurückgeführt (die hier eine Länge von 64 bzw. 32 Bit besitzen). Das naive Verfahren zur Multiplikation hat eine Laufzeit von O(k²), wobei k die Länge der Faktoren ist (genauer: die Länge in Worten). Auf einem 64-Bit-System wäre dieses rechnerisch um Faktor 4 schneller als auf 32-Bit.
Zwar gibt es Verfahren mit besserer Komplexität (Karatsuba, Schönhage), diese kommen jedoch erst ab bestimmten Bitlängen zum Einsatz.
|
Profil
|
weird
Senior
Dabei seit: 16.10.2009
Mitteilungen: 5301
| Beitrag No.236, eingetragen 2017-02-24
|
\quoteon(2017-02-24 14:05 - Primentus in Beitrag No. 234)
Ok, mag sein, dass bei den NextPrime-Algorithmen vielleicht doch probabilistische Methoden verwendet werden, aber bei Mathematica kann ich es mir irgendwie nicht vorstellen, dass das System ein unzuverlässiges Ergebnis ausgibt. Leider hab ich hier die NextPrime-Funktion noch nicht zur Verfügung, denn dann könnte man vielleicht anhand der Berechnungszeit darauf schließen, ob es probabilistisch ist oder nicht.
\quoteoff
Sorry, dass ich dir da ausnahmsweise widersprechen muss, aber ich halte es für vollkommen ausgeschlossen, dass Mathematica in der von dir angegebenen Zeit deterministische Primzahltests, wie z.B. den Goldwasser-Kilian-Test (verfeinert von Atkin-Morain auf der Basis von sog. CM-Kurven) durchgeführt hat, der wäre zwar für 25-stellige Zahlen sicher noch ohne weiteres machbar, aber doch deutlich langsamer, und zwar gleich um einige Zehnerpotenzen!
\quoteonWas die Primzahlalgorithmen betrifft - mir ist ja ehrlich gesagt schon ein Algorithmus lieber, der ein 100% sicheres Ergebnis liefert, aber dafür länger rechnet, als wenn ich in Windeseile ein Ergebnis habe, auf das ich mich gar nicht verlassen kann.
\quoteoff
Naja, auch das kann man so nicht ganz stehen lassen. Wenn man von einer Zahl im Sinne der exakten Mathematik beweisen will, dann führt ohnehin kein Weg an einen deterministischen Primzahltest vorbei, da gebe ich dir vollkommen Recht. Es gibt aber viele Anwendungen, z.B. für Zwecke der Kryptographie, da reicht eine ausreichend niedrige Irrtumswahrscheinlichkeit aus, da erstens andere "Fehlerquellen" um Größenordnungen wahrscheinlicher sind und man zweitens in der Anwendung selber dann bei einem einfachen Test i.d.R. auch sofort merken würde, dass mit der "angeblichen Primzahl" etwas nicht stimmt. (Bei RSA würden z.B. Ver- und Entschlüsselung - außer in gewissen seltenen Ausnahmefällen - nicht "zusammenpassen".)
\quoteonAber gut, man könnte dafür zumindest im Anschluss eine Primfaktorzerlegung für die entsprechende vermeintliche Primzahl machen, um auf Nummer sicher zu gehen. Ist dann nur die Frage, wie lange das dann wiederum dauert.
\quoteoff
Auch das stimmt so leider nicht, denn selbst wenn die ausgegebene Zahl prim ist, könnte trotzdem ihre "Nummer" in der Primzahlfolge falsch, und zwar zu niedrig sein, indem zwischendurch zusammengesetzte Zahlen mit Primzahlen verwechselt wurden.
Ja, ich weiß, ich bin heute der "Geist, der stets verneint", oder wie man auch sagt, der "advocatus diaboli", aber wie ich ja schon angedeutet habe, ist dies ein Gebiet, wo ich mich durch viele Vorträge und Publikationen auch wirklich auskenne und wo ich insbesondere auch viele der angesprochenen Algorithmen schon selbst implementiert habe und somit "aus erster Hand" kenne. ;-)
|
Profil
|
Primentus
Senior
Dabei seit: 18.02.2016
Mitteilungen: 2179
Wohnort: Deutschland
| Beitrag No.237, eingetragen 2017-02-24
|
@Kay_S:
Ok, dann wird es wohl so sein, dass das tatsächlich so viel ausmacht mit den verschiedenen Bit-Versionen. Hätte ich nicht gedacht.
@weird:
Tja, dem habe ich nichts mehr hinzuzufügen - außer vielleicht: so sei es! Glaube ich Dir mal so weit, da es offenbar Dein Spezialgebiet ist (aber das vermute ich nicht erst seit heute).
Deswegen bin ich auch nur der Primentus* und Du der Primus del Prim, wie ich es in meinem Pseudo-Latein ausdrücken würde. :-D Gegen diabolisch gute Argumente ist natürlich nichts einzuwenden.
P.S.: Ich lerne gerne dazu was die Primzahlenwelt betrifft, und auch Deine lateinischen Begriffe sind immer wieder interessant!
*Wahlweise nehme ich aber auch Bezeichnungen wie Prim$\mathbf{\frac{e}{E}}$nt(h)usiast entgegen. :-D
LG Primentus
|
Profil
|
hyperG
Senior
Dabei seit: 03.02.2017
Mitteilungen: 2158
| Beitrag No.238, eingetragen 2017-03-20
|
\quoteon(2017-02-24 21:03 - Primentus in Beitrag No. 237)
... dann wird es wohl so sein, dass das tatsächlich so viel ausmacht mit den verschiedenen Bit-Versionen. Hätte ich nicht gedacht.
\quoteoff
Das möchte ich mit folgenden Fakten untermauern:
NextPrime-Benchmark-Tests 32...64 Bit 1...8 Kerne
Interessant wird die neue CPU von AMD RYZEN mit 16 virtuellen Kernen!
|
Profil
|
Primentus
Senior
Dabei seit: 18.02.2016
Mitteilungen: 2179
Wohnort: Deutschland
| Beitrag No.239, eingetragen 2017-03-20
|
@hyperG:
Interessante Zahlen. Denen gemäß sieht es aber jetzt so aus, wie wenn die Verdopplung der Anzahl Bits bei gleichbleibender Anzahl Kerne doch nur etwas weniger als ne Halbierung der Berechnungszeit bringt (vgl. 11,38 min vs. 5,01 min), und die Verachtfachung der Anzahl Kerne bei gleichbleibender Bitzahl ergibt eine in etwa vierfach schnellere Berechnungszeit (10,1 min vs. 2,44 min).
LG Primentus
|
Profil
|
hyperG
Senior
Dabei seit: 03.02.2017
Mitteilungen: 2158
| Beitrag No.240, eingetragen 2017-03-21
|
Nein, so einfach und konst. sind die Verbesserungs-Faktoren nicht!
Kerne/Parallelisierung:
- was man hier sieht sind einfach nur verschiedene Optimierungs-Phasen
(und noch bin ich nicht am Ende der Optimierung)
- nicht jeder Algorithmus lässt sich in 8 ideal gleiche Teil-Rechnungen parallelisieren
(und es gibt auch noch "Sammelpunkte" {WaitForMultipleObjects}, wo man warten muss, bis alle Threads fertig sind)
- nicht jede CPU kann intern 100% parallelisieren. So zeigt Test 3 bei Intel's i7 (4 echte Kerne und per Hyperthreading 8 logische Kerne) bei den beiden selben exe eine Verbesserung um Faktor 4,247 und bei AMD (8 echte Kerne) Faktor 5,315.
(bei Vista 64 Bit war das Hyperthreading noch schlechter)
Außerdem gelingt Multithreading mit externer GMP.DLL natürlich nicht so gut!
Test 4 mit internem 128 Bit MulMod-ASM-Befehl (ohne DLL) schafft es der i7 nach der Parallelisierung auf Faktor 7.
Mit weiteren Optimierungen kommt man zwar etwas höher -> wird aber bei selber CPU nie den Faktor 8 erreichen können!
64 Bit-Technik:
Mit 256 Bit MulMod-ASM könnte Test 2 bestimmt nochmals verbessert werden...
was den Verbesserungsfaktor zur 32-Bit-Version nochmals vergrößern würde.
Allein die Unterschiede der 32-Bit GMP.DLL bei Version 4 und 5 sind gewaltig!
Bei dem GMP-Projekt gibt es so viele Compilerschalter und Optimierungsstufen...
(man könnte für jede CPU eine speziell zugeschnittene Version "basteln").
Ich hätte auch nie gedacht, dass sich 10 Mio. 20stellige Primzahlen, die mit meinen ersten JAVA Programm
über 35 min dauerten, nach zig Optimierungen und AMD-CPU in unter 18 s fertig sind:
Geschwindigkeitsfaktor etwa 120 !!!
Oder die erste GMP-Version (32 Bit 1 Kern) mit 18,77 min -> nach 3 Optimierungen
(64 Bit 8 Kerne) nur noch 1,2 min benötigt: fast 16 mal schneller!
Oder der NextPrime-Befehl von JAVA 64/2,44=26,3 mal schneller gemacht werden kann...
|
Profil
|
hyperG
Senior
Dabei seit: 03.02.2017
Mitteilungen: 2158
| Beitrag No.241, eingetragen 2017-12-23
|
\quoteon(2017-02-19 12:23 - hyperG in Beitrag No. 213)
...
Output:
Prime(1000000000000000010000000)=58310039994836584663869571 in 3843660 ms =64 min
...
\quoteoff
Hätte nie gedacht, dass nach so vielen Optimierungen immer noch was rauszuholen ist:
Mit Version 6 nun nur noch 34,289 s
und mit neuer Hardware nur noch 16,924 s
NextPrime-Benchmark
Bezogen auf die Ausgangssoftware (JAVA ist schon schneller als 80 % der anderen Interpreter-Sprachen) macht das eine
\sourceon Optimierungsfaktor (Geschwindigkeitssteigerung)
Verbesserung um den Faktor 112 !!!
Und mit dem i9 sogar Faktor 227 !!!
\sourceoff
|
Profil
|
hyperG
Senior
Dabei seit: 03.02.2017
Mitteilungen: 2158
| Beitrag No.242, eingetragen 2019-02-10
|
So, nun habe ich alle 4 Kerne bei mathematica
mit ParallelTable
aktivieren können und tatsächlich nun nur noch 1/4 der Zeit:
NextPrime-Benchmark
Mit neuem PC & neuer mathematica-Version konnten die 82,63 min (im Beitrag 220 noch 537,5 Minuten)
auf 9,61 min verkürzt werden.
Bei 64-Bit-Zahlen ab 13169525310647365859
dauern die 10 Mio. NextPrime nun 5,65 min.
Grobe Schätzung der NextPrime "Schärfe"/Zuverlässigkeiten
99,999999999999? % Mathematica, maple
100-100/2^100 % JAVA (bis heute noch kein Fehlerfall gefunden)
100-100/ 4^50 % Pari/GP
100-100/ 4^50 % GMP/mpz_nextprime
100-700/3825123056546413051 % (ggT(x,102481630431415235)<2)&&(PowMod(2,x-1,x)==1)
|
Profil
|
Primentus
Senior
Dabei seit: 18.02.2016
Mitteilungen: 2179
Wohnort: Deutschland
| Beitrag No.243, eingetragen 2019-02-11
|
Hallo hyperG,
nur noch 9,61 Minuten für $10^{7}$mal NextPrime ist wirklich eine sehr gute Zeit. Da sieht man mal, was man mit neuem schnellem PC + Mathematica + Parallelisierung alles rausholen kann.
Bedeutet also unter anderem: richtig eingesetzt können die Parallel-Funktionen echt was bringen.
Bezüglich 64 Bit-Zahlen ist es wie ich sehe auch nochmal eine super Leistungssteigerung. Freut mich!
LG Primentus
|
Profil
|
matph
Senior
Dabei seit: 20.11.2006
Mitteilungen: 5506
Wohnort: A
| Beitrag No.244, eingetragen 2019-02-11
|
Hallo,
Deine Pari/GP Zuverlässigkeit (Baillie-Pomerance-Selfridge-Wagstaff Test) sollte im Grunde die selbe sein wie jene von Maple.
Die 100% die du angibst gelten (natürlich in pari, und ich gehe einfach mal davon aus, auch in maple und mathematica dies bei ihren Tests sicher gestellt haben) für 64-Bit Integer.
Weit darüber hinaus ist dies allerdings meines Wissens in keinen der 3 Programme für die nextprimes Funktionen sichergestellt, es gibt eigene Methoden in allen drei welche eine sichere Überprüfung ermöglichen, falls du dies möchtest :-)
--
mfg
matph
|
Profil
|
hyperG
Senior
Dabei seit: 03.02.2017
Mitteilungen: 2158
| Beitrag No.245, eingetragen 2019-02-12
|
Danke matph,
100 % war zu hoch angesetzt -> habe ich korrigiert.
Die genaue Zahl bei JAVA habe ich auch korrigiert und mit LINK-Quelle versehen.
Die meisten Programme nutzen auch nur die Lib-DLLs...
Solange man keine Fehlerbeispiele analog
Miller-Rabin-Pseudoprimzahlen
hat, sind es eben nur Schätzungen.
|
Profil
|
matph
Senior
Dabei seit: 20.11.2006
Mitteilungen: 5506
Wohnort: A
| Beitrag No.246, eingetragen 2019-02-12
|
Hallo,
Deine Schätzung für pari/gp ist nach wie vor zu gering ;-)
--
mfg
matph
|
Profil
|
Ehemaliges_Mitglied
 | Beitrag No.247, eingetragen 2019-02-14
|
\quoteon(2016-08-05 20:35 - cyrix in Beitrag No. 3)
Das hat wenig mit Primzahlen zu tun. Du nutzt nur aus, dass diese (wenn größer als 3) nicht durch 2 oder 3 teilbar sind, denn solche Zahlen önnen trivialerweise nicht als Differenz einer Zweier- und einer Dreierpotenz dargestellt werden.
Cyrix
[Die Antwort wurde nach Beitrag No.1 begonnen.]
\quoteoff
Doch z.B. ist ja $\displaystyle 5=2^3-3^1$ darstellbar oder ich hab was falsch verstanden..
Man kann evtl "postulieren" dass $3^n \pm 2^m$ signifikant oft auf eine $\pm p$ trifft, oder dass man mit geschickt gewaehlten m und n Paerchen "viele" primes erhaelt, so dass die o.a. Abbildung $M_n \subset \IN \times \IN \mapsto \mathbb S \subset \mathbb P$ existiert und gewisse Eigenschaften hat. Das koennte man sich naeher anschauen..
|
Profil
|
|
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2023 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die
Nutzungsbedingungen,
die Distanzierung,
die Datenschutzerklärung und das Impressum.
[Seitenanfang]
|
Home / Seite ohne Frame
2023-11-29 01:19 ?
Wie unterstütze ich den Matheplaneten mit Geld?
