Die Mathe-Redaktion - 22.02.2017 13:59 - Registrieren/Login
Auswahl
Schwarzes Brett
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 Dez. 2016

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 696 Gäste und 26 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]   6 Seiten
Autor
Universität/Hochschule Primzahleneigenschaften
Folgende Antworten hat der Fragesteller vermutlich noch nicht gesehen.
Er/sie war noch nicht wieder auf dem Matheplaneten
weird
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.10.2009
Mitteilungen: 2873
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.200, eingetragen 2017-02-17 22:27


2017-02-17 19:02 - Primentus in Beitrag No. 199 schreibt:
Hab allerdings in Mathematica noch kein Analogon für die Funktion next gefunden. Man braucht sie aber noch in einer anderen Code-Zeile. Mal schauen, ob ich da noch was finde.

In manchen Programmiersprachen heißt dieser Befehl continue.

Ich denke, dann hab ich nun verstanden, wie Dein Algorithmus grundsätzlich arbeitet. Du speicherst Dir also sämtliche relevanten Zwischensummen ab und verwendest das für die weitere Aufsummierung. Dann hast Du es in der Tat geschafft, die Durchläufe der Summenformeln drastisch zu reduzieren, was dann wohl auch der Hauptgrund dafür sein dürfte, dass Dein Algorithmus so schnell arbeitet.

Auch dieses "Zwischenspeichern", sofern es nicht vermieden werden kann, ist wieder ein algorithmischer Aspekt und mit der Idee einer "Primzahlformel" eigentlich nicht vereinbar. Der Computer sollte eigentlich nur in eine fertige Formel einsetzen und von darüber hinaus gehenden Möglichkeiten nicht Gebrauch machen, sonst sind wir gleich wieder bei einem "Algorithmus" zur Erzeugung von Primzahlen. Was den Geschwindigkeitszuwachs betrifft, so glaube ich allerdings, dass er in erster Linie auf die "ausgelagerte" Funktion FibMod zurückzuführen ist.

Ja, ich habe beim Herumexperimentieren mit den diversen Fib-Funktionen auch schon festgestellt, dass da teilweise überraschende Sonderfälle auftreten. Das verunsichert einen dann auch etwas, weil man sich fragt, ob denn am grundsätzlichen Algorithmus etwas falsch ist oder ob nur die entsprechende Fib-Funktion falsche Werte liefert. Diese Fibonacci-basierte Variante scheint nicht besonders zuverlässig zu sein.

Naja, die im Zusammenhang mit der Fibonacci-Folge verwendeten Primzahltests sind eben prinzipiell nur probabilistisch, d.h., mit einer gewissen -wenngleich  i.allg. kleinen  - Wahrscheinlichkeit können auch Fehler auftreten. Was mich jetzt doch ein wenig überrascht hat, dass auch in meinem Programm aus #198 mit derselben Grundidee bereits unter 100000 zwei solche Fehlfunktionen auftraten, auch wenn das im Vergleich zum Programm von hyperG sehr wenige sind. Und ja, auch wenn man alle anderen Einwände gegen hyperG's Programm möglicherweise irgendwie beseitigen kann, diesen einen eben nicht, eine Primzahlformel, welche auch falsche Resultate liefern kann, das geht nun mal gar nicht!  biggrin

PS: Falls du noch vor haben solltest,  mein Programm aus #191 in Mathematica zu übersetzen, dann unbedingt die Version aus #198 nehmen, welche viel "cleaner" und auch schneller ist, da die Fibonaccifolge darin wie ich finde extrem "ökonomisch" und insbesondere auch "matrizenfrei" realisiert wurde.  wink



  Profil  Quote  Link auf diesen Beitrag Link
matph
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 20.11.2006
Mitteilungen: 5226
Aus: A
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.201, eingetragen 2017-02-17 22:47


Hallo,

@weird:
Die Maple Funktktion nextprime ist in Wirklichkeit der gleiche Aufruf zur Funktion mpz_nextprime, welche nichts anderes macht, als die folgenden Zahlen via Miller-Rabin-Test zu überprüfen, bis eine neue Primzahl oder in extrem unwahrscheinlichen Fällen starke Pseudoprimzahl gefunden ist, siehe hier - unsere Programme sind daher de facto identisch...

@all:
Ganz allgemein sollte man schon feststellen, natürlich handelt es sich bei diesem Test nicht um einen arithmetischen Ausdruck oder ein Polynom, doch dies trifft auch auf die anderen Möglichkeiten nicht zu, und als analytischer Ausdruck lässt sich dieser durchaus ebenfalls theoretisch darstellen smile

--
mfg
matph


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



  Profil  Quote  Link auf diesen Beitrag Link
weird
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.10.2009
Mitteilungen: 2873
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.202, eingetragen 2017-02-17 23:31


2017-02-17 22:47 - matph in Beitrag No. 201 schreibt:

Die Maple Funktktion nextprime ist in Wirklichkeit der gleiche Aufruf zur Funktion mpz_nextprime, welche nichts anderes macht, als die folgenden Zahlen via Miller-Rabin-Test zu überprüfen, bis eine neue Primzahl oder in extrem unwahrscheinlichen Fällen starke Pseudoprimzahl gefunden ist, siehe hier - unsere Programme sind daher de facto identisch...

Das ist buchstäblich nur die halbe Wahrheit, denn nextprime() basiert ganz wesentlich auf isprime(), und diese Funktion benützt zwar einen Miller-Rabin-Test (zur Basis 2?), das ist richtig, aber darüber hinaus auch einen Baillie-PSW-Test, der auf Lucasfolgen beruht (siehe hier). Das macht die von dir zitierte Funktion nicht(!), aber erst diese Kombination macht eigentlich die Stärke des Tests aus.

Ganz allgemein sollte man schon feststellen, natürlich handelt es sich bei diesem Test nicht um einen arithmetischen Ausdruck oder ein Polynom, doch dies trifft auch auf die anderen Möglichkeiten nicht zu, und als analytischer Ausdruck lässt sich dieser durchaus ebenfalls theoretisch darstellen smile

Dass dies generell auch auf die "anderen Möglichkeiten" nicht zutrifft, sehe ich jetzt nicht ein, inwiefern könnte damit eine Formel wie z.B. die aus #83 gemeint sein? Ich weiß nicht, wie weit du diese Diskussion hier mitverfolgt hast, die inzwischen ja schon sehr umfangreich geworden ist, aber um die Darstellbarkeit als Formel in den einfachsten arithmetischen Grundfunktionen, in welche man nur einzusetzen braucht, um die Primzahlen der Reihe nach in der natürlichen Reihenfolge zu erhalten, darum geht es ja hier gerade. Dass dies auch bei Verwendung von Miller-Rabin-Tests noch möglich ist, halte ich zwar jetzt nicht für ausgeschlossen, trivial ist es aber nicht und muss erst noch bewiesen werden. Und ja, wie hier auch schon mehrfach betont wurde, sollte eine "echte" Primzahlformel nicht schon von der Theorie her fallweise auch fehlerhafte Ergebnisse liefern können.  wink



  Profil  Quote  Link auf diesen Beitrag Link
matph
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 20.11.2006
Mitteilungen: 5226
Aus: A
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.203, eingetragen 2017-02-18 00:14


Hallo,

2017-02-17 23:31 - weird in Beitrag No. 202 schreibt:
Das ist buchstäblich nur die halbe Wahrheit, denn nextprime() basiert ganz wesentlich auf isprime(), und diese Funktion benützt zwar einen Miller-Rabin-Test (zur Basis 2?), das ist richtig, aber darüber hinaus auch einen Baillie-PSW-Test
Dies geht aus der Maple-Dokumentation die in Beitrag No.201 verlinkt ist allerdings nicht hervor, ganz im Gegenteil, hier steht das es sich um die Funktionen aus GMP handelt, und in diesen wird kein Baillie-PSW-Test eingesetzt.

2017-02-17 23:31 - weird in Beitrag No. 202 schreibt:
Dass dies generell auch auf die "anderen Möglichkeiten" nicht zutrifft, sehe ich jetzt nicht ein, inwiefern könnte damit eine Formel wie z.B. die aus #83 gemeint sein? Ich weiß nicht, wie weit du diese Diskussion hier mitverfolgt hast, die inzwischen ja schon sehr umfangreich geworden ist, aber um die Darstellbarkeit als Formel in den einfachsten arithmetischen Grundfunktionen, in welche man nur einzusetzen braucht, um die Primzahlen der Reihe nach in der natürlichen Reihenfolge zu erhalten, darum geht es ja hier gerade.

Ich muss zugeben, ich habe nicht alle Beiträge gelesen, doch ich denke wir sprechen aneinander vorbei, denn ein arithmetischer Ausdruck darf keine Potenzen und erst recht keine Logarithmieren oder ähnliches enthalten, und in den Beiträgen welche ich gesehen habe, ist dies sehr wohl der Fall - es handelt sich um analytische Ausdrücke...

2017-02-17 23:31 - weird in Beitrag No. 202 schreibt:
Dass dies auch bei Verwendung von Miller-Rabin-Tests noch möglich ist, halte ich zwar jetzt nicht für ausgeschlossen, trivial ist es aber nicht und muss erst noch bewiesen werden.

Als arithmetischer Ausdruck nein, als analytische Ausdruck ja, man kann z.B. diese Implementierung (1.2 Miller-Rabin Primality Test) nehmen, die Guards in Heaviside-Funktionen umschreiben, f und iter lassen sich durch Summen darstellen, welche dann entsprechend multipliziert werden, natürlich für die Praxis denkbar ineffizient, doch es geht ja nur um die Machbarkeit... smile

2017-02-17 23:31 - weird in Beitrag No. 202 schreibt:
Und ja, wie hier auch schon mehrfach betont wurde, sollte eine "echte" Primzahlformel nicht schon von der Theorie her fallweise auch fehlerhafte Ergebnisse liefern können.  wink

Natürlich, deshalb heißt es ja auch probabilistisch, doch ich denke dies war auch allen Mitlesern ohnehin bewusst cool
Mit meinem ursprünglichen Beitrag ging es mir nur darum, zu sagen, dass wenn man schon den Miller-Rabin-Test einsetzt, die Rechenzeit natürlich extrem gering im Vergleich zu den anderen vorgestellten Methoden wird (du hast vom Start bis ins Ziel in Abfahrtshocke durchfahren gesprochen - dann kann man dazu auch seinen Rennanzug dafür auspacken...)

--
mfg
matph


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



  Profil  Quote  Link auf diesen Beitrag Link
weird
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.10.2009
Mitteilungen: 2873
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.204, eingetragen 2017-02-18 01:14


2017-02-18 00:14 - matph in Beitrag No. 203 schreibt:
Dies geht aus der Maple-Dokumentation die in Beitrag No.201 verlinkt ist allerdings nicht hervor, ganz im Gegenteil, hier steht das es sich um die Funktionen aus GMP handelt, und in diesen wird kein Baillie-PSW-Test eingesetzt.

Naja, und mein Link aus Beitrag #202 widerspricht dem ganz klar, was den Aufbau der isprime()-Funktion in Maple betrifft, also kannst du dir dann aussuchen was glaubwürdiger ist. Für jeden, der sich allerdings auch nur ein bißchen mit Primalitätstests auskennt, ist jedoch ganz klar, dass ein einzelner Miller-Rabin-Test viel zu schwach wäre und sich da Beispiele fast nach Belieben finden ließen, in denen er nicht funktioniert, d.h., kein CAS, das etwas auf sich hält, könnte sich das leisten, schon gar nicht Maple. Magma verwendet z.B. gleich 20 Stück davon und selbst das erscheint mir für sich allein genommen noch eher fragwürdig.

Ich muss zugeben, ich habe nicht alle Beiträge gelesen, doch ich denke wir sprechen aneinander vorbei, denn ein arithmetischer Ausdruck darf keine Potenzen und erst recht keine Logarithmieren oder ähnliches enthalten, und in den Beiträgen welche ich gesehen habe, ist dies sehr wohl der Fall - es handelt sich um analytische Ausdrücke...

Warum ein arithmetischer Ausdruck keine Potenzen enthalten darf, versteh ich zwar nicht, aber wir können uns gerne auf "analytischer Ausdruck" einigen, solange nicht von den Möglichkeiten eines Computerprogramms wie z.B. Schleifenkonstrukte oder if-Abfragen Gebrauch gemacht wird, da man ja sonst gleich von "Algorithmen" zur Erzeugung von Primzahlen sprechen könnte. Dies wäre zwar auch ein durchaus interessantes Thema, entspricht aber nicht der Grundintention dieses Threads.

Natürlich, deshalb heißt es ja auch probabilistisch, doch ich denke dies war auch allen Mitlesern ohnehin bewusst cool

Dessen bin ich mir nicht so sicher. Und natürlich kann man auch probabilistische Methoden in die Diskussion miteinbeziehen, wie es hier ja auch durch die Beiträge von hyperG und die Diskussion darüber auch geschehen ist. Ob man da aber dann noch von einer "Primzahlformel" im strengen Sinn des Wortes sprechen kann, wenn sie mit Sicherheit auch falsche Resultate liefert, und das sogar unendlich oft, das würde ich jetzt eigentlich klar verneinen.  wink



  Profil  Quote  Link auf diesen Beitrag Link
matph
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 20.11.2006
Mitteilungen: 5226
Aus: A
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.205, eingetragen 2017-02-18 02:03


Hallo,

2017-02-18 01:14 - weird in Beitrag No. 204 schreibt:
Naja, und mein Link aus Beitrag #202 widerspricht dem ganz klar, was den Aufbau der isprime()-Funktion in Maple betrifft, also kannst du dir dann aussuchen was glaubwürdiger ist.

Der Wikipediaartikel gibt für Maple's isprime function Referenz 11 an, dies ist die isprime - Maple Help. Auf dieser Seite wird zwar nicht explizit auf mpz_probab_prime_p aus GMP verwiesen, allerdings nicht sonderlich überraschend auf die selbe Quelle des Algorithmus wie bei GMP - Knuth, The Art of Computer Programming Vol. 2, und hier auf Seite 379 findet man die Beschreibung des verwendeten Miller-Rabin Tests. Die Seite selbst spricht allerdings tatsächlich noch von einem Lucas Test.

Nach dem es hier allerdings nicht um eine Glaubenssache gehen sollte, und es relativ leicht zu testen ist, welche der beiden Maple Seiten korrekt ist: Falls nextprime(189452997113368438678230) 189452997113368438678273 liefert, wird wie in isprime - Maple Help vermutlich noch ein Lucas Test durchgeführt, falls das Ergebnis 189452997113368438678231 ist, so wird nur mpz_probab_prime_p(p,k) mit k<14 verwendet smile

Wie man einen Ausdruck nennt ist nur Konvention, allerdings sollten alle beteiligten das selbe darunter verstehen, auf wikipedia gibt es eine nette Übersicht, was meist damit gemeint ist...

--
mfg
matph


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



  Profil  Quote  Link auf diesen Beitrag Link
weird
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.10.2009
Mitteilungen: 2873
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.206, eingetragen 2017-02-18 09:16


2017-02-18 02:03 - matph in Beitrag No. 205 schreibt:
Nach dem es hier allerdings nicht um eine Glaubenssache gehen sollte, und es relativ leicht zu testen ist, welche der beiden Maple Seiten korrekt ist: Falls nextprime(189452997113368438678230) 189452997113368438678273 liefert, wird wie in isprime - Maple Help vermutlich noch ein Lucas Test durchgeführt, falls das Ergebnis 189452997113368438678231 ist, so wird nur mpz_probab_prime_p(p,k) mit k<14 verwendet smile

Ok, dann kann man ja mit nachfolgendem Test

Maple 2015
nextprime(189452997113368438678230)
                    189452997113368438678273
 

diese Sache wohl endgültig - und nun auch für dich - abhaken.   biggrin

Falls du übrigens Genaueres zum Primzahltest in isprime() finden willst, solltest du dann nicht auf irgendwelche dubiose Quellen zurückgreifen, sondern gleich auf sowas wie hier.  

PS: In dem oben zitierten Artikel steht auch, dass es in der "Frühzeit" von Maple tatsächlich noch Versionen gab, wo isprime() nur auf Miller-Rabin-Tests basierte. Natürlich war es child's play da konkrete "Löcher" aufzuzeigen - wahrlich ein Supergau für ein renommiertes CAS. Aber inzwischen haben sie ja ihre Hausaufgaben längst gemacht, auch wenn das an einigen Leuten hier *räusper* vorbeigegangen ist.   wink



  Profil  Quote  Link auf diesen Beitrag Link
Primentus
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 18.02.2016
Mitteilungen: 154
Aus: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.207, eingetragen 2017-02-18 17:46


2017-02-17 22:27 - weird in Beitrag No. 200 schreibt:
Auch dieses "Zwischenspeichern", sofern es nicht vermieden werden kann, ist wieder ein algorithmischer Aspekt und mit der Idee einer "Primzahlformel" eigentlich nicht vereinbar. Der Computer sollte eigentlich nur in eine fertige Formel einsetzen und von darüber hinaus gehenden Möglichkeiten nicht Gebrauch machen, sonst sind wir gleich wieder bei einem "Algorithmus" zur Erzeugung von Primzahlen. Was den Geschwindigkeitszuwachs betrifft, so glaube ich allerdings, dass er in erster Linie auf die "ausgelagerte" Funktion FibMod zurückzuführen ist.

Ja, ich gebe Dir insofern Recht, dass das mit dem Zwischenspeichern zumindest nicht mehr formeltauglich ist, aber immerhin hat sich hyperG noch an das Prinzip der Aufsummierung wie sie in der Primzahlformel stattfindet, gehalten und nicht einen gänzlich anderen Algorithmus genommen. Streng genommen müssen wir aber natürlich sagen, dass die Funktion nicht mehr im ursprünglichen Sinne der Primzahlformel ist. Was den Geschwindigkeitszuwachs betrifft, so glaube ich jedoch eher, dass das auf das Zwischenspeichern zurückzuführen ist und nicht so sehr auf die Funktion FibMod.

2017-02-17 22:27 - weird in Beitrag No. 200 schreibt:
Naja, die im Zusammenhang mit der Fibonacci-Folge verwendeten Primzahltests sind eben prinzipiell nur probabilistisch, d.h., mit einer gewissen -wenngleich  i.allg. kleinen  - Wahrscheinlichkeit können auch Fehler auftreten.

Okay, ich dachte ursprünglich, dass es da nur anfangs einige (endlich viele) Ausnahmen gibt und die Fibonacci-Folge anschließend zuverlässig für die Primalitätsprüfung verwendet werden kann. Aber wenn probabilistisch hier das Stichwort ist, dann wird es natürlich klar. Aber dann finde ich diese Methode der Primalitätsprüfung generell nicht besonders gut, weil man die Funktion ja ständig "flicken und reparieren" muss für immer größere n. Da hätte ich doch schon gern lieber eine zuverlässige Formel. Daher bin ich nach wie vor einfach ein Fan der Primzahlformeln, weil sie einfach zuverlässig fehlerfrei arbeiten, auch wenn man in Kauf nehmen muss, dass sie im Vergleich zu den "Schi"-Funktionen nicht so schnell sind. Dann lieber langsam und gemächlich ans Ziel als hoppla-di-hopp auf die Schnauze fallen. biggrin

2017-02-17 22:27 - weird in Beitrag No. 200 schreibt:
2017-02-17 19:02 - Primentus in Beitrag No. 199 schreibt:
Hab allerdings in Mathematica noch kein Analogon für die Funktion next gefunden. Man braucht sie aber noch in einer anderen Code-Zeile. Mal schauen, ob ich da noch was finde.

In manchen Programmiersprachen heißt dieser Befehl continue.

Danke für den Hinweis. Es gibt in Mathematica sogar einen Continue[]-Befehl, aber der scheint dieselbe Bededeutung wie Break[] zu haben. Ich hab dann noch ein bisschen weiter gesucht und habe nun die Lösung gefunden: es ist der Goto[]-Befehl in Kombination mit dem Label[]-Befehl (Sprungmarke).

2017-02-17 22:27 - weird in Beitrag No. 200 schreibt:
PS: Falls du noch vor haben solltest,  mein Programm aus #191 in Mathematica zu übersetzen, dann unbedingt die Version aus #198 nehmen, welche viel "cleaner" und auch schneller ist, da die Fibonaccifolge darin wie ich finde extrem "ökonomisch" und insbesondere auch "matrizenfrei" realisiert wurde.  wink

Hab ich nun gemacht und die Funktion NthPrimeSchi genannt (weil ich den Schi-Vergleich einfach so genial finde). Et voilà:
Mathematica
f[x_List] := {x[[1]]+x[[2]], x[[1]]+2*x[[2]]}
NthPrimeSchi[k_] := 
  Module[{a = {0, 1}, d = 4, i = 2, p = 1, q, t},
    If[k < 3, Return[k + 1]];
    While[True, 
      i = i + 1;
      If[i > k, Return[p]];
      While[True,
        p = p + d;
        a = f[a];
        If[d == 4, a = f[a]];
        d = 6 - d;
        q = p - 1;
        If[MemberQ[{252601, 741751}, p], Goto[endofwhile]];
        While[Mod[q, 2] == 0,
          q = q/2;
          t = Mod[2^q, p];
          If[t > 1, Break[]]
        ] 
        If[(t < p - 1) && (t*Mod[q, 2] != 1), Goto[endofwhile]];
        If[p == 5 || (Mod[a[[1]], p] + Mod[a[[1]] + a[[2]], p]) == 1, Break[]];
	Label[endofwhile]
      ]
      (* If[!PrimeQ[p], Return[p]]; *)
    ]
  ]
 
Timing[NthPrimeSchi[100]]
Timing[NthPrimeSchi[500]]
Timing[NthPrimeSchi[1800]]
Timing[NthPrimeSchi[10000]]
Timing[NthPrimeSchi[100000]]
Ergebnis:
Mathematica
{0. Second, 541}
{0.047 Second, 3571}
{0.265 Second, 15401}
{5.694 Second, 104729}
{1031.88 Second, 1299709}

Wie man sieht, ist Mathematica für größere k bei mir nicht so schnell wie Maple, was denke ich wieder an der etwas langsamen Mod-Funktion von Mathematica liegt.

LG Primentus

Edit: Ich habe die Berechnungen nochmal neu durchgeführt und die Berechnungszeiten nochmal aktualisiert, da ich festgestellt habe, dass ich noch ein anderes Programm laufen hatte, das die Berechnungen etwas beeinträchtigt hat. An der Tatsache, dass die Funktion für größere k sehr langsam wird, ändert das aber nichts.



  Profil  Quote  Link auf diesen Beitrag Link
weird
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.10.2009
Mitteilungen: 2873
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.208, eingetragen 2017-02-18 19:05


2017-02-18 17:46 - Primentus in Beitrag No. 207 schreibt:
Es gibt in Mathematica sogar einen Continue[]-Befehl, aber der scheint dieselbe Bededeutung wie Break[] zu haben. Ich hab dann noch ein bisschen weiter gesucht und habe nun die Lösung gefunden: es ist der Goto[]-Befehl in Kombination mit dem Label[]-Befehl (Sprungmarke).

Hm, ich habe nach Beispielen im Internet gesucht, wo Continue[] verwendet wird (z.B. hier) und es scheint wirklich exakt das zu machen, was es soll, nämlich den restlichen Schleifeninhalt danach zu überspringen. In dem verlinkten Beispiel wird für gerade Zahlen also dann die Anweisung r+=i übersprungen, sodass als dann nur die ungeraden Zahlen im Intervall [1,10] aufsummiert werden, was tatsächlich 25 ergibt. Außerdem verwendest du eine While-Schleife der Form While[True,...], wo Mathematica eigentlich Do[] vorgesehen hat, wenn ich dieses Beispiel jetzt richtig interpretiere.

Hab ich nun gemacht und die Funktion NthPrimeSchi genannt (weil ich den Schi-Vergleich einfach so genial finde). Et voilà: [...]

Ja, sehr nett, vielen Dank!  wink

Die seltsamen Sprünge in den Berechnungszeiten für größere Argumente sind allerdings wirklich mysteriös. Vielleicht überwinde ich ja eines Tages noch meine ausgeprägte Idiosynkrasie gegen dieses CAS, um dann auch ein bißchen mitreden zu können, wenn es um solche Dinge geht!   biggrin  



  Profil  Quote  Link auf diesen Beitrag Link
Primentus
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 18.02.2016
Mitteilungen: 154
Aus: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.209, eingetragen 2017-02-18 19:37


2017-02-18 19:05 - weird in Beitrag No. 208 schreibt:
Hm, ich habe nach Beispielen im Internet gesucht, wo Continue[] verwendet wird (z.B. hier) und es scheint wirklich exakt das zu machen, was es soll, nämlich den restlichen Schleifeninhalt danach zu überspringen.

Jetzt hab ich in der fertigen Funktion NthPrimeSchi nochmal den Goto[]-Befehl durch Continue[] ausgetauscht und siehe da, es geht sogar - Du hast also recht. Es funktionieren beide Varianten. Hinsichtlich Berechnungszeiten gibt es aber praktisch keine Unterschiede zwischen beiden Varianten.

2017-02-18 19:05 - weird in Beitrag No. 208 schreibt:
Außerdem verwendest du eine While-Schleife der Form While[True,...], wo Mathematica eigentlich Do[] vorgesehen hat, wenn ich dieses Beispiel jetzt richtig interpretiere.

Ja, es gibt in Mathematica auch ein Do[], aber da ist das Problem, dass man wie bei For[] die Laufvariablengrenzen vorab wissen und angeben muss (wie in Deinem verlinkten Beispiel das {i,1,10}), was in unserem Fall aber nicht gegeben ist. Also musste ich ein While[True, ...] verwenden, was zwar eigentlich eine Endlosschleife ist, aber da innerhalb des While[] zuverlässige Abbruchbedingungen vorhanden sind, funktioniert es so wunderbar.

2017-02-18 19:05 - weird in Beitrag No. 208 schreibt:
Die seltsamen Sprünge in den Berechnungszeiten für größere Argumente sind allerdings wirklich mysteriös.

Ja, die Sprünge sind schon etwas merkwürdig, aber ich denke wirklich, dass das an der Mod-Funktion liegt, die in Mathematica für größere Argumente einfach immer langsamer wird, was ich ja bei der Beschäftigung mit den Fib-Funktionen schon festgestellt habe. Scheinbar arbeitet Maple da effizienter.

2017-02-18 19:05 - weird in Beitrag No. 208 schreibt:
Vielleicht überwinde ich ja eines Tages noch meine ausgeprägte Idiosynkrasie gegen dieses CAS, um dann auch ein bißchen mitreden zu können, wenn es um solche Dinge geht!   biggrin  

Oh, das wusste ich gar nicht, dass Du so eine große Abneigung gegen Mathematica hast. Ich liiiebe dieses System ehrlich gesagt - sogar noch mehr als meine absoluten Lieblings-Computergames und das will was heißen. wink

LG Primentus



  Profil  Quote  Link auf diesen Beitrag Link
hyperG
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 34
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.210, eingetragen 2017-02-18 21:38


Hallo weird,

ich habe mal den Pseudoprimzahl-Suchalgorithmus
t:=time():nthprime(10000),(time()-t)*'s'
                        104729, 0.141 s
 
t:=time():nthprime(100000),(time()-t)*'s'
                        1299709, 1.734 s


mit der fertigen JAVA-Funktion verglichen:
...
long offs=gesIndex-gegIndex;
for(c2 = 0; c2 < offs; c2++)
{    bi3 = bi3.nextProbablePrime();
}
System.out.println("Prime("+(gesIndex)+")="+bi3+" in "+(System.currentTimeMillis()-seed)+"ms");
 
Prime(100000)=1299709 in 4.633 s
Prime(1000000)=15485863 in 47.780 s



Vorteil dabei:
- man kann auf bekannten Werten aufbauen und an beliebiger Stelle weiterrechnen
- erste Fehler sollen erst oberhalb 9000 Stellen kommen

Interessant dürfte es bei noch größeren Zahlen werden...



  Profil  Quote  Link auf diesen Beitrag Link
weird
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.10.2009
Mitteilungen: 2873
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.211, eingetragen 2017-02-19 07:49


2017-02-18 21:38 - hyperG in Beitrag No. 210 schreibt:
Prime(100000)=1299709 in 4.633 s
Prime(1000000)=15485863 in 47.780 s

Wenn da Java-intern "ehrlich" gerechnet wurde, sind diese Zeiten sehr respektabel. In vielen Programmiersprechen ist es aber so, dass bei solchen Rechnungen sehr viel auf vorausberechnete Tabellen zurückgegriffen wird, deren Werte gewissermaßen als "Stützwerte" dienen, von denen aus dann erst "wirklich" gerechnet wird. Dem User kann das nur Recht sein, denn er bekommt damit das gewünschte Ergebnis schneller, Rechenzeitvergleiche mit eigenen Programmen ohne "cheating" (s. z.B. #198 bzw. #207) werden damit aber fast sinnlos.

Und ja, wenn du schreibst, dass "Fehler" beim oben verwendeten probabilistischen Primzahltest erst jenseits von 9000 Stellen auftreten sollten, dann frage ich mich schon ein bißchen, wie "seriös" diese Aussage ist. Jedenfalls dürfte sie schwer zu widerlegen sein.  biggrin



  Profil  Quote  Link auf diesen Beitrag Link
weird
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.10.2009
Mitteilungen: 2873
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.212, eingetragen 2017-02-19 08:44


2017-02-18 19:37 - Primentus in Beitrag No. 209 schreibt:
Jetzt hab ich in der fertigen Funktion NthPrimeSchi nochmal den Goto[]-Befehl durch Continue[] ausgetauscht und siehe da, es geht sogar - Du hast also recht. Es funktionieren beide Varianten. Hinsichtlich Berechnungszeiten gibt es aber praktisch keine Unterschiede zwischen beiden Varianten.

Da bin ich aber froh, denn Goto-Befehle sind eigentlich unter Programmierern ein absolutes No-Go.  biggrin


Oh, das wusste ich gar nicht, dass Du so eine große Abneigung gegen Mathematica hast. Ich liiiebe dieses System ehrlich gesagt - sogar noch mehr als meine absoluten Lieblings-Computergames und das will was heißen. wink

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



  Profil  Quote  Link auf diesen Beitrag Link
hyperG
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 34
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.213, eingetragen 2017-02-19 12:23


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: 5226
Aus: A
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.214, eingetragen 2017-02-19 17:32


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



  Profil  Quote  Link auf diesen Beitrag Link
weird
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.10.2009
Mitteilungen: 2873
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.215, eingetragen 2017-02-19 18:24


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



  Profil  Quote  Link auf diesen Beitrag Link
hyperG
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 34
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.216, eingetragen 2017-02-19 18:34


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: 5226
Aus: A
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.217, eingetragen 2017-02-19 18:54


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



  Profil  Quote  Link auf diesen Beitrag Link
hyperG
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 34
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.218, eingetragen 2017-02-19 19:01


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: 2873
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.219, eingetragen 2017-02-20 08:40


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



  Profil  Quote  Link auf diesen Beitrag Link
Primentus
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 18.02.2016
Mitteilungen: 154
Aus: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.220, eingetragen 2017-02-20 17:02


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



  Profil  Quote  Link auf diesen Beitrag Link
hyperG
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 34
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.221, eingetragen 2017-02-20 22:21


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: 154
Aus: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.222, eingetragen 2017-02-21 00:18


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



  Profil  Quote  Link auf diesen Beitrag Link
matph
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 20.11.2006
Mitteilungen: 5226
Aus: A
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.223, eingetragen 2017-02-21 02:46


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



  Profil  Quote  Link auf diesen Beitrag Link
Slash
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.03.2005
Mitteilungen: 4736
Aus: New York
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.224, eingetragen 2017-02-21 04:50


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.


-----------------
Drei kleine Regeln, die dich sicher durchs Leben bringen. 1. Vertritt mich mal eben! 2. Oh, gute Idee, Chef! 3. Das war bestimmt jemand anders! (Homer Simpson)



  Profil  Quote  Link auf diesen Beitrag Link
matph
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 20.11.2006
Mitteilungen: 5226
Aus: A
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.225, eingetragen 2017-02-21 05:25


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



  Profil  Quote  Link auf diesen Beitrag Link
hyperG
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 34
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.226, eingetragen 2017-02-21 11:42


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: 2873
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.227, eingetragen 2017-02-21 13:37


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



  Profil  Quote  Link auf diesen Beitrag Link
Primentus
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 18.02.2016
Mitteilungen: 154
Aus: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.228, eingetragen 2017-02-21 17:39


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



  Profil  Quote  Link auf diesen Beitrag Link
hyperG
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 34
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.229, eingetragen 2017-02-22 00: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: 2873
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.230, eingetragen 2017-02-22 07:35


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



  Profil  Quote  Link auf diesen Beitrag Link
fermare wird per Mail über neue Antworten informiert.
Seite 6Gehe zur Seite: 1 | 2 | 3 | 4 | 5 | 6  
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]