Die Mathe-Redaktion - 16.01.2018 20:29 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
ListenpunktSchwätz / Top 15
ListenpunktWerde Mathe-Millionär!
ListenpunktZur Award-Abstimmung
ListenpunktFormeleditor fedgeo
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden oder den Newsletter bestellen.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 743 Gäste und 31 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von Wauzi
Zahlentheorie » Primzahlen - sonstiges » Primzahleneigenschaften
Thema eröffnet 2016-08-05 20:02 von
fermare
Druckversion
Druckversion
Antworten
Antworten
Seite 6   [1 2 3 4 5 6 7]   7 Seiten
Autor
Universität/Hochschule Primzahleneigenschaften
Folgende Antworten hat der Fragesteller vermutlich noch nicht gesehen.
Er/sie war noch nicht wieder auf dem Matheplaneten
hyperG
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 305
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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. :
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
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  Quote  Link auf diesen Beitrag Link
matph
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 20.11.2006
Mitteilungen: 5306
Aus: A
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.214, eingetragen 2017-02-19


Hallo,

GP/PARI
p()={r=58310039994836584070534263;for(i=0,9999999,r=nextprime(r+1));print(r)}
58310039994836584663869571
time = 8min, 55,719 ms.

--
mfg
matph


-----------------
Wir müssen wissen, wir werden wissen. Hilbert
Das Buch der Natur ist in der Sprache der Mathematik geschrieben. Galilei



Wahlurne Für matph bei den Matheplanet-Awards stimmen
  Profil  Quote  Link auf diesen Beitrag Link
weird
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.10.2009
Mitteilungen: 3632
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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:

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

Die Frage ist nur, was genau soll damit bewiesen werden?  confused



Wahlurne Für weird bei den Matheplanet-Awards stimmen
  Profil  Quote  Link auf diesen Beitrag Link
hyperG
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 305
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.216, eingetragen 2017-02-19


Hallo matph,

habe mir extra die Mühe gemacht und mich in c++ mit gmp.DLL eingearbeitet:
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

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  Quote  Link auf diesen Beitrag Link
matph
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 20.11.2006
Mitteilungen: 5306
Aus: A
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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: smile--
mfg
matph


-----------------
Wir müssen wissen, wir werden wissen. Hilbert
Das Buch der Natur ist in der Sprache der Mathematik geschrieben. Galilei



Wahlurne Für matph bei den Matheplanet-Awards stimmen
  Profil  Quote  Link auf diesen Beitrag Link
hyperG
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 305
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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:
Tabelle
GP/pari     8,9 min
c++GMPx32  31,3 min
JAVA       64,0 min
maple      96,9 min

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  Quote  Link auf diesen Beitrag Link
weird
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.10.2009
Mitteilungen: 3632
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.219, eingetragen 2017-02-20


2017-02-19 19:01 - hyperG in Beitrag No. 218 schreibt:
Tabelle
GP/pari     8,9 min
c++GMPx32  31,3 min
JAVA       64,0 min
maple      96,9 min


LOL, eine Tabelle mit Rechenzeiten und mein Programm Schlusslicht, davon hast du wohl schon immer geträumt, was?  biggrin

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.   frown

Aber ok, weißt du was, ich schreib jetzt das Ganze mal schnell ein bißchen um, und zwar wie folgt:

Maple 2015
p0:=58310039994836584070534263:
 
testprime:=proc(n,p0,b:=100000)
   local a:=p0,k:=n,p:=a,d:=2,m:=102481630431415235;
   if a<max(b,50) then return (nextprime@@n)(a) end if;
   while not p mod 6 in {1,5} do p:=p-1 end do;   
   if p mod 6=1 then d:=4 end if;
   do 
      p:=p+d; d:=6-d;
      if igcd(p,m)>1 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

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!  eek

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.   biggrin



Wahlurne Für weird bei den Matheplanet-Awards stimmen
  Profil  Quote  Link auf diesen Beitrag Link
Primentus
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 18.02.2016
Mitteilungen: 558
Aus: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.220, eingetragen 2017-02-20


2017-02-19 08:44 - weird in Beitrag No. 212 schreibt:
Da bin ich aber froh, denn Goto-Befehle sind eigentlich unter Programmierern ein absolutes No-Go.  biggrin

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.

2017-02-19 08:44 - weird in Beitrag No. 212 schreibt:
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.   wink

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. smile Aber auch allgemein finde ich das Konzept eines CAS sehr interessant. Das sind schon sehr mächtige Programme.

2017-02-20 08:40 - weird in Beitrag No. 219 schreibt:
2017-02-19 19:01 - hyperG in Beitrag No. 218 schreibt:
Tabelle
GP/pari     8,9 min
c++GMPx32  31,3 min
JAVA       64,0 min
maple      96,9 min


LOL, eine Tabelle mit Rechenzeiten und mein Programm Schlusslicht, davon hast du wohl schon immer geträumt, was?  biggrin

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.   frown

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:
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]]
Ergebnis:
Mathematica
{32250.8 Second, 58310039994836584663869571}
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.
MuPAD
t1:=time(); r:=58310039994836584070534263; for i from 1 to 10^7 do r:=nextprime(r+1) end_for; t2:=time(); print(t2-t1);
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



Wahlurne Für Primentus bei den Matheplanet-Awards stimmen
  Profil  Quote  Link auf diesen Beitrag Link
hyperG
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 305
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.221, eingetragen 2017-02-20


weird - Beitrag No.219, eingetragen 2017-02-20 08:40 schreibt:
"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"

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

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:
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)
Tabelle GCD-Abkürzung 10^7 mal um 10^24
maple	  9,4 min
c++GMPx32 11 min {ohne Optimierung}

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  Quote  Link auf diesen Beitrag Link
Primentus
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 18.02.2016
Mitteilungen: 558
Aus: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.222, eingetragen 2017-02-21


2017-02-19 17:32 - matph in Beitrag No. 214 schreibt:
GP/PARI
p()={r=58310039994836584070534263;for(i=0,9999999,r=nextprime(r+1));print(r)}
58310039994836584663869571
time = 8min, 55,719 ms.

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. wink

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



Wahlurne Für Primentus bei den Matheplanet-Awards stimmen
  Profil  Quote  Link auf diesen Beitrag Link
matph
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 20.11.2006
Mitteilungen: 5306
Aus: A
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.223, eingetragen 2017-02-21


Hallo,

2017-02-21 00:18 - Primentus in Beitrag No. 222 schreibt:
Du scheinst einen sehr schnellen Rechner zu haben.
Naja, mein Rechner auf dem ich dies getestet habe (und gerade noch einmal den Test wiederholt habe) ist schon etwas über sechs Jahre alt wink
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


-----------------
Wir müssen wissen, wir werden wissen. Hilbert
Das Buch der Natur ist in der Sprache der Mathematik geschrieben. Galilei



Wahlurne Für matph bei den Matheplanet-Awards stimmen
  Profil  Quote  Link auf diesen Beitrag Link
Slash
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.03.2005
Mitteilungen: 5979
Aus: New York
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.224, eingetragen 2017-02-21


2017-02-21 02:46 - matph in Beitrag No. 223 schreibt:
allerdings scheint pari/gp (gp64-readline-2-9-1) die Last schön auf alle 8 Kerne (4 physische / 4 HTT) zu verteilen,

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.


-----------------
Difficilia quae pulchra



Wahlurne Für Slash bei den Matheplanet-Awards stimmen
  Profil  Quote  Link auf diesen Beitrag Link
matph
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 20.11.2006
Mitteilungen: 5306
Aus: A
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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 smile

--
mfg
matph


-----------------
Wir müssen wissen, wir werden wissen. Hilbert
Das Buch der Natur ist in der Sprache der Mathematik geschrieben. Galilei



Wahlurne Für matph bei den Matheplanet-Awards stimmen
  Profil  Quote  Link auf diesen Beitrag Link
hyperG
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 305
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.226, eingetragen 2017-02-21


2017-02-21 00:18 - Primentus in Beitrag No. 222 schreibt:
... bei mir auch mal in PARI/GP ausgeführt und es dauerte ca. 36 min

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):
Pseudoprimzahlen
318665857834031151167461 denn 399165290221×798330580441
360681321802296925566181
2995741773170734841812261
3317044064679887385961981
3404730287403079539471001=1304747157001×2609494314001
59276361075595573263446330101=172157429516701*344314859033401
564132928021909221014087501701=531099297693901*1062198595387801
1543267864443420616877677640751301=27778299663977101*55556599327954201
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

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  Quote  Link auf diesen Beitrag Link
weird
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.10.2009
Mitteilungen: 3632
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.227, eingetragen 2017-02-21


2017-02-20 22:21 - hyperG in Beitrag No. 221 schreibt:
Natürlich sind die PCs alle unterschiedlich schnell - ABER nicht FAKTOR 10 sondern nur ein paar Prozente!

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?  biggrin


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.

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?  biggrin


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!

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.   eek

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!   frown



Wahlurne Für weird bei den Matheplanet-Awards stimmen
  Profil  Quote  Link auf diesen Beitrag Link
Primentus
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 18.02.2016
Mitteilungen: 558
Aus: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.228, eingetragen 2017-02-21


2017-02-21 02:46 - matph in Beitrag No. 223 schreibt:
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.

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.

2017-02-21 11:42 - hyperG in Beitrag No. 226 schreibt:
 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

2017-02-21 11:42 - hyperG in Beitrag No. 226 schreibt:
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)

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).

2017-02-21 13:37 - weird in Beitrag No. 227 schreibt:
2017-02-20 22:21 - hyperG in Beitrag No. 221 schreibt:
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!

[...] 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 [...]

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.

2017-02-21 13:37 - weird in Beitrag No. 227 schreibt:
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!   frown

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



Wahlurne Für Primentus bei den Matheplanet-Awards stimmen
  Profil  Quote  Link auf diesen Beitrag Link
hyperG
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 305
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.229, eingetragen 2017-02-22


2017-02-21 13:37 - weird in Beitrag No. 227 schreibt:
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?

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!


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?
...

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  Quote  Link auf diesen Beitrag Link
weird
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.10.2009
Mitteilungen: 3632
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.230, eingetragen 2017-02-22


2017-02-22 00:22 - hyperG in Beitrag No. 229 schreibt:
2017-02-21 13:37 - weird in Beitrag No. 227 schreibt:
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?

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)

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!!!

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!!

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?!  confused

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...

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:

Natürlich wird die Software schneller, wenn man bei probabilistischen Algorithmen die "Schärfe" herausnimmt!

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! frown



Wahlurne Für weird bei den Matheplanet-Awards stimmen
  Profil  Quote  Link auf diesen Beitrag Link
Primentus
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 18.02.2016
Mitteilungen: 558
Aus: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.231, eingetragen 2017-02-22


2017-02-22 00:22 - hyperG in Beitrag No. 229 schreibt:
Ich habe ja nicht ahnen können, dass sich da 2 Vertreter von teurer Software auf den Schlips getreten fühlen...

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.

2017-02-19 12:23 - hyperG in Beitrag No. 213 schreibt:
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


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



Wahlurne Für Primentus bei den Matheplanet-Awards stimmen
  Profil  Quote  Link auf diesen Beitrag Link
hyperG
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 305
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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:
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

Habe nun ein extra langsames Notebook mit 2 Kernen herausgesucht:
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}
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

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  Quote  Link auf diesen Beitrag Link
weird
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.10.2009
Mitteilungen: 3632
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.233, eingetragen 2017-02-24


2017-02-22 17:20 - Primentus in Beitrag No. 231 schreibt:
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.

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.  eek



Wahlurne Für weird bei den Matheplanet-Awards stimmen
  Profil  Quote  Link auf diesen Beitrag Link
Primentus
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 18.02.2016
Mitteilungen: 558
Aus: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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



Wahlurne Für Primentus bei den Matheplanet-Awards stimmen
  Profil  Quote  Link auf diesen Beitrag Link
Kay_S
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 06.03.2007
Mitteilungen: 1292
Aus: Koblenz (früher: Berlin)
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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.



Wahlurne Für Kay_S bei den Matheplanet-Awards stimmen
  Profil  Quote  Link auf diesen Beitrag Link
weird
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.10.2009
Mitteilungen: 3632
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.236, eingetragen 2017-02-24


2017-02-24 14:05 - Primentus in Beitrag No. 234 schreibt:
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.

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!

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.

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".)

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.

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.  wink



Wahlurne Für weird bei den Matheplanet-Awards stimmen
  Profil  Quote  Link auf diesen Beitrag Link
Primentus
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 18.02.2016
Mitteilungen: 558
Aus: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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. biggrin  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<math>\mathbf{\frac{e}{E}}</math>nt(h)usiast entgegen. biggrin

LG Primentus



Wahlurne Für Primentus bei den Matheplanet-Awards stimmen
  Profil  Quote  Link auf diesen Beitrag Link
hyperG
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 305
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.238, eingetragen 2017-03-20


2017-02-24 21:03 - Primentus in Beitrag No. 237 schreibt:
... dann wird es wohl so sein, dass das tatsächlich so viel ausmacht mit den verschiedenen Bit-Versionen. Hätte ich nicht gedacht.

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  Quote  Link auf diesen Beitrag Link
Primentus
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 18.02.2016
Mitteilungen: 558
Aus: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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



Wahlurne Für Primentus bei den Matheplanet-Awards stimmen
  Profil  Quote  Link auf diesen Beitrag Link
hyperG
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 305
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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  Quote  Link auf diesen Beitrag Link
hyperG
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 305
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.241, eingetragen 2017-12-23 14:43


2017-02-19 12:23 - hyperG in Beitrag No. 213 schreibt:
...
Output:
Prime(1000000000000000010000000)=58310039994836584663869571 in 3843660 ms =64 min
...

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
Optimierungsfaktor (Geschwindigkeitssteigerung)
Verbesserung um den  Faktor 112 !!!
Und mit dem i9 sogar Faktor 227 !!!




  Profil  Quote  Link auf diesen Beitrag Link
-->> Fortsetzung auf der nächsten Seite -->>
Seite 6Gehe zur Seite: 1 | 2 | 3 | 4 | 5 | 6 | 7  
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2017 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. 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]