Rundung mit Summe

English

Häufig muss man einige Zahlen auf einmal runden, aber die Summe soll hinterher „aufgehen“. Das kann man „summenerhaltendes Runden“ nennen, wobei unter Umständen auch die Summe gerundet wird. Der häufigste Fall sind Prozentwerte und wenn die gerundeten Zahlen nicht zusammen 100% ergeben, versteht das niemand. Da kann es schon besser sein, etwas schwieriger verständliche Dinge hinter den Kulissen zu tun. Kurz gesagt ist unsere Frage, ob die Rundung ein Endomorphismus der additiven Gruppe ist. Das bedeutet, dass \bigwedge_{x,y\in M} r(x+y)=r(x)+r(y). Auf den resten Blick sieht das vernünftig aus und die Fehler heben sich ja oft irgendwie weg. Aber wir können für eine gängige Rundungsmethode ein Gegenbeispiel finden: x=1.4, y=2.3, z=3.3. Wir haben x+y+z=7. Jetzt wird das gerundet und ergibt r(x)=1 \wedge r(y)=2 \wedge r(z)=3 \bigrightarrow r(x)+r(y)+r(z)=6 \ne 7. Ein Gegenbeispiel reicht und es ist kein Endomorphismus.

Ist das ein ganz neues Konzept? Es wird ja offensichtlich in fast allen Druckerzeugnissen, die irgendwie Prozentwerte so angeben, für die Gesamtsumme „gemogelt“. Aber es stellt sich heraus, dass das auch hochoffiziell alle vier Jahre passiert. Wir haben irgendwelche Ereignisse, die sich „Wahlen“ nennen und da kann man Parteien oder Listen für ein Parlament eine Stimme geben. Das Parlament hat meistens eine vorgegebene Anzahl von Sitzen, wenn wir mal Spezialitäten wie 5%-Sperrklausel und Überhangmandate in der deutschen Wahlpraxis vergessen, um es noch halbwegs für Logik zugänglich zu halten. Man stelle sich nur vor, was passiert, wenn 40 Parteien antreten und je 2.5% erhalten, um zu sehen, dass das System nicht korrekt ist, im Sinne einer korrekten Software. Nun sollte man meinen, die Parlamentssitze werden einfach im Verhältnis der Stimmen aufgeteilt. Wenn man n Parlamentssitze hat, werden die Stimmenanteile in Prozent auf Vielfache von \frac{100}{n} gerundet und zwar so, dass es am Schluss aufgeht. Es gibt viele Verfahren, um das zu bewerkstelligen und je nachdem, welches Verfahren man auswählt, kann bei denselben Stimmenzahlen die Sitzverteilung geringfügig variieren. Habe ich das Wort „Mogeln“ oben erwähnt? Es muss wohl Zufall sein. Welches Verfahren gerade am gerechtesten ist, wechselt also von Jahr zu Jahr immer wieder ein bisschen.

Wenn wir nicht gerade eine Wahlauswertungssoftware schreiben, ist in den meisten Fällen diese Frage weniger aufgeladen. Es soll in einem Text eine Summe von mehreren gerundeten Werten eingehalten werden und die Rundung soll „einigermaßen vernünftig“ erfolgen. Der oberflächliche Leser wird zufrieden sein, der etwas kritischere auch, weil die Summe stimmt und der Leser, der sich richtig Gedanken macht wird es auch verstehen, dass man da mogeln musste und dass man das einigermaßen sinnvoll getan hat. Man beachte, dass diese Thematik einige Überraschungen birgt, z.B. das Alabama-Paradoxon und das Wählerzuwachsparadoxon.

Wie in Restklassenrundung beschrieben, gehen wir von Mengen M und N \subseteq M mit einer Metrik d: M\times M \rightarrow {\Bbb R_+}, (m, n) \mapsto d(m,n) \ge 0 aus und wollen Abbildungen r : M \rightarrow N betrachten, bei denen d(x, r(x)) klein bleibt und eventuell ein paar weitere Bedingungen erfüllt sein sollen. Da aber die Korrektur schon Teil der Abbildung sein soll, interessiert uns hier eigentlich eher so etwas wie eine Abbildung
s: M^n \rightarrow N^n, (m_1,\ldots,m_n) \mapsto (n_1,\ldots n_n) mit \sum_{i=1}^n m_i = \sum_{i=1}^n n_i und für alle i ist d(m_i,n_i) „klein“. Reine Auf- oder Abrundung kann also nicht die Lösung sein, da das nie aufgeht. Wir könnten die Fehlerquadrate minimieren, was den Vorteil hat, das große absolute Abweichungen sich stärker auswirken, so dass eine gleichmäßige Verteilung der Korrektur besser wegkommt, also z.B.
\sum_{i=1}^n (d(m_i, n_i))^2 ist minimal. Es lassen sich Beispiele konstruieren, wo das nicht eindeutig ist. In dem Fall kann man entweder eine Regel festlegen oder mit Zufallszahlen ermitteln welche der passenden Möglichkeiten zum Zuge kommt. Man kann auch versuchen, die relativen Fehler zu minimieren, also so etwas wie
\sum_{i=1: m_i \ne 0}^n (\frac{d(m_i,n_i)}{d(m_i,m_i)})^2, wobei man die Summanden mit m_i=0 weglassen muss, was nicht stört, wenn 0\in N ist, man also sowieso 0 auf 0 runden will.
Eine Alternative ist, sich einfach an den Sitzzuteilungsverfahren für Parlamente zu orientieren und deren Algorithmen sinngemäß für die hier beschriebene Aufgabe anzupassen:

Oft sind die Anforderungen an die „Qualität“ der Rundung niedriger als bei der Zuteilung von Parlamentssitzen, aber es lohnt sich schon, sich hierüber einige Gedanken zu machen statt einfach irgendwie mit einem naiven Ansatz zu runden.

Frage: Wie verhalten sich die oben aufgeführten Sitzzuteilungsverfahren zur Minimierung der absoluten und relativen Fehlerquadrate?

Bei genügendem Interesse kann ich einmal eine Implementierung für so eine Rundung hinzufügen.

Gelegentlich begegnen uns auch Probleme, die dem hier geschilderten sehr ähnlich sind oder die sich darauf zurückführen lassen. Wer hätte gedacht, dass die Zuteilung von Parlamentssitzen eigentlich eine Rundung ist?

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

Auf GPU rechnen

Heutige Rechner haben bekanntlich sehr leistungsfähige CPUs mit „Quadcore“ und mehr.
Aber auch die Grafikkarten sind ziemlich toll geworden und haben zum Teil auch so große eigene Lüfter wie die CPU.
Sie haben eine Menge eigenes Memory und sie können recht komplizierte Operationen selbsttätig rechnen, natürlich nur für die grafische Darstellung.

Nun stellt sich die Frage, ob man das auch sonst zum Rechnen benutzen kann. Man hört Geschichten, dass die Grafikkarte um Größenordnungen leistungsfähiger als die CPU sei. Warum schaffen das die Grafikkartenhersteller so leicht nebenbei, besser als die CPU in deren Kernaufgabe zu sein und außerdem noch Grafik darzustellen?

Grafikkarten bieten die Möglichkeit, massiv parallel zu rechnen, aber nach dem Prinzip SIMD. Das heißt, dass ein oder sehr wenige Befehlsströme verarbeitet werden und eine große Zahl von Recheneinheiten jeweils den identischen Code mit verschiedenen Daten ausführt. Für Vektoroperationen ist das optimal. Und es erklärt auch die brachiale Leistung der Grafikchips, weil man den aufwändigen Teil, Maschinencode zu interpretieren, nur einmal (oder wenige Male) baut und nur die eigentliche Recheneinheit mehrfach. Man bekommt so mit derselben Siliziummenge mehr Rechenleistung, aber mit der Einschränkung, SIMD (oder fast SIMD) zu sein. Aber man hat diese Geräte in den Rechnern drin. Es gibt sogar „Grafikkarten“, die nur rechnen können, aber bei denen man die eigentlichen Grafikchips weggelassen hat. Und viele Rechner haben den Grafikkern mit auf dem selben Chip wie die CPU-Kerne, so dass man eine einfache Grafik zur Verfügung hat, aber man baut dann doch zusätzlich noch eine externe Grafikkarte ein, die noch besser ist. Selbst ohne die Grafikfähigkeit zu gefährden hat man also eine GPU zum Rechnen übrig.

Nun ist das Programmieren dieser Geräte nicht so einfach. Grundsätzlich muss man sich mit einem völlig neuen Programmiermodell herumschlagen. Viele Algorithmen lassen sich speziell für SIMD entwickeln, aber sie sind anders als was wir gewohnt sind und automatisch lässt sich da nur beschränkt etwas optimieren. In der Regel muss man also mit C das Programm schreiben und kann dabei auf OpenCL bauen. Das ist ein nützlicher Standard, der einiges erleichtert, aber es bleibt schwierig. Für manche Zwecke lohnt es sich aber, den Entwicklungsaufwand zu treiben.

Vor ein paar Tagen habe ich drei Vorträge über Ansätze gehört, F# zu verwenden, um die GPU zu programmieren. Man kann also unter Einhaltung gewisser Regeln F#-Programme schreiben, die sich etwa in OpenCL übersetzen lassen und dann compiliert die GPU nutzen:

  • FSCL: Homogeneous Programming and Execution on Heterogeneous Platforms (by Gabriele Cocco, Pisa University)
  • Professional GPU Development with F# and the Alea Compiler Suite (by Daniel Egloff, QuantAlea)
  • New Abstractions for Radically Simplified GPU Programming in F# and .NET (by Luc Bläser, HSR, based on joint work with QuantAlea)

All diese Ansätze sollten schon heute oder zumindest in zukünftigen Implementierungen auch für Mono laufen und damit für Linux zur Verfügung stehen.

Es würde wohl den Rahmen dieses Artikels sprengen, im Einzelnen darauf einzugehen, aber vielleicht kann ich noch Links bekommen, die auf weiterführendes Material zu den einzelnen Lösungsansätzen führen.

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

Numerische Typen

Es geht hier nicht um dynamische oder statische Typsisierung, sondern eher darum, was von den Programmiersprachen an Funktionalität für numerische Typen angeboten wird. Irgendeine Form der Typisierung (dynamisch oder statisch) ist natürlich erforderlich, damit das funktionieren kann. Im Extremfall reicht vielleicht sogar der Ansatz, dass durch die Funktionsnamen unterschieden wird, als welche Typen die Eingabeparameter zu interpretieren sind, was z.B. bei Assemblersprachen praktisch durchgängig so üblich ist.

Was ich bei numerischen Typen sehr wichtig finde, ist dass man die Formeln, die die Berechnung beschreiben, so hinschreiben kann, wie sie sind, also z.B.

    \[ a = b \cdot c + d \cdot e \]

oder

a = b * c + d * e

oder gerne auch

a := b (*) c (+) d (*) e

statt

a = (b * c) + (d * e),

denn „Punktrechnung vor Strichrechnung“ lernt man in der Grundschule und das sollte zumindest bei Leuten, die sich mit Quelltexten von Software beschäftigen, im Erwachsenenalter sitzen. Damit will ich nicht sagen, dass man jeweils alle Präzendenzhierarchiestufen aller verwendeten Programmiersprachen kennen sollte, aber diese her schon. Smalltalk zwingt einen zu diesen Klammern.

Noch schlimmer ist Java, wo man für die meisten numerischen Typen etwa so etwas schreiben muss:

a = b.multiply(c).add(d.multiply(e));

Da erkennt kaum jemand die Formel wieder und Fehler sind vorprogrammiert…
Für Software, die in größerem Stil Dinge tut, die mit den primitiven numerischen Typen nicht machbar sind, ist Java nicht geeignet. Andere JVM-Programmiersprachen haben Operatorüberladung und erlauben es, mit geringerem Fehlerrisiko solche Dinge zu entwickeln. Eventuell kann auch ein Präprozessor eingesetzt werden, der eine Java-ähnliche Sprache mit einer Form von Operatorüberladung in Java übersetzt.

Was vielleicht auch geht, ist statt Infix auf Postfix- oder Präfixnotation zu wechseln. Ob man da die Formeln noch erkennt, ist ein bißchen eine Gewohnheits-, Geschmacks- und vielleicht auch Fähigkeitsfrage, wobei es sicher gute SW-Entwickler gibt, die einfach nicht den Blick dafür haben, Infix-Notation oder Postfix-Notation zu erkennen. Das sieht dann mit Präfixnotation in Lisp etwa so aus:

(setq a (+ (* b c) (* d e)))

oder mit Postfix-Notation, die man von alten HP-Taschenrechnern oder von Forth oder von der Druckersprache Postscript kennen könnte etwa so:

&a
b
c
*
d
e
*
+
=

oder etwa so:

b ENTER C * ENTER d ENTER e * + STO a

Angeblich soll das verständlicher sein als die Infixnotation, sagen manche HP-Taschenrechner-Fans aus den 80er Jahren.

In diesem Blogbeitrag über Zahlen steht ein bißchen dazu, auf was sich numerische Typen beziehen können. Eine 1:1-Zuordnung ist in der Regel nicht möglich, weil selbst „unbegrenzte“ Ganzzahlen wie bei Ruby oder Lisp in Wirklichkeit durch den Speicher des Rechners begrenzt sind. Aber man kann doch eine realistische Approximation erkennen.

  Ruby Perl Python Java Scala Clojure Elixir C C++
{\Bbb N}, {\Bbb N_0} ? ? ? (unsigned long eingeschränkt da, Überlauf) (unsigned long eingeschränkt da, Überlauf)
{\Bbb Z} nativ (Integer, BigNum) BigInt ? (BigInteger eingeschränkt wegen fehlendem Operator-Überladen) BigInteger nativ nativ (externe Libraries, z.B. GMP, eingeschränkt brauchbar wegen fehlendem Operator-Überladen) externe Libraries, z.B. GMP
{\Bbb Q} Rational Math::BigRat Fraction (externe Libraries, eingeschränkt brauchbar wegen fehlendem Operator-Überladen) externe Libraries, eventuell Aufnahme in Standardlibrary geplant. nativ ? (externe Libraries, z.B. GMP, eingeschränkt brauchbar wegen fehlendem Operator-Überladen) externe Libraries, z.B. GMP
{\Bbb R} Float, LongDecimal, BigDecimal ja ? Double, BigDecimal Double, BigDecimal ? ? double double
{\Bbb C} Complex ? ? externe Libraries ohne Operatorüberladung mühsam und fehleranfällig. ? ? ? complex ?

p-adische Zahlung und endliche Körper sind wohl schon zu sehr in der Mathematik angesiedelt und selten nativ in Programmiersprachen zu finden, außer in Programmiersprachen, die gezielt eine mathematiklastige Clientel ansprechen. Dabei sind gerade endliche Körper noch recht wichtig für Kryptographie und Codierungstheorie und werden dort natürlich auch benutzt.

Am schmerzhaftesten ist wohl immer noch, dass so wenige Programmiersprachen einen guten ganzzahligen numerischen Typ in die Sprache integriert haben, der es erlaubt, mit beliebig langen Zahlen (im Rahmen von Hauptspeicher) umzugehen.

Programmiersprachen, die so etwas wie Rational als numerischen Typ kennen, lassen ein gängiges Problem erkennen. Erfahrungsgemäß werden bei längeren Rechnungen Nenner und Zähler sehr sehr groß und die Berechnung entsprechend langsam. Dass man gut kürzen kann, ist eher die Ausnahme. Daran sollte man denken und entsprechende Performance- und Lasttests machen, um zu sehen, ob man in Laufzeit- und Speicherprobleme gerät.

Share Button

Shift- und Rotationsfunktionen

English

Im Kommentar zu Carry Bit: How does it work ist nach den Shift- und Rotationsfunktionen gefragt worden. Welche es genau gibt, hängt natürlich von der Prozessorarchitektur ab, aber grundsätzlich muss man die folgenden Aspekte beachten:

  • 8, 16, 32, 64,… Bit: Wieviele Bits sind von der Operation betroffen?
  • Shift vs. Rotate: Beim Shift werden an einer Seite Bits als 0 oder 1 ergänzt und auf der anderen Seite wandern sie in das Carry-Bit, beim Rotieren werden Bits im Kreis rotiert, die herausfallenden Bits vom einen Ende werden am anderen Ende wieder eingefügt.
  • ROL und ROR vs RCL und RCR: Beim Rotieren durch Carry wird das Carry-Bit als 9., 17., 33. oder 65. Bit miteinbezogen.
  • Logical vs. Arithmetic Shift: Bezieht sich auf die Vorzeichenbehandlung. Für arithmetic Shift wird die Zahl als vorzeichenbehaftet im Zweierkomplement gelesen wird. Deshalb wird beim Right-Shift nicht zwingend eine 0 als höchstwertiges Bit eingefügt, sondern je nach Vorzeichen eine 0 oder eine 1.

Heutige CPUs haben Barrelshifter oder etwas vergleichbares eingebaut und können deshalb auch Shift- und Rotate-Operationen um mehr als eine Bit-Position schnell ausführen.

Wie die Befehle genau heißen, und welche es gibt, hängt vom Prozessor ab:

Beispiele (8 Bit), Verschiebung oder Rotation nur um eine Bitposition:

Vorher (Carrybit in Klammern)ROL
(rotate left)
RCL
(rotate left through carry)
ROR
(rotate right)
RCR
(rotate right through carry)
ASL / SHL
(arithmetic/logical shift left)
SHR
(logical shift right)
ASR
(arithmetic shift right)
00000000 (0)00000000 (0)00000000 (0)00000000 (0)00000000 (0)00000000 (0)00000000 (0)00000000 (0)
00000000 (1)00000000 (1)00000001 (0)00000000 (1)10000000 (0)00000000 (0)00000000 (0)00000000 (0)
00000001 (0)00000010 (0)00000010 (0)10000000 (0)00000000 (1)00000010 (0)00000000 (1)00000000 (1)
00000001 (1)00000010 (1)00000011 (0)10000000 (1)10000000 (1)00000010 (0)00000000 (1)00000000 (1)
10000000 (0)00000001 (0)00000000 (1)01000000 (0)01000000 (0)00000000 (1)01000000 (0)11000000 (0)
10000000 (1)00000001 (1)00000001 (1)00000001 (1)11000000 (0)00000000 (1)01000000 (0)11000000 (0)
11111111 (0)11111111 (0)11111110 (1)11111111 (0)01111111 (1)11111110 (1)01111111 (1)11111111 (1)
11111111 (1)11111111 (1)11111111 (1)11111111 (1)11111111 (1)11111110 (1)01111111 (1)11111111 (1)

Diese Shift- und Rotate-Operationen braucht man vor allem, um Multiplikation mit Zweierpotenzen und Division durch Zwierpotennzen auszudrücken. In C, C++, Perl, Java und einigen anderen Programmiersprachen gibt es diese Operationen „<<" (für ASL oder SHL), ">>“ (für SHR) und „>>>“ für ASR.

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

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

Integration numerischer Typen in Programmiersprachen

Rechnen ist ja das, was wir mit den Computern so machen, deshalb heißen sie ja auch Rechner.
Und zum Rechnen brauchen wir die numerischen Typen andauernd, also kann das wohl kein Problem sein, oder?

Es hängt ein bißchen davon ab, was man sich unter numerischen Typen vorstellt. Fließkommazahlen oder irgendeine Art von Ganzzahlen können fast alle, manche sogar beides. Gute Ganzzahlentypen sind aber leider nur selten verfügbar, da die Frage des Überlaufs oft schlecht gelöst ist. Weitere interessante numerische Datentypen sind rationale Zahlen, komplexe Zahlen und Festkomma-Dezimalzahlen.

Doch wie sieht es mit der Integration in die Sprache aus? Man möchte gerne so etwas wie
a = b*c + d*e
schreiben und meint damit, daß eine Zuweisung an a erfolgen soll, die den Wert (b*c) + (d*e) beinhaltet. Wegen „Punktrechnung vor Strichrechnung“ sollte man die Klammern aber weglassen können. Im Fall von Sprachen wie Lisp oder Forth, die eine völlig andere Syntax verwenden, paßt diese Infix-Schreibweise natürlich nicht ins Bild und man kann diese Anforderung nicht sinnvoll stellen. In Lisp mit der Präfix-Schreibweise wäre es so etwas wie:
(setq a (+ (* b c) (* d e)))
und in Forth mit seiner Postfix-Schreibweise wäre es etwa so etwas:
b @ c @ * d @ e @ * + a ! .
C, Perl, Ruby, C++, Java, C#, JavaScript, Lua und vielen anderen funktioniert das mit den eingebauten Datentypen recht gut, aber sobald man eigene numerische Datentypen einführt, braucht man so etwas wie „Operator überladen“, was z.B. Lua, Perl, Ruby, C++ und C# können, aber Java und JavaScript nicht. Deshalb fängt man in Java an, für BigDecimal, BigInteger oder eigene Datentypen so etwas wie
a = b.multiply(c).add(d.multiply(e))
zu schreiben, was praktisch unlesbar und damit fehleranfällig ist. Vielleicht kann man sich mit einem Präprozessor behelfen, aber es bleibt ein Gebastel.

Ein anderer Aspekt ist am Beispiel von Java ganz gut zu sehen. Dort soll ja „alles“ ein Objekt sein. Man kann schön Interfaces, Klassen und Methoden schreiben und Verwenden, die sich auf Objekte verlassen, wie z.B. Map. Nun sind diese „primitiven“ Typen leider keine Objekte und man muß diese Wrapper-Klassen wie Integer, Double, Long, Boolean u.s.w. verwenden, was leider umständlich ist, zumal man mit den Wrappern die numerischen Fähigkeiten nicht mehr zur Verfügung hat. Scheinbar wurde das durch Autoboxing und Autounboxing gelöst, aber ich glaube, daß diese Erweiterung mehr Probleme geschaffen als gelöst hat. Nur als Beispiel, was bedeutet
x==y
wenn x und y long oder Long sind? Mal wird die Objekt-Identität und mal der Wert verglichen und ich vergesse immer, ob unboxing oder boxing zum Zuge kommt, wenn man dabei long und Long zusammenkommen läßt. Man kann aber einige spezielle Collection-Klassen finden, die auf Primitive zugeschnitten sind und dadurch ohne Boxing und Autoboxing auskommen, schneller laufen und weniger Speicher verbrauchen. In erster Linie bleibt es aber umständlich, weil man immer wieder diese Sonderfälle für Primitive und zum Teil auch Arrays berücksichtigen muß.

Share Button

Fließkommazahlen als Ersatz für Ganzzahlen

Wie ärgerlich ist eigentlich die Tatsache, daß Lua und JavaScript keine „int“s kennen und man stattdessen Fließkommazahlen („double“) verwenden muß?

Natürlich fühlt es sich völlig falsch an und ich möchte die Entscheidung, nur diese 8-byte-Fließkomma-Zahlen als numerischen Typ zu unterstützen, nicht gutheißen.

Aber was bedeutet das nun genau? Bekommen wir nun plötzlich irgendwo 7.999999999 statt 8?

Die Fließkommazahlen sind heute zum Glück standardisiert und fast jede Implementierung hält sich einigermaßen an diesen Standard. Es gibt eine 4-Byte-Variante und eine 8-Byte-Variante. Die 4-Byte-Variante ist nur dann sinnvoll, wenn man dem Entwickler die Wahl läßt, und fast jeder Entwickler nimmt „zur Sicherheit“ lieber die 8-Byte-Variante. Diese Fließkommazahl sieht nun ungefähr so aus:
1 Bit ist das Vorzeichen
11 Bits drücken den 2er-Exponenten aus
52 Bits drücken die Mantisse aus, dazu kommt als 53stes eine führende 1, die man nicht speichern muß, weil sie ja immer da ist.
Damit kann man die ganzen Zahlen von -2^{53} bis 2^{53} exakt ausdrücken und hat damit etwas, was etwa 54-Bit-Ganzzahlen entsprechen würde. Rein Informationsmäßig ist das eine zusätzliche Bit im Vorzeichen und das andere im 2-er-Exponenten codiert. Wenn man also nur addiert, subtrahiert und multipliziert und dabei immer im Bereich von -2^{53} bis 2^{53} bleibt, kann man exakte Ergebnisse erwarten. Natürlich ist es langsamer, aber auch das ist bei heutigen CPUs, die schnelle Fließkommaoperationen seit etwa 20 Jahren standardmäßig (und vorher gegen Aufpreis) in der Hardware eingebaut haben, nicht so tragisch. Wie ist es mit den ungenutzten Bits? Normalerweise stören die nicht, aber wenn man Applikationen entwickelt, die sehr speicherintensiv sind, kann auch so etwa ausnahmsweise mal relevant werden.

Ärgerlicher ist da schon die Divsion. Hat man bei ints so etwas wie „/“ für die Division mit Abrundung und „%“ für den Rest, wird bei Fließkommazahlen mit „/“ wirklich dividiert und eine neue Fließkommazahl berechnet. Wie rundet man hier ab, um das „int-/“ und das „int-%“ zu bekommen? Es sollte dabei ja trotzdem noch das 6.9999999999999 zu 7 gerundet werden.

Ungefähr so etwas könnte funktionieren:

def divmodf(x, y)
xf = x.to_f
yf = y.to_f
df = if (yf < 0) then
-0.2
else
0.2
end
qf = (xf + df) / yf;
q = qf.floor
r = (yf*(qf-q)).round(0)
return q,r
end

Das ist jetzt in Ruby geschrieben, aber es würde natürlich ähnlich in Lua oder JavaScript funktionieren.

Share Button