Virtual machines

We all know that Java uses a „virtual machine“ that is it simulates a non-existing hardware which is the same independent of the real hardware, thus helping to achieve the well known platform independence of Java. Btw. this is not about virtualization like VMWare, VirtualBox, Qemu, Xen, Docker and similar tools, but about byte code interpreters like the Java-VM.

We tend to believe that this is the major innovation of Java, but actually the concept of virtual machines is very old. Lisp, UCSD-Pascal, Eumel/Elan, Perl and many other systems have used this concept long before Java. The Java guys have been good in selling this and it was possible to get this really to the mainstream when Java came out. The Java guys deserve the credit for bringing this in the right time and bringing it to the main stream.

Earlier implementations where kind of cool, but the virtual machine technology and the hardware were to slow, so that they were not really attractive, at least not for high performance applications, which are now actually a domain of Java and other JVM languages. Some suggest that Java or other efficient JVM languages like Scala would run even faster than C++. While it may be true to show this in examples, and the hotspot optimization gives some theoretical evidence how optimization that takes place during run time can be better than static optimization at compile time, I do not generally trust this. I doubt that well written C-code for an application that is adequate for both C and Java will be outperformed by Java. But we have to take two more aspects into account, which tend to be considered kind of unlimited for many such comparisons to make them possible at all.

The JVM has two weaknesses in terms of performance. The start-up time is relatively long. This is addressed in those comparisons, because the claim to be fast is only maintained for long running server applications, where start-up time is not relevant. The hotspot optimization requires anyway a long running application in order to show its advantages. Another aspect that is very relevant is that Java uses a lot of memory. I do not really know why, because more high level languages like Perl or Ruby get along with less memory, but experience shows that this is true. So if we have a budget X to buy hardware and then put software written in C on it, we can just afford to buy more CPUs because we save on the memory or we can make use of the memory that the JVM would otherwise just use up to make our application faster. When we view the achievable performance with a given hardware budget, I am quite sure that well written C outperforms well written Java.

The other aspect is in favor of Java. We have implicitly assumed until now that the budget for development is unlimited. In practice that is not the case. While we fight with interesting, but time consuming low level issues in C, we already get work done in Java. A useful application in Java is usually finished faster than in C, again if it is in a domain that can reasonably be addressed with either of the two languages and if we do not get lost in the framework world. So if the Java application is good enough in terms of performance, which it often is, even for very performance critical applications, then we might be better off using Java instead of C to get the job done faster and to have time for optimization, documentation, testing, unit testing.. Yes, I am in a perfect world now, but we should always aim for that. You could argue that the same argument is valid in terms of using a more high-level language than Java, like Ruby, Perl, Perl 6, Clojure, Scala, F#,… I’ll leave this argument to other articles in the future and in the past.

What Java has really been good at is bringing the VM technology to a level that allows real world high performance server application and bringing it to the main stream.
That is already a great achievement. Interestingly there have never been serious and successful efforts to actually build the JavaVM as hardware CPU and put that as a co-processor into common PCs or servers. It would have been an issue with the upgrade to Java8, because that was an incompatible change, but other than that the JavaVM remained pretty stable. As we see the hotspot optimization is now so good that the urge for such a hardware is not so strong.

Now the JVM has been built around the Java language, which was quite legitimate, because that was the only goal in the beginning. It is even started using the command line tool java (or sometimes javaw on MS-Windows 32/64 systems). The success of Java made the JVM wide spread and efficient, so it became attractive to run other languages on it. There are more than 100 languages on the JVM. Most of them are not very relevant. A couple of them are part of the Java world, because they are or used to be specific micro languages closely related to java to achieve certain goals in the JEE-world, like the now almost obsolete JSP, JavaFX, .

Relevant languages are Scala, Clojure, JRuby, Groovy and JavaScript. I am not sure about Jython, Ceylon and Kotlin. There are interesting ideas coming up here and there like running Haskell under the name Frege on the JVM. And I would love to see a language that just adds operator overloading and provides some preprocessor to achieve this by translating for example „(+)“ in infix syntax to „.add(..)“ mainstream, to allow seriously using numeric types in Java.

Now Perl 6 started its development around 2000. They were at that time assuming that the JVM is not a good target for a dynamic language to achieve good performance. So they started developing Parrot as their own VM. The goal was to share Parrot between many dynamic languages like Ruby, Python, Scheme and Perl 6, which would have allowed inter-language inter-operation to be more easily achievable and using libraries from one of these languages in one of the others. I would not have been trivial, because I am quite sure that we would have come across issues that each language has another set of basic types, so strings and numbers would have to be converted to the strings and numbers of the library language when calling, but it would have been interesting.

In the end parrot was a very interesting project, theoretically very sound and it looked like for example the Ruby guys went for it even faster than the the Perl guys, resulting in an implementation called cardinal. But the relevant Perl 6 implementation, rakudo, eventually went for their own VM, Moar. Ruby also did itself a new better VM- Many other language, including Ruby and JavaScript also went for the JVM, at least as one implementation variant. Eventually the JVM proved to be successful even in this area. The argument to start parrot in the first place was that the JVM is not good for dynamic languages. I believe that this was true around 2000. But the JVM has vastly improved since then, even resulting in Java being a serious alternative to C for many high performance server applications. And it has been improved for dynamic languages, mostly by adding the „invoke_dynamic“-feature, that also proved to be useful for implementing Java 8 lambdas. The experience in transforming and executing dynamic languages to the JVM has grown. So in the end parrot has become kind of obsolete and seems to be maintained, but hardly used for any mainstream projects. In the end we have Perl 6 now and Parrot was an important stepping stone on this path, even if it becomes obsolete. The question of interoperability between different scripting languages remains interesting…

Share Button

Restklassenrundung

English

Das Konzept der Rundung kennt man grundsätzlich. Aber versuchen wir es etwas systematischer zu erfassen.

Man hat eine Menge M von Zahlen und eine Teilmenge N \subseteq M davon, deren Elemente in der verwendeten Programmierumgebung dargestellt werden. Dazu hat man noch eine Metrik d : M \times M \rightarrow \Bbb R_+, (x, y) \mapsto r=d(x,y)>=0. Man verlangt normalerweise noch gewisse Eigenschaften von d:

  • Positive Definitheit: d(x,y) = 0 \iff x = y
  • Symmetrie: d(x,y)=d(y,x)
  • Dreiecksungleichung: d(x,z) \le d(x,y) + d(y,z)

Typischerweise sind die Zahlen, mit denen wir uns meistens beschäftigen, in der Welt der reellen und komplexen Zahlen gedacht, man kann also fast immer sicher sein, dass M \subseteq \Bbb C ist, meistens sogar M \subseteq \Bbb R oder wenn wir ehrlich sind sogar M \subseteq \Bbb Q. Dann ist normalerweise d(x,y) = |x-y|. Wer die komplexen Zahlen noch nicht kennt, denke einfach an reelle und rationale Zahlen, das ist das, womit wir normalerweise bewusst zu tun haben. Dabei sind natürlich Konzepte wie Rundung speziell in p-adischen Zahlen hochinteressant, aber dafür muss ich die erstmal erklären und das lasse ich heute…

Was stellen wir uns nun unter einer Rundung vor?
Vielleicht eine Abbildung
r: M \rightarrow N, x \mapsto r(x),
die mit gewissen Nebenbedingungen für jedes x jeweils so gewählt wird, dass d(x, r(x)) minimal ist.
Die Nebenbedingungen brauchen wir einerseits, um es eindeutig zu machen, wenn mehrere Werte y\in N existieren, für die d(x,y) minimal ist. Der klassische Fall ist das Runden auf ganzzahlige Werte und die Frage mit der 0.5. Wenn N eine Teilmenge der reellen Zahlen ist, was ja „meistens“ der Fall ist, hat man eine Anordung. Da kommen dann die folgenden Constraints zum Tragen (Beispiel immer mit Rundung auf ganze Zahlen):

ROUND_UP
|r(x)|\ge |x| Z.B. r(0.4)=1 und r(0.5)=1 und r(-0.5)=-1
ROUND_DOWN
|r(x)|\le |x| Z.B. r(0.6)=0 und r(0.5)=0 und r(-0.5)=0
ROUND_CEILING
r(x) \ge x Z.B. r(0.4)=1 und r(0.5)=1 und r(-0.5)=0
ROUND_FLOOR
r(x) \le x Z.B. r(0.6)=0 und r(0.5)=0 und r(-0.5)=-1
ROUND_HALF_UP
Minimiere d(r(x),x), aber wenn es mehrere optimale Werte für r(x) gibt, wähle den am weitesten von 0 entfernten, z.B. r(0.4)=0 und r(0.6)=1 und r(0.5)=1 und r(-0.5)=-1
ROUND_HALF_DOWN
Minimiere d(r(x),x), aber wenn es mehrere optimale Werte für r(x) gibt, wähle den am nächsten an 0, z.B. r(0.4)=0 und r(0.6)=1 und r(0.5)=0 und r(-0.5)=0
ROUND_HALF_CEILING
Minimiere d(r(x),x), aber wenn es mehrere optimale Werte für r(x) gibt, wähle den größten, z.B. r(0.4)=0 und r(0.6)=1 und r(0.5)=1 und r(-0.5)=0
ROUND_HALF_FLOOR
Minimiere d(r(x),x), aber wenn es mehrere optimale Werte für r(x) gibt, wähle den kleinesten, z.B. r(0.4)=0 und r(0.6)=1 und r(0.5)=0 und r(-0.5)=-1
ROUND_HALF_EVEN
Minimiere d(r(x),x), aber wenn es mehrere optimale Werte für r(x) gibt, wähle den mit gerader Endziffer. Achtung, dieser Constraint ist im „klassischen“ Fall anwendbar, aber nicht allgemeingültig. Z.B.: r(0.4)=0 und r(0.6)=1 und r(0.5)=0 und r(-0.5)=0 und (1.5)=2
ROUND_UNNECESSARY
Dieser Constraint ist im mathematischen Sinne nicht geeignet (oder nur mit hässlichen Verrenkungen), aber programmatisch können wir das: Wir nehmen r(x)=x und schmeißen eine Exception wenn nicht x\in N schon gilt.

Typischerweise denken wir im Dezimalsystem und dann wählen wir eine Zehnerpotenz 10^n mit n \in \Bbb N, also n \ge 0. Nun ist einfach
N = \{ x \in M : 10^n x \in \Bbb Z\},
also umgangsprachlich sind in N alle Zahlen aus M mit maximal n Stellen nach dem Komma. Diese Rundung funktioniert ganz gut mit so etwas wie LongDecimal in Ruby oder BigDecimal in Scala oder Java, wobei BigDecimal weniger Rundungsmodi anbietet als LongDecimal für Ruby.

Nun kommen wir zur Restklassenrundung. Wir gehen wieder von dieser Zehnerpotenz 10^n aus. Dann brauchen wir noch eine natürlich Zahl m \ge 2 und eine Menge von Resten R \subseteq \{0,...,m-1\}. Nun ist
N = \{ x \in M : 10^n x \in {\Bbb Z} \wedge \bigvee_{r \in R} 10^n x \equiv r \mod{m}\}.
Das bedeutet, wenn wir mit Nullen auf die angegebene Anzahl von Nachkommastellen auffüllen, das „Komma“ (normalerweise als „.“ geschrieben) weglassen und dann diese Zahl mit Rest durch m teilen, der dabei herauskommende Rest in R liegt.
In diesem Fall wird es mit dem ROUND_HALF_EVEN eventuell schwierig, da es undefiniert oder mehrdeutig werden kann. Aber wir müssen auch den Fall abdecken, dass die 0 nicht in R ist und Regeln angeben, wohin die 0 gerundet werden soll. Die Kandidaten sind hier mit selbsterklärenden Namen versehen:

  • ZERO_ROUND_TO_PLUS
  • ZERO_ROUND_TO_MINUS
  • ZERO_ROUND_TO_CLOSEST_PREFER_PLUS
  • ZERO_ROUND_TO_CLOSEST_PREFER_MINUS
  • ZERO_ROUND_UNNECESSARY

Ein wichtiger Anwendungsfall ist hier m=10 und R=\{0, 5\}. So kann man in der Schweiz Geldbeträge auf Vielfache von 5 Rappen (0.05 CHF) runden. Dies wurde in Rundung bei Geldbeträgen bereits genauer beschrieben.

Share Button

Ist Ruby funktional

Wenn die Liste der funktionalen Sprachen erstellt wird, dann tauchen Haskell, Scala, Erlang, F#, Clojure und einige andere Lisp-Varianten auf.

Wenn man sich anschaut, welche Merkmale funktionale Sprachen auszeichnen, dann stellt sich die Frage, ob das nicht alles mit Ruby auch machbar ist.

Schauen wir einmal was man so typischerweise findet, meist auf Englisch:

  • Functions as „first class citizen“
  • Closures
  • Pure Functions
  • Higher Order functions
  • Everything returns a value
  • Immutability
  • No hidden state
  • Prefer recursion over iteration (immutable loop variable…)

Funktionen existieren in Ruby also losgelöste Objekte, in verschiedenen Formen, z.B. als proc, als lambda, als anonymer Block und durch Referenzierung einer Methode über ihren Namen (Reflection).

Closures werden von Ruby problemlos unterstützt, bei all diesen Formen der Funktionen werden Variablen aus dem definierenden Kontext eingebunden, wo sie referenziert werden. Methoden kann man übrigens als Spezialfall von Closures ansehen, weil sie als Kontext das Objekt einbinden, zu dem sie gehören.

Unter „pure function“ versteht man Funktionen, die den Funktionen aus der Mathematik entsprechen. Sie haben absolut keinen Seiteneffekt, sind reproduzierbar, können in beliebiger Zahl parallel ausgeführt werden und geben bei mehrfachen Aufrufen immer dasselbe Resultat. Sie eignen sich für Memoize, was nun eigentlich wieder ein Seiteneffekt ist, aber sozusagen ein transparenter. Man denke an sort() und sort!() in Ruby. Dies verlangt Disziplin vom Entwickler und gute Dokumentation.

„Higher Order Functions“ sind Funktionen höherer Ordnung, die also selbst Funktionen als Parameter oder Rückgabewert haben. Das ist in der funktionalen Programmierung Routine und nicht so ein spezieller Spezialfall, den man mal alle paar Jahre benutzt, wie Funktionspointer in C. Typische Beispiele sind Methoden wie inject(), map(), group_by()… each() sollte man nur verwenden, wenn man die Seiteneffekte wirklich braucht.

Alle Ausdrücke haben einen Wert. Das ist recht gut in Ruby umgesetzt, z.B. x = if (...) ... else ... end kann man verwenden…

Immutibility (Unveränderbarkeit) ist die Achillesferse. Es wird nicht wirklich gut unterstützt. Man soll Variablen nicht neu zuweisen und auch nicht irgendwas mutieren. Warum nimmt man nicht freeze()? Wir brauchen ein deepfreeze(), aber was bedeutet das? Wie sieht es mit collections aus? Es gibt immer Möglichkeiten, diese unverändert zu lassen und mit jedem Schritt eine neue Collection zu produzieren. Dasselbe gilt für Zeichenketten.

„No hidden State“, also kein versteckter Zustand. Man kann Kontextobjekte haben und herumreichen. Zustand ist unerwünscht und sollte kontrolliert an wenigen Orten gehandhabt werden.

„Recursion instead of Iteration“ steht für Rekursion statt Iteration. Funktionale Sprachen unterstützen Optimierung bei Tailrekursion (Endrekursion). Einige andere Sprachen, z.B. C mit gcc, Scala und viele Lisp-Dialekte, aber nicht Java, unterstützen diese Optimierung und erlauben es, zumindest Endrekursion ohne zu große Furcht einzusetzen. Bei Ruby hängt es von der Version und den Einstellungen ab, ist also mit Vorsicht zu genießen. Der Ruby-Ansatz ist es eher, die Iteratorn zu verwenden.

Fazit: Man kann mit ein paar Einschränkungen in Ruby funktional programmieren, aber es erfordert etwas mehr Disziplin, weil einige Dinge vom Entwickler beachtet werden müssen und nicht von der Sprache unterstützt werden.

Share Button

Zufällige Zeichenkette erzeugen

Oft braucht man so eine zufällige Zeichenkette, die nur aus bestimmten Zeichen bestehen darf.

Hier ist eine einfache Ruby-implementierung dafür:


#!/usr/bin/ruby

arr = ('a'...'z').to_a + ('A'...'Z').to_a + ('0'...'9').to_a + ['.', '/']
val = (0..16).inject("") do |a, x| i = (arr.size() * rand()).to_i;a + arr[i] end
puts val

Es wird eine 16-Zeichen lange Zeichenkette generiert, die aus den Zeichen [a-zA-Z0-9./] besteht.

Share Button

Getter und Setter

In der objektorientierten Programmierung gilt es als fortschrittlich, getter und setter zu verwenden, statt auf Attribute direkt zuzugreifen, weil das einem die Flexibilität gibt, später auf berechnete Attribute umzuschwenken. Etwas hässlich ist das, weil die getter und setter, etwas willkürlich den Attributnamen mit so einem vorangestellten „get“ oder „is“ oder „set“ und eventueller Umwandlung der Groß- und Kleinschreibung einzelner Zeichen versehen. Eine subtile Besonderheit ist, dass es verwirrend wird, wenn Attributnamen mit „get“, „is“ oder „set“ beginnen. Gerade Boolean-Attribute ist man versucht mit „hasSomething“, „isSomething“, „doesSomething“, „canSomething“, „mustSomething“,… o.ä. zu benennen, was dann zu dem Getter „getIsSomething()“ oder „isIsSomething()“ führt. Oder man lässt in dem Fall das Präfix weg, aber nur beim Getter…

Schöner ist es, wenn man Getter und Setter natürlich bennen kann, wie das z.B. in C#, Ruby und Scala der Fall ist: Man schreibt den Getter so, als würde man das Attribut public machen und darauf zugreifen, aber hat durch die entsprechenden Sprachkonstrukte die Möglichkeit, die Getter und Setter durch andere Implementierungen zu ersetzen, wenn der Bedarf besteht. Es gibt sicher wichtigeres, aber das ist zumindest schöner, lesbarer und deshalb weniger fehleranfällig. Und sprachlich auch sauberer als diese „halb-magic“-Bedeutung von „get…“, „set…“ und „is…“.

Im Grunde genommen sind aber auch Zugriffe auf Listen und Maps oft eine Art Getter und Setter:
y=a.get(pos) könnte man auch als y=a[pos] schreiben wollen, entsprechend a.put(pos, x) auch als a[pos]=x. Dasselbe gilt für Maps mit u=m.get(k), was schöner und intuitiver als etwas in der Art von u=m[k] wäre. Oder statt m.put(k, v) so etwas wie m[k]=v. Aus genügend abstrakter Sicht ist das nicht so wichtig, aber wenn die Lesbarkeit sich verbessert, macht man weniger Fehler und so hat man pragmatisch gesehen einen kleinen Qualitäts und Effizienzgewinn mit der Zuweisungsschreibweise.

Nun sind aber Setter in Wirklichkeit oft problematisch. Es ist immer gut, Objekte immutable zu haben, weil man sie dann problemloser zwischen Threads herumreichen kann, ohne dass es zu Fehler bei gleichzeitigen Zugriffen kommen kann. Nun stellt sich aber die Frage, wie man dann das Objekt konstruieren soll. Ein Konstruktor mit positionalen Parametern ist zwar möglich, aber oft nicht sehr lesbar, wenn die Parameterliste nicht völlig überschaubar und klar ist. So etwas wie benannte Parameter könnte sehr viel helfen. Ein anderes Muster ist es, ein temporäres Objekt mit Settern aufzubauen und dann daraus das eigenteliche unveränderliche (immutable) Objekt zu generieren. Man kann dafür spezielle Setter nehmen, die jeweils das veränderte Objekt zurückgeben und das etwa so etwas schreiben wie
SomethingImmutable s = new SomethingTemp().setX(x).setY(y).setZ(z).toSomething(),
was nicht superschön ist, aber wenn man auf Java Wert legt, doch eine Möglichkeit.

Hier zeigt sich auch, warum es so schön ist, wenn man Listen und Maps und vielleicht andere Collections einfach mit allen Elementen konstruieren und dann gleich immutable machen kann. In Java geht das für Listen immerhin schon mit
Collections.immutableList(Arrays.asList(a, b, c, d, e, f, g, h))
machen. Wobei diese Konstruktion relativ neu ist und wegen der Konstruktionsphase Collections nicht defaultmäßig immutable sein können. Immerhin könnte man ein
Arrays.asImmutableList(T..t)
definieren. Oder eine Methode auf List
.immutable().
Schöner (klarer, lesbarer, weniger fehleranfällig) wäre es aber, wenn man das als
[a, b, c, d, e, f, g, h]
schreiben könnte. Für die Ausgabe von Listen mittels toString() wird so etwas ja schon verstanden. Für das Konstruieren von Maps gibt es in anderen Programmiersprachen auch Schreibweisen, die etwa so aussehen wie
m = { k1 => v1, k2 => v2, k3 => v3, k4 => v4}.
Will man sich normalerweise dafür interessieren, welche Map-Implementierung jetzt genommen wird? So etwas ließe sich als
m = new TreeMap{k1 => v1, k2 => v2, k3 => v3, k4 => v4}
schreiben. Solche Dinge waren für Java 8 vorgesehen, sind aber wohl in letzter Minute rausgeflogen oder auf Java 9 verschoben worden.

Share Button

Division mit Rest

Die Division mit Rest ist in vielen Programmiersprachen enthalten und man könnte meinen, dass klar ist, was damit gemeint ist. Meistens wird diese Restbildung mit „%“ geschrieben, was alle von C übernommen haben und was auch gut ist. Außer man will etwas mit Prozentrechnung programmieren und ist vom Taschenrechner für % etwas anderes gewohnt.

Aber man sollte etwas vorsichtig sein.

Zunächst gilt bei vielen Programmiersprachen die Regel, dass „immer“

    \[ a = ( a/b) * b + a \% b \]

gilt. Das ist schön, aber manche Programmiersprachen finden es logischer, wenn a/b eine Fließkommazahl oder eine rationale Zahl ergibt. Eine „ganzzahlige gerundete Division“ wäre natürlich zusätzlich cool, aber wenn man es so ausdrückt, fällt schon auf, wo die Schwierigkeit liegt. Setzen wir mal einen positiven Divisor voraus…. Wie wird hier gerundet? Je nach Rundungsverfahren ist für r = a \% b immer r \ge 0 (Ruby) oder nur r \ge 0 für a \ge 0 und für negative a ist es r \le 0 (Scala). Denkbar wäre aber auch, dass -\frac{a}{2} \le r < \frac{a}{2} gilt.
Leider ist es ein bisschen schwierig, eine elegante Schreibweise zu finden, um die Rundungsmethode für das % zu definieren.

In der Praxis benötigt man diese Reste oft für weitere Verarbeitungen. Was macht man nun mit den negativen Resten?
Oft ist es sinnvoll, a zu negativen Resten hinzu zu addieren. Dann hat man immer noch einen legitimen Rest, aber mit dem richtigen Vorzeichen, etwa das, was bei Ruby sowieso herauskäme.

Share Button

Flashsort in Ruby

Es gibt auf github eine einfache Implementierung von Flashsort in Ruby, nachdem hier auf github schon eine Implementierung in C zu finden ist. Die C-Implementierung ist typischerweise schneller als die libc-Funktion qsort, aber letztlich hängt das von den Daten ab und davon, wie gut die metric-Funktion ist, die man zusätzlich zur Vergleichsfunktion bei Flashsort liefern muss. Man kann sich diese metric-Funktion als eine Art monotone Hashfunktion vorstellen, also gilt

    \[\bigwedge_{a,b: a\le b} m(a) \le m(b) \]

Diese zusätzlich benötigte Funktion oder Methode ist nicht wirklich vorhanden, außer bei numerischen Werten, was den Einsatz von Flashsort etwas erschwert. Entscheidend für eine gute Performance ist eine gute metric-Funktion, allerdings sind bei typischen Text-Dateien schon ziemlich triviale Implementierungen ganz brauchbar.

In diesem Blogbeitrag sind weitere Sortieralgorithmen für Ruby gezeigt.

Share Button

Rundung bei Geldbeträgen

English

Ein Teil der numerischen Berechungen bezieht sich auf Geldbeträge. Es ist immer ganz schön, wenn diese Berechnungen stimmen oder wenn man zumindest durch solche Ungenauigkeiten kein Geld verliert. Natürlich gibt es Berechnungen, die von ungefähren Zahlwerten ausgehen dürfen, wenn es etwa um Berechnungen von prozentualen Renditen geht. Da können dann auch diese Fließkomma-Zahlen (double, Float oder wie sie auch heißen) zum Einsatz kommen, es muss aber natürlich auf numerische Probleme Rücksicht genommen werden, sonst können sich Rundungsfehler massiv hochschaukeln.

Oft ist es aber notwendig, mit den genauen Beträgen zu rechen. Nun kann man so etaws wie 3.23 sehr schön als Fließkommazahl schreiben, aber leider arbeiten diese Fließkommazahlen intern im Dualsystem und drücken also die Zehntel und Hundertstel in Brüchen mit Zweierpotenzen im Nenner aus. Man kann einmal den Versuch machen x=323_{10}=101000011_{2} durch y=100_{10}=1100100_2 zu teilen, im Dualsystem. Da bekommt man dann z=x/y=11.0011101011100001010001111010111000010100011110101\ldots_{2}, genauer z=11.00\overline{11101011100001010001} oder als Bruch daraus z=11_2+\frac{11101011100001010001_2}{100_2*(100000000000000000000_2-1_2)} oder im Zehnersystem z=3_{10}+\frac{964689_{10}}{4_{10}\cdot1048575_{10}}.

Man sieht also, dass diese unscheinbare Zahl mit nur zwei Stellen nach dem Komma im Dualsystem unendlich viele Stellen nach dem Komma bräuchte. In den üblichen Double oder Float-Typen sind aber nur 64 Bit insgesamt vorgesehen und es werden einige Stellen weggeworfen. Zum Glück funktioniert es meistens und die gespeicherte Zahl wird immer noch als 3.23 angezeigt, aber jeder, der ein bißchen mit diesen Fließkommazahlen hantiert hat, weiß, dass irgendann einmal etwas in der Art von 3.299999999999 oder 3.2300000001 statt 3.23 herauskommt und dass bei typischen Additions- und Subtraktionsoperationen. Man kann sogar auf 3.22 oder 3.24 kommen, wenn man lange genug herumrechnet. Für viele Applikationen ist das unakzeptabel.

Eine einfache und oft sinnvolle Lösung ist es, mit Ganzzahlen zu rechnen und die Beträge in Cent, Rappen, Pfennigen u.s.w. auszudrücken. Dann ist das Rundungsproblem für reine Additionen und Subtraktionen vollständig gelöst oder zumindest für alle anderen Operationen etwas einfacher handhabbar. Man muss nur in der Software darauf achten, dass man die „Beträge in Cent“ und die „Beträge in Euro“ niemals, wirklich niemals durcheinanderbringt. In Scala würde man verschiedene Typen verwenden, so dass zur compile-Zeit diese Durchmischung unterbunden wird. Wichtig ist natürlich in jedem Fall, dass man nicht so etwas wie int von Java verwendet, wo der Überlauf zu unüberschaubaren Katastrophen führen kann. Und Abschätzungen über die oberen Grenzen des monetären Reichtums von Firmen und Einzelpersonen gezählt in einer potentiell inflationsgefährdeten Währung sind fast immer falsch. Hier zeigt sich, dass Java für Finanzapplikationen schlecht geeignet ist, weil man dann statt a = b + c * d für BigInteger so etwas wie a = b.{\rm add}(c.{\rm multiply}(d)) schreiben muss, was dazu führt, dass man die Formel nicht mehr „sieht“ und deshalb sehr viel mehr Fehler produziert. Eventuell kann man das Problem mit einem Präprozessor lösen oder es mit einer Library, die wenigstens so etwas wie UPN-Notation für die Berechnung ermöglicht, etwas entschärfen. Dann schreibt man etwa so etwas

Calculation calc = new Calculation();
calc.push(b)
calc.push(c)
calc.push(d)
calc.add()
calc.multiply()
a = calc.top()

Wer noch alte HP-Taschenrechner oder Forth kennt, wird das vielleicht mögen, aber für die meisten von uns ist auch das nicht wirklich die Lösung des Problems.

Üblich und sinnvoll ist aber in den meisten Fällen, so ein dezimaler Festkomma-Typ für diesen Anwendungsfall. In Java ist das BigDecimal, in Ruby LongDecimal. Ein Beispiel in Ruby

> sudo gem install long-decimal
Successfully installed long-decimal-1.00.01
1 gem installed
....
> irb
irb(main):001:0> require "long-decimal"
=> true
irb(main):002:0> x = LongDecimal("3.23")
=> LongDecimal(323, 2)
irb(main):003:0> y = LongDecimal("7.68")
=> LongDecimal(768, 2)
irb(main):004:0> z = LongDecimal("3.9291")
=> LongDecimal(39291, 4)
irb(main):005:0> x+y
=> LongDecimal(1091, 2)
irb(main):006:0> (x+y).to_s
=> "10.91"
irb(main):007:0> x+y*z
=> LongDecimal(33405488, 6)
irb(main):008:0> (x+y*z).to_s
=> "33.405488"
irb(main):009:0> 

Interessant ist, dass bei Addition und Subtraktion die Anzahl der benötigten Nachkommastellen gleich bleibt bzw. sich die größere Anzahl von Nachkommastellen durchsetzt. Bei Multiplikation und Division und sowieso bei komplexeren Operationen können aber viele Nachkommastellen entstehen. Da ist es entscheidend, richtig zu runden. LongDecimal kennt die folgenden Rundungsmethoden:

ROUND_UP
Rundet von 0 weg, für positive Zahlen gleich wie ROUND_CEILING
ROUND_DOWN

Rundet zu 0 hin, für positive Zahlen gleich wie ROUND_FLOOR

ROUND_CEILING
Rundet auf, also hin zu größeren, positiveren, weniger negativen Zahlen
ROUND_FLOOR
Rundet ab, also hin zu kleineren, negativeren, weniger positiven Zahlen
ROUND_HALF_UP
Rundet ab der Mitte weg von 0, unterhalb der Mitte zu 0 hin
ROUND_HALF_DOWN
Rundet bis einschließlich der Mitte zur 0 hin, oberhalb der Mitte von der 0 weg.
ROUND_HALF_CEILING
Rundet bis einschließlich der Mitte auf (Richtung unendlich) hin, sonst ab.
ROUND_HALF_FLOOR
Rundet ab der Mitte ab, sonst auf.
ROUND_HALF_EVEN
Rundet die Mitte so, dass dabei die letzte Stelle gerade wird.
ROUND_HALF_ODD
Rundet die Mitte so, dass dabei die letzte Stelle ungerade wird.
ROUND_UNNECESSARY
Rundet gar nicht und wirft eine Exception, wenn die weggerundeten Stellen nicht alles Nullen sind.

Welche man davon anwendet sollte man unbedingt mit den entsprechenden Spezialisten von der „Fachseite“ besprechen oder für den jeweiligen Anwendungsfall herausfinden. Als Fortsetzung vom obigen Beispiel sähe das etwa so aus:

irb(main):035:0> t=(x+y*z)
=> LongDecimal(33405488, 6)
irb(main):036:0> 
irb(main):037:0* t.round_to_scale(2, LongDecimal::ROUND_UP).to_s
=> "33.41"
irb(main):038:0> t.round_to_scale(2, LongDecimal::ROUND_DOWN).to_s
=> "33.40"
irb(main):039:0> t.round_to_scale(2, LongDecimal::ROUND_CEILING).to_s
=> "33.41"
irb(main):040:0> t.round_to_scale(2, LongDecimal::ROUND_FLOOR).to_s
=> "33.40"
irb(main):041:0> t.round_to_scale(2, LongDecimal::ROUND_HALF_UP).to_s
=> "33.41"
irb(main):042:0> t.round_to_scale(2, LongDecimal::ROUND_HALF_DOWN).to_s
=> "33.41"
irb(main):043:0> t.round_to_scale(2, LongDecimal::ROUND_HALF_CEILING).to_s
=> "33.41"
irb(main):044:0> t.round_to_scale(2, LongDecimal::ROUND_HALF_FLOOR).to_s
=> "33.41"
irb(main):045:0> t.round_to_scale(2, LongDecimal::ROUND_HALF_EVEN).to_s
=> "33.41"
irb(main):046:0> t.round_to_scale(2, LongDecimal::ROUND_UNNECESSARY).to_s
ArgumentError: mode ROUND_UNNECESSARY not applicable, remainder 5488 is not zero
        from /usr/local/lib/ruby/gems/1.9.1/gems/long-decimal-1.00.01/lib/long-decimal.rb:507:in `round_to_scale_helper'
        from /usr/local/lib/ruby/gems/1.9.1/gems/long-decimal-1.00.01/lib/long-decimal.rb:858:in `round_to_scale'
        from (irb):46
        from /usr/local/bin/irb:12:in `
' irb(main):047:0>

Eine Besonderheit ist, dass in manchen Ländern die kleinste Münze nicht mehr gebräuchlich ist. In der Schweiz ist zum Beispiel der kleinstmögliche Betrag 5 Rappen (0.05 CHF), nicht 1 Rappen. Nun kann man zwar die Bank dazu bringen, Überweisungen zu machen, deren Endziffer nicht 0 oder 5 ist, aber es ist doch verbreitet, Rechungen auf Vielfache von 5 Rappen zu runden. Man kann das Lösen, indem man den Betrag mit 20 multipliziert, dann auf die gewünschte Art rundet und zum Schluss wieder durch 20 dividiert und das Ergebnis auf 2 Nachkommastellen rundet. In Ruby geht das aber einfacher, weil LongDecimal eine „Restklassenrundung“ kennt. Man kann also sagen, man möchte eine Zahl x mit n dezimalen Nachkommastellen so runden, dass die mit 10^n\cdot x einer der Restklassen \overline{0} \mod 10 oder \overline{5} \mod 10 entspricht. In dem Fall ist es einfach die Endziffer. Man kann eine beliebige Menge von Endziffern vorgeben und sogar die 0 verbieten, wobei dann noch festgelegt werden muss, wie die 0 gerundet werden soll, was die üblichen Rundungsmodi nicht vollständig erklären können. Bei Interesse kann ich darauf noch näher eingehen, es ist aber für diesen praktischen Fall nicht relevant, weil die Endziffer 0 natürlich erlaubt ist. Für diesen praktischen Anwendungsfall funktioniert es also so:


irb(main):003:0> t.round_to_allowed_remainders(2, [0, 5], 10, LongDecimal::ROUND_UP).to_s
=> "33.45"
irb(main):005:0> t.round_to_allowed_remainders(2, [0, 5], 10, LongDecimal::ROUND_DOWN).to_s
=> "33.40"
irb(main):006:0> t.round_to_allowed_remainders(2, [0, 5], 10, LongDecimal::ROUND_CEILING).to_s
=> "33.45"
irb(main):007:0> t.round_to_allowed_remainders(2, [0, 5], 10, LongDecimal::ROUND_FLOOR).to_s
=> "33.40"
irb(main):008:0> t.round_to_allowed_remainders(2, [0, 5], 10, LongDecimal::ROUND_HALF_UP).to_s
=> "33.40"
irb(main):009:0> t.round_to_allowed_remainders(2, [0, 5], 10, LongDecimal::ROUND_HALF_DOWN).to_s
=> "33.40"
irb(main):010:0> t.round_to_allowed_remainders(2, [0, 5], 10, LongDecimal::ROUND_HALF_CEILING).to_s
=> "33.40"
irb(main):011:0> t.round_to_allowed_remainders(2, [0, 5], 10, LongDecimal::ROUND_HALF_FLOOR).to_s
=> "33.40"

Man kann nun also in der Finanzapplikation für jede Währung Rundungsmethoden definieren.

LongDecimal kann noch etwas mehr. So ist es möglich, Logarithmen, e-Funktion, Quadratwurzel und Kubikwurzel auf eine gewünschte Anzahl von Nachkommastellen genau zu berechnen und die entsprechenden Algorithmen sind daraufhin optimiert, das Ergebnis möglichst schnell, aber natürlich mit der erforderlichen Genauigkeit zu berechnen.

Share Button

Scala, Ruby, Perl,… – wann nimmt man was?

Wer einen goldenen Hammer hat, für den sieht jede Schraube wie in Nagel aus. Aber wir haben einen riesigen Werkzeugkasten und wie man sieht, überschneiden sich tatsächlich manche Werkzeuge in ihren Einsatzbereichen, aber das Universalwerkzeug ist nicht wirklich in Sicht oder doch nicht wirklich in allen Bereichen mit den Spezialwerkzeugen konkurrenzfähig.

Oft hat man ja Altlasten, also vorhandene Applikationen, die man erweitern oder ergänzen soll oder es sollen sogar neue, „in die Landschaft passende“ Applikationen hinzugefügt werden. Dann landet man bei Cobol, Railo, Fortran, C, Java, C#, C++, PL/SQL, PL/1, (Visual)Basic u.s.w. Wobei diese zum Teil sogar ihre sehr große „Nische“ haben, in der sie noch aktuell sind. Dass C für Systemprogrammierung noch sehr aktuell und fast konkurrenzlos ist, sei unbenommen.

Wenn keine Vorgaben durch Bibliotheken, Altlasten, IT-Landschaft u.s.w. bestehen, ist es natürlich interessant, in der zur Verfügung stehenden Zeit möglichst viel machen zu können. Eine Technologie, die einen zwingt, viel Zeit mit trivialen Aufgaben zu verbringen und die eigentlich interessanten Dinge in einem Wust von trivialem Code zu verstecken, den man nun einmal schreiben muss, darf man dann auch schon einmal hinterfragen. Letztlich sind zwei Wege vielversprechend, um mit wenig Code viel auszudrücken und letzlich in wenig Zeit viel zu entwickeln: Die funktionalen Sprachen wie z.B. F#, Clojure, Erlang, Elixir und Haskell. Oder die Skriptsprachen wie Ruby, Perl, Perl6 (wenn es mal fertig wird), Python und PHP. Natürlich überschneidet sich das ein Stück weit, weil einige funktionale Sprachen auch ein bißchen wie Skriptsprachen einsetzbar sind und einige Skriptsprachen auch gewisse funktionale Konstruktionen unterstützen.

Letztlich erweisen sich die funktionalen Sprachen als vielversprechend, wenn es darum geht, sehr leistungsstarke Applikationen zu entwickeln, die einen hohen Durchsatz und eine hohe Parallelisierung der Verarbeitung verwirklichen. Twitter soll mit Scala diesen Weg gegangen sein. Grundsätzlich bieten alle ernsthaften funktionalen Sprachen hier einige Möglichkeiten. F# lässt sich übrigens auch mit Mono kombiniert unter Linux verwenden. Vielleicht hat Erlang noch einen kleinen Vorteil, weil es schon auf VM-Ebene für diesen Einsatzbereich optimiert ist. Diese VM lässt sich aber auch mit Elixir verwenden. Aber man hat die Wahl zwischen mehreren Wegen.

Für viele Web-Applikationen hat sich Ruby als gut geeignet erwiesen, man sieht aber, dass es einige sehr gute PHP-Applikationen gibt. z.B. MediaWiki, die Software, mit der Wikipedia läuft. Allerdings zeichnet sich im Moment ein Trend ab, mehr von der Logik in Javascript auf der Client-Seite zu implementieren und serverseitig (fast) nur noch Webservices mit REST anzubieten, die die eigentliche Businesslogik und die Zugriffe auf die Daten zur Verfügung stellen. Diese REST-Services kann man natürlich in Ruby entwickeln; aber da gibt es viele Wege…

Ruby und vor allem Perl sind aber auch sehr stark, wenn es darum geht, Textdateien zu verarbeiten. Man kann diese nach Mustern durchsuchen, umgruppieren und umbauen und damit schöne Auswertungen machen. Für sehr große Datenmengen sollte man sich natürlich noch etwas eingehendere Gedanken machen, weil dann der Durchsatz und die Parallelisierung plötzlich mehr Bedeutung bekommen als das eigentlich Parsen des Texts. Aber man kann noch viel mehr…

Eine große Applikation kann diese Dinge auch kombinieren. GNU-Emacs ist eine sehr altes Beispiel, dass hier einen noch heute sehr aktuellen Ansatz verfolgt. Die Grundfunktionalität ist in C entwickelt und die weitergehenden Funktionen und Erweiterungen alle in Emacs-Lisp. So läßt sich ohne viel Aufwand einen Erweiterung einbinden, was nicht so leicht geht, wenn man erst einmal neu kompliieren muss. Die Idee lässt sich auch heute noch aufgreifen, wenn man eine Applikation z.B. in Scala entwickelt und dann die Möglichkeit anbietet, diese über Ruby- oder Groovy-Scripte anzusprechen, zu erweitern und zu konfigurieren.

Wenn man einmal an Häuser denkt, ist die Idee nicht so abwegig. Das eigentliche Haus ist relativ stabil aus Beton, Stein und Holz gebaut und bleibt in der Regel jahrzehntelang unverändert. Die Möbel sind selten aus Beton gegossen und eher flexibler (auch wenn sie vielerorts jahrzehntelang gleich stehen).

Share Button

Quadrat- und Kubikwurzeln berechnen vor 30 Jahren und heute ;-)

Unsere Rechner können sehr viele Rechenoperationen schon auf der CPU erledigen, wenn es darum geht, mit den Standardtypen (z.b. double, dem gängigen 8-Byte-Fließkommaformat) zu rechnen. Das war gegen Anfang der 80er Jahre noch nicht so, da konnten typische CPUs nur gerade mit 8-Bit-Ganzzahlen addieren, subtrahieren und ein paar Bit-Operationen ausführen und doch ließ sich daraus alles aufbauen. Langzahladdition und -subtraktion waren trivial, Multiplikation und Division etwas schwieriger, aber noch gut machbar. Aber für die Quadratwurzeln musste man schon etwas genauer überlegen. Das mitgelieferte Basic konnte das für 5-Byte-Fließkommazahlen, aber das Verfahren war einfach nur dumm und langsam, den es wurde der Logarithmus genommen, halbiert und dann die Exponentialfuntion. Mathematisch völlig richtig, aber eben langsam und mit unnötigen Rundungsfehlern behaftet. Wer sich ein bisschen mit dem Thema auskennt, landet recht schnell bei dem Newton-Verfahren. Man schätzt die Quadratwurzel, z.B. von 2, dividiert 2 durch den Schätzwert und nimmt dann den Mittelwert von Schätzung und Quotient für die nächste Iteration. Zu offensichtlich, um es nicht so zu machen und in der Praxis auch ganz brauchbar. Es gibt aber ein Verfahren, wie man früher ähnlich wie die Division auch die Quadratwurzeln „handschriftlich“ berechnen konnte und dieses Verfahren lässt sich sehr gut verwenden, um eine Quadratwurzelberechnung zu schreiben. Hier ist eine Ruby-Implementierung, die von Ganzzahlen ausgeht:
Zu einer ganzen Zahl x \ge 0 werden ganze Zahlen r \ge 0 und s \ge 0 gesucht so dass x = r + s^2 und (s+1)^2 > x gilt.

  def check_is_int(x, name="x")
    raise TypeError, "#{name}=#{x.inspect} must be Integer" unless x.kind_of? Integer
  end

  #
  # helper method for internal use: checks if word_len is a reasonable
  # size for splitting a number into parts
  #
  def check_word_len(word_len, name="word_len")
    raise TypeError, "#{name} must be a positive number <= 1024" unless (word_len.kind_of? Fixnum) && word_len > 0 && word_len <= 1024
    word_len
  end

  #
  # split number (Integer) x into parts of word_len bits each such
  # that the concatenation of these parts as bit patterns is x
  # (the opposite of merge_from_words)
  #
  def split_to_words(x, word_len = 32)
    check_word_len(word_len)
    check_is_int(x, "x")
    m = x.abs
    s = (x <=> 0)
    bit_pattern = (1 << word_len) - 1
    words = []
    while (m != 0 || words.length == 0) do
      w = m & bit_pattern
      m = m >> word_len
      words.unshift(w)
    end
    if (s < 0) then
      words[0] = -words[0]
    end
    words
  end


  #
  # calculate the an integer s >= 0 and a remainder r >= 0 such that
  # x = s**2 + r and s**2 <= x < (s+1)**2
  # the wordwise algorithm is used, which works well for relatively
  # large values of x.  n defines the word size to be used for the
  # algorithm.  It is good to use half of the machine word, but the
  # algorithm would also work for other values.
  #
  def sqrtw_with_remainder(x, n = 16)
    check_is_int(x, "x")
    check_is_int(n, "n")

    n2 = n<<1
    n1 = n+1
    check_word_len(n2, "2*n")

    s = (x <=> 0)
    if (s == 0) then
      return [0, 0]
    elsif (s < 0)
      a = sqrtw_with_remainder(-x)
      return [ Complex(0, a[0]), a[1]]
    end

    xwords = split_to_words(x, n2)
    if (xwords.length == 1) then
      return sqrtb_with_remainder(xwords[0])
    end

    xi = (xwords[0] << n2) + xwords[1]
    a  = sqrtb_with_remainder(xi)
    yi = a[0]
    if (xwords.length <= 2) then
      return a
    end

    xi -= yi*yi
    2.upto(xwords.length-1) do |i|
      xi = (xi << n2) + xwords[i]
      d0 = (yi << n1)
      q  = (xi / d0).to_i
      q0 = q
      j  = 0
      was_negative = false
      while (true) do
        d = d0 + q
        r = xi - (q * d)
        break if (0 <= r && (r < d || was_negative))
        if (r < 0) then
          was_negative = true
          q = q-1
        else
          q = q+1
        end
        j += 1
        if (j > 10) then
          break
        end
      end
      xi = r
      yi = (yi << n) + q
    end
    return [ yi, xi ]
  end

  #
  # calculate an integer s >= 0 and a remainder r >= 0 such that
  # x = s**2 + r and s**2 <= x < (s+1)**2
  # the bitwise algorithm is used, which works well for relatively
  # small values of x.
  #
  def sqrtb_with_remainder(x)
    check_is_int(x, "x")

    s = (x <=> 0)
    if (s == 0) then
      return [0, 0]
    elsif (s < 0)
      a = sqrtb_with_remainder(-x)
      return [ Complex(0, a[0]), a[1]]
    end

    xwords = split_to_words(x, 2)
    xi = xwords[0] - 1
    yi = 1

    1.upto(xwords.length-1) do |i|
      xi = (xi << 2) + xwords[i]
      d0 = (yi << 2) + 1
      r  = xi - d0
      b  = 0
      if (r >= 0) then
        b  = 1
        xi = r
      end
      yi = (yi << 1) + b
    end
    return [yi, xi]
  end

Daraus lässt sich dann relativ einfach eine Quadratwurzelfunktion mit entsprechender Nachkommstellenberechnung bilden.

Witzerweise lässt sich das Verfahren auch für Kubikwurzeln sinngemäß anwenden.

Hier ein kleiner Test:

irb(main):138:0> sqrtw_with_remainder(2)
=> [1, 1]
irb(main):139:0> sqrtw_with_remainder(200)
=> [14, 4]
irb(main):140:0> sqrtw_with_remainder(20000)
=> [141, 119]
irb(main):141:0> sqrtw_with_remainder(2000000)
=> [1414, 604]
irb(main):142:0> sqrtw_with_remainder(200000000000000000000000000000000000000000000000000000000000)
=> [447213595499957939281834733746, 228299936041363866321288807484]
irb(main):143:0> sqrtw_with_remainder(2000000000000000000000000000000000000000000000000000000000000)
=> [1414213562373095048801688724209, 1974464361663955412145937324319]
irb(main):144:0> sqrtw_with_remainder(3000000000000000000000000000000000000000000000000000000000000)
=> [1732050807568877293527446341505, 3021967735564464902990914334975]
irb(main):145:0> sqrtw_with_remainder(3)
=> [1, 2]
irb(main):146:0> sqrtw_with_remainder(300)
=> [17, 11]
irb(main):147:0> sqrtw_with_remainder(30000)
=> [173, 71]
irb(main):148:0> sqrtw_with_remainder(3000000)
=> [1732, 176]
Share Button