Kleiner UPN-Rechner für BigIntegers

[Landei]

Rechnen mit BigIntegers ist wirklich eine Qual. Nachdem ich eine Weile überlegt hatte, ein DSL für BigInteger zu schreiben, aber "dank" der recht starren Java-Syntax keine wesentliche Verbesserung gegenüber den vorhandenen Klassen erzielen konnte (jedenfalls keine, die den zusätzlichen Wrapperklassen-Aufwand rechtfertigen würde), habe ich meine Strategie geändert und bin zur Umgekehrt Polnische Notation umgeschwenkt. Ich weiß, die ist etwas gewöhnungsbedürftig. Hier als erstes Ergebnis ein Vergleich von Code für den Lucas-Lehmer-Test.

Konventionell (von Lucas-Lehmer test for Mersenne numbers (Java) - LiteratePrograms ):

    public static boolean lucasLehmer(int p) {
        BigInteger s = BigInteger.valueOf(4);
        BigInteger m = BigInteger.valueOf(2).pow(p).subtract(BigInteger.ONE);
        for (int i = 0; i < p - 2; i++) {
            s = s.multiply(s).subtract(BigInteger.valueOf(2)).mod(m);
        }
        return s.equals(BigInteger.ZERO);
    }

Und mit UPN:

    public static boolean lucasLehmerBIRPN(int p) {
        BigInteger s = _(4);
        BigInteger m = _(2, p, POW, DEC); // [2 p ^ --] -> (2^p)-1 
        for (int i = 0; i < p - 2; i++) {
            s = _(s, SQUARE, 2, MINUS, m, MOD); //[s ² 2 - m %] -> (s²-2) % m
        }
        return s.equals(_(0));
    }

Mir geht es erst einmal nur um die Syntax. Wenn ich daran weiterarbeite, kommt das Dingens auf Google Code. Das Beispiel funktioniert zwar schon, die Anzahl der verfügbaren Funktionen ist aber noch ziemlich beschränkt, und ich sehe auch noch einiges Optimierungspotential.

Natürlich kann man auch eine Erweiterung schreiben, die eine "normale" Infix-Eingabe zulässt (eventuell auch als zu parsenden String mit varargs á la printf), und hinter den Kulissen mittels Shuntingyard-Algorithmus in Postfix umwandelt.

Was meint ihr dazu?

[edit] Kleine Verbesserung in meinem Code.

 

[Landei]

Das Ding mutiert immer weiter unter meinen Händen. Zwar immer noch kein Infix, dafür ein Parser.

    public static boolean lucasLehmerParsed(int p) {
        BigInteger s = _("4");
        BigInteger m = _("2 $0 ^ --", p);
        for (int i = 0; i < p - 2; i++) {
            s = _("$0 ² 2 - $1 %", s, m);
        }
        return s.equals(_("0"));
    }

Noch ein kleines bisschen, und ich habe Forth (oder Joy, oder Cat, oder Factor) in Java...

 

[Landei]

OK, jetzt war es nur noch Fleißarbeit, den restlichen BigInteger-Krams (und ein paar eigene Sachen wie Fakultät) zu integrieren. Ergebnis steht hier: birpn - Project Hosting on Google Code

 

[steinitz]

Interessant! Ich suche gerade Java-Beispiele für das Rechnen in endlichen Körpern! Das geht so etwas in die Richtung.
Ein Hinweis wäre toll!

Was charakterisiert übrigens die Carmichael-Zahlen, die den Test Miller-Rabin-Test bestehen?

 

[Landei]

Version 0.2 ist fertig. Ich habe noch Funktionen hinzugefügt, etwa die ganzzahlige Wurzel (insgesamt sind es immerhin 55 Funktionen). Weiterhin unterstütze ich boolesche Logik (also logische Operatoren, Vergleichsoperatoren, if, isPrime, isSquare u.s.w), Ranges (erzeuge die Zahlen 5..20, Schrittweite 3) und Metafunktionen (eine gegebene Funktion auf alle Zahlen auf dem Stack anwenden). Ich habe alle Operatorn mit JUnit abgedeckt, dabei habe ich tatsächlich drei, vier Bugs gefunden. Das Modul ist erweiterbar, man kann eigene Funktionen oder Metafunktionen verwenden (nach Registrierung auch in der geparsten Version). Die Dokumentation habe ich erweitert, auch wenn sie noch nicht perfekt ist.

Download: http://birpn.googlecode.com/files/BIRPN-0.2.jar

Interessant ist, dass man sich relativ einfach eigene Funktionen oder Metafunktionen schreiben und ganz normal verwenden kann (für die Verwendung mit dem String-Aufruf müssen sie vorher registriert werden). Dafür fehlt zwar noch die Dokumentation, aber wer sich die Sourcen der vorhandenen Operatoren anschaut, kann sehen, wie es funktionert.

Ich plane als nächstes, Dokumentation und JUnit-Abdeckung auf Vordermann zu bringen, sowie die Projektstruktur zu verbessern. Neue Features sind erst mal nicht geplant. Eine interessante Erweiterung wäre eine zweite Utility-Klasse, die statt RPN die "normale" Infix-Notation erlaubt, aber das wäre schon ein wenig Arbeit...

 

[Landei]

Neues Release: http://birpn.googlecode.com/files/BIRPN-0.3.jar

Ein Doppelklick auf das Jar öffnet jetzt einen kleinen UPN-Rechner zum Rumspielen...