BIRPN – BigInteger polnisch umgedreht


Heute will ich mein Mini-Projekt BIRPN vorstellen.

Java’s umständliche BigInteger-Arithmetik kann einem wirklich den Tag vermiesen, aber für eine „ordentliche“ DSL reicht Java’s Syntax einfach nicht aus. Also habe ich mir überlegt, anstatt einer Infix-DSL nachzutrauern, lieber einen kleinen Postfix-Auswerter zu schreiben (hier ein Wikipedia-Artikel über Postfix oder „Umgekehrt Polnische Notation“). Die Ergebnisse von gerade einmal einem Tag Arbeit lassen sich wirklich sehen. Hier mein Standardbeispiel:

    //from http://en.literateprograms.org/Lucas-Lehmer_test_for_Mersenne_numbers_%28Java%29
    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);
    }

In den „Operator-Stil“ übersetzt:

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

Und einen Schritt weiter zum „Parser-Stil“:

    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"));
    }

Neben den üblichen Helferlein (statischer Import, Autoboxing) hat mir vor allem der Trick geholfen, die Operator-Konstanten (wie PLUS oder POW) auch als BigInteger zu speichern. Dabei verlasse ich mich auf die Objekt-Identität (jeder Operator entspricht einer anderen Instanz von new BigInteger(„0“)), und habe dafür das erste Mal in meinem Leben eine IdentityHashMap verwendet. Dieser Trick ist natürlich grenzwertig, aber die Alternative, die BigIntegers in Wrapper zu verpacken, wäre kaum praktischer als direkt mit BigIntegers zu arbeiten.

So, dann lasse ich hier mal gut sein, bevor BIRPN noch zu einer Programmiersprache auswächst und eigenes Bewusstsein entwickelt…

Advertisements

Kommentar verfassen

Trage deine Daten unten ein oder klicke ein Icon um dich einzuloggen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden / Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden / Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden / Ändern )

Google+ Foto

Du kommentierst mit Deinem Google+-Konto. Abmelden / Ändern )

Verbinde mit %s