Mersenne number primality test program

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

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

[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. Um diesen Test durchzuführen, ist es 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. Kleiner Tipp: Verwende die Routinen von Rudy Velthuis nicht in Free Pascal, sondern eher in Delphi. In Free Pascal treten diverse Schwierigkeiten auf.

Wenn Du Fragen hast, helfe ich Dir gerne weiter.

Das Sternenlicht...

[Pedaltreter]

Hallo Sternenlicht,
leider habe ich nur Lazarus auf meinem Computer installiert und werde die Implementationen von Velthuis nicht integrieren können.
Außerdem habe ich bei sehr großen und umfangreichen Berechnungen das Problem, dass meine Anwendung einfriert. Damit meine ich, dass zwar die Berechnungen weiter laufen, allerdings kann ich in der Zeit kein Menü bedienen. Hast Du eine Idee, wie ich die Probleme lösen kann?
Gruß, Pedaltreter.

[Sternenlicht]

Lieber Pedaltreter,

lieben Dank für Deine Mitteilung. Du hattest lange nichts von Dir hören lassen, so habe ich nicht mehr nachgeschaut, ob Du zurückgeschrieben hattest. Entschuldige mir das bitte!

Kurze Frage vorweg: Hast Du denn inzwischen die Probleme lösen können?
Wenn Du die Velthuis - Module in oder mit Lazarus nicht implementieren kannst, so verwende doch einfach das Embarcadero RAD Studio. Inzwischen ist die Version bei 11 angekommen. Die Community - Edition ist meines Erachtens kostenlos, solange Du das Programm für private Zwecke verwendest. Du kannst es auf der Seite:

www.embarcadero.com

erwerben. Bevor ich jedoch etwas Falsches geschrieben habe, ließ Dir die Lizenzbedingungen durch.

Zu dem Problem mit dem Einfrieren des Programmes, kann ich Dir folgenden Lösungsvorschlag machen: Lass die Berechnungen in einem sogenannten Threat laufen. Den Haupt- Threat verwendest Du dann nur für Deine Bildschirmausgaben und für die Bedienung der Menüs. Alternativ kannst Du auch kleine Pausen zwischen den Berechnungen einlegen, damit Ressourcen für die Bildschirmausgaben frei werden. Allerdings laufen dadurch die Berechnungen etwas langsamer. Daher wäre ein zusätzlicher Threat eine relativ einfache und effiziente Methode, um das Problem zu lösen.

Gib mir einfach Bescheid, sonst kann ich Dir gerne helfen, wenn Du nicht weiterkommst.

Liebe Grüße, das Sternenlicht...