Anschrift
Frauengasse 3-5
2500 Baden
02252 / 44403

Primzahltests mit Java und C# 06-04-2011

Der Rabin Miller Test

mime rabinnet.zip 73.7 KB mime 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 (mime 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 mime 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:
java.jpg     net.jpg
 

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