Der Rabin Miller Test
rabinnet.zip
73.7 KB
rabinjava.zip
24.4 KB
Vor einigen Jahren habe ich für C# den Rabin Miller Test implementiert.
Dieser Test dient dazu, Pseudoprimzahlen zu bestimmen. Der Test entscheidet also mit einer gewissen Wahrscheinlichkeit, ob eine Zahl eine Primzahl ist oder eben nicht. Eine kurze Zusammenfassung habe ich hier zusammengeschrieben (
rabin.pdf
115.9 KB
).
Die Sprache war C# auf .NET Basis. Da es keine Bibliothek für beliebig große Integer-Zahlen gab, habe ich die selbst geschrieben (kann man hier herunterladen
VLI.zip
160.7 KB
). Ob diese Bibliothek sehr performant ist, kann ich nicht sagen, aber sie dürfte fehlerfrei funktionieren. Wenn man Glück hat, wurde das .NET Framework mittlerweile mit einer solchen Bibliothek ausgestattet.
Da .NET nicht unbedingt plattformübergreifend ist (abgesehen von MONO), und unsere Schule eher Richtung Opensource geht, also mit Microsoft nicht so richtig etwas anfangen kann, sind wir nun auf Java umgestiegen.
In Java gibt es bereits eine Klasse für beliebig große Zahlen, nämlich BigInteger. Es gibt sogar den Rabin Miller und den Luca Lehmer Test in dieser Klasse. Trotzdem habe ich den „eigenen“ Rabin Miller Test in Java implementiert. Und möchte nun die Laufzeittests zwischen der C# und der Java Anwendung präsentieren.
In den Screenshots sehen Sie wie die beiden Programme aussehen:
Mit beiden Programmen habe ich einen 30 minütigen Test durchgeführt, mit folgenden Ergebnissen:
Java Programm | .NET C# Programm |
Größte Primzahl: 2150417 | Größte Primzahl: 282599 |
Gefundene Primzahlen: 134119 | Gefundene Primzahlen: 22791 |
Im nachfolgenden Diagramm sehen Sie die Berechnungsdauer für gefundene Primzahlen. Offensichtlich habe ich die Java Anwendung „besser“ geschrieben, da die Berechnungszeiten deutlich geringer sind (in Verwendung ist ein ThreadPool der Klasse ExecutorService, während bei C# nur ein Thread gearbeitet hat).