Mersenne number primality test program

Die Welt der Zahl. Interessierst Du Dich für Primzahlen, Mersenne Primzahlen und für die Mathematik? Hier findest Du interessante Verlinkungen zu Seiten und Projekten
Benutzeravatar
Sternenlicht
Administrator
Beiträge: 135
Registriert: 29.04.2018, 14:38:26
Wohnort: Dortmund

Re: Primzahlen im 100-stelligem Bereich mit Pascal

Beitrag von Sternenlicht »

Hallo lieber Pedaltreter,

es ist natürlich klar, dass die Berechnungen von Primzahlen immer länger dauern, je größer die zu berechnende Zahl wird. Erschwerend wirkt es sich zeitlich auch noch darauf aus, dass mit Strings gerechnet wird, anstatt mit Real-, Extended- bzw. Integer- Zahlen.

Die von mir dargelegten Routinen mit String Berechnungen funktionieren lediglich, auch wenn sie zeitintensiver sind. Außerdem können die Routinen sicherlich, sofern sie zur Berechnung von Primzahlen eingesetzt werden, noch verfeinert und effektiver programmiert werden. Bei der Berechnung von Primzahlen müssen nicht alle Fehlerüberprüfungen vorgenommen werden, wie sie in die einzelnen Funktionen eingesetzt wurden, weil die Fehler von vornherein vermieden werden können. Auch die Überprüfung auf negative Zahlen kann wegfallen, weil dies nur Zeit kostet und negative Zahlen bei der Primzahlberechnung wohl nicht vorkommt.

Weitere Optimierungen können bei der schriftlichen Division vorgenommen werden. Zum Beispiel basiert diese hauptsächlich auf das Subtrahieren. Sollte der Divisor noch im Wertebereich von int64 Variablen sein, wäre die Subtraktion mit Integer in Erwägung zu ziehen.

Auch die Optimierung des Wurzelziehens sollte in Betracht gezogen werden. Bei meiner Berechnung wurde ein Algorithmus der schrittweisen Annäherung herangezogen. Kann man machen, es gibt jedoch auch andere Algorithmen, wie zum Beispiel die Ansicht eines Geometriebeispiels: Möchte ich die Wurzel aus 25 ziehen, kann ich mir ein Rechteck vorstellen von 25 * 1. Jetzt versuche ich das Rechteck zu einem Quadrat zu führen: 2 * 12.5, 3 * 8.3, bis ich auf 5 * 5 komme.

Letzten Endes bleibt zu überlegen, ob die String Berechnung wirklich das Optimalste ist, oder ob es noch andere Möglichkeiten gibt. Meine dargelegten Routinen waren nur ein funktionales Beispiel, was sich sicherlich auf vielfältiger Weise optimieren lässt.

Liebe Grüße, das Sternenlicht...
Guten Morgen!

Hier spricht das Universum!
Ich werde mich heute um all Deine Probleme kümmern!
Dazu benötige ich Deine Hilfe nicht!

Also genieße den Tag!
Pedaltreter
Beiträge: 16
Registriert: 12.07.2018, 21:11:52

Re: Mersenne number primality test program

Beitrag von Pedaltreter »

Hallo Sternenlicht,
vielen Dank für Deine Geduld. Deine Pascal- Routinen sind sehr zuverlässig, wobei allerdings die Laufzeiten nur für begrenzte Zahlen geeignet zu sein scheinen. Wir haben im Seminar den Lucas-Lehmer-Test für Mersenne- Zahlen besprochen. Promt wollte ich dazu einen Code in Pascal schreiben und bin dabei wieder an meine Grenzen gestoßen. Der Lucas-Lehmer-Test mit Deinem Programmcode dauert für die Zahl (2^99991)-1 ganze 139 Tage. Ich überlege, ob man da nicht weitere Optimierungen vornehmen kann.
Der Pedaltreter.
Benutzeravatar
Sternenlicht
Administrator
Beiträge: 135
Registriert: 29.04.2018, 14:38:26
Wohnort: Dortmund

Re: Mersenne number primality test program

Beitrag von Sternenlicht »

Lieber Pedaltreter,

selbstverständlich kann man da noch diverse Optimierungen vornehmen. Mein selbstentwickelter Code für große Integer - Zahlen arbeitet mit String- Variablen. Das ist für sehr große Zahlen > 1000 Stellen überhaupt nicht effizient. Für Deine anfänglichen Wünsche, Zahlen im 100 stelligen Bereich zu berechnen, reichen die String- Verarbeitungen grundsätzlich noch aus.

Lazarus (Free Pascal) oder auch Delphi stellen keine so großen Datentypen für Integerzahlen zur Verfügung. Inzwischen habe ich auch etwas recherchiert. In der Programmiersprache #C (Sharp) unter Microsoft .NET gibt es den Biginteger - Typ. Damit lassen sich auch noch größere Zahlen zuverlässig verarbeiten.

Ich habe gerade mal überschlagen, Deine Berechnungen nach dem Lucas-Lehmer-Test (2^99991)-1 müsste eine ca. 30000 stellige Zahl ergeben. Damit diesen Test durchzuführen, ist nicht optimal, wenn Du meine Routinen verwendest.

Meines Erachtens hast Du zwei Möglichkeiten:
  • Du kannst solche Berechnungen besser mit Microsoft .Net in C#, Visual Basic oder C mit dem Datentyp Biginteger berechnen.
  • Auf der Seite: http://rvelthuis.de/programs/bigintegers.html wurde von Rudy Velthuis genau dieser "Biginteger" - Datentyp in Object - Pascal implementiert. Diese Seite wäre für Deine Zwecke die optimale Anlaufstelle, wenn Du weiterhin in Pascal programmieren möchtest.
Wenn Du Fragen hast, helfe ich Dir gerne weiter.

Das Sternenlicht...
Guten Morgen!

Hier spricht das Universum!
Ich werde mich heute um all Deine Probleme kümmern!
Dazu benötige ich Deine Hilfe nicht!

Also genieße den Tag!

Zurück zu „Mathematik“