Aktualisierung von WordPress

English

Die Aktualisierung von WordPress und Plugins hat hier nicht so gut funktioniert.

Es hat eine kleine Änderung geholfen, jetzt ist alles gut:

In .htaccess am Anfang diese Zeile

AddHandler php56-cgi .php

einfügen…
Danach funktionierten alle Updates gut.

Vielleicht hilft das auch anderen, die damit Probleme hatten….

Share Button

O’Reilly schließt Aktivitäten in Deutschland

This article is of minor relevance to English speaking readers, because it concerns the German O’Reilly books, while the English O’Reilly books continue to be available. So I will write in German.

Der O’Reilly-Verlag hatte jahrelang eine deutsche Niederlassung in Köln, wo deutschsprachige Versionen der beliebten Informatik-Fachbücher herausgegeben wurden. Dies waren oft Übersetzungen, aber in einigen Fällen auch exklusiv in deutscher Sprache erscheinende Titel oder doch Titel, die später vom Deutschen ins Englische übersetzt wurden. Der d-Punkt-Verlag wird die Aktivitäten übernehmen und auch unter dem Name O’Reilly weiterführen.

Mehr dazu unter
Informatik Aktuell.

Share Button

How to multiply long numbers

Assuming we have a multiplication of n-bit-numbers already available.
Other than typical compiled languages, which assume that the multiplication result fits into the same size as the two factors, we should take a closer look.
Unsigned n-bit-numbers as factors x and y fullfill

    \[0 \le x \le 2^n-1\]

    \[0 \le y \le 2^n-1\]

So we have for the product z=x*y

    \[0 \le z \le (2^n-1)^2 \le 2^{2n}-1\]

So we should be prepared for a 2n-bit long result. Assembly language provides for this. In Java we are kind of running out of luck, because we have the 64-bit-long as the largest possible value, so we cannot make use of the 64-bit capabilities of our CPU by getting a 128-bit-result. Even worse we do not have unsigned primitive types. For addition and subtraction it is possible to cheat by assuming that the longs are unsigned, because the addition for signed and unsigned numbers is almost the same, but for multiplication this is slightly more complex.

In C we do have better chances, but we need to go compiler and OS-specific to some extent. gcc on 64-bit platforms has a type __uint128_t and we can hope that something like this

__uint128_t mul(unsigned long long x, unsigned long long y) {
  __uint128_t xx = (__uint128_t) x;
  __uint128_t yy = (__uint128_t) y;
  __uint128_t z = xx*yy;
  return z;
}

is optimized by the compiler to one assembly language instruction that multiplies two unsigned 64-bit-integers into one unsigned 128-bit integer.

Multiplication of longer numbers is achieved by just assuming

    \[ x= \sum_{j=0}^{m-1}2^{nj}x_j, y= \sum_{j=0}^{m-1}2^{nj}y_j\]

with

    \[ \bigwedge_{j=0}^{m-1} 0\le x_j, y_j <2^n.\]

Now the product is

    \[ z = \sum_{j=0}^{m-1}\sum_{k=0}^{m-1}2^{n(j+k)}x_j y_k \]

where each x_j y_k summand needs to be split into a lower and an upper part such that

    \[x_j y_k = 2^n h(x_j y_k) + l(x_j y_k).\]

All these half products need to be added with propagating the carry bits to the next higher level.
This can be sorted out and done with a lot of additions with carry-bit, finally giving the desired result.

For reasonably short numbers this is a good approach, if it is done well, but it can be replaced by better algorithms for larger numbers.

The most obvious next step is to move to the Karatsuba algorithm.
Assuming we have two factors x=x_l + 2^m x_h and y = y_l + 2^m y_h the naïve approach of having to calculate the four products
x_h y_h, x_h y_l, x_l y_h, x_l y_l can be replaced by calculation of only three products x_h y_h, (x_l + x_h)(y_l+ y_h), x_l y_l, because what is actually needed is the sum x_h y_l+x_l y_h which can be obtained by

    \[(x_l + x_h)(y_l+ y_h)-x_l y_l-x_h y_h=x_h y_l+x_l y_h.\]

That can be iterated by subdividing the numbers subsequently into halves until a size is reached that can be handled well enough by the naïve approach.
An issue that needs to be observed is that x_l + x_h and y_l+ y_h need one bit more than their summands.

For even larger numbers the so called Toom-Cook algorithm, an extension of the idea of the Karatsuba-algorithm for more than two summands, can be useful and for numbers larger than that the Schönhage-Strassen multiplication proves to be faster. It is implemented in some libraries for long integer arithmetic, like GMP. Since around 2007 this can be improved by using the Fürer algorithm which is assymptotically faster, but I do not know of any useful implementations and for practical purposes the improvement does not seem to be very relevant.

Addition 2019-10-08: In 2019 an algorithm has been discovered, that is assumed to be assymptotically O(n \log n), which is according to a conjecture of Schönhage the best possible result. It has not yet been proven rigorously and the conjecture is still a conjecture. The question is, if for practical purposes of multiplying numbers that still fit into real computers, there is a real gain from these algorithms. So the questions is, if they become faster than Schönhage-Strassen on numbers that are not too long to be practically multiplied. So right now this is really mostly an issue of mathematics and theoretical informatics. See also Maths whiz solves 48-year-old multiplication problem.. And see for the paper.

Share Button

How to recover the Carry Bit

As frequent readers might have observed, I like the concept of the Carry Bit as it allows for efficient implementations of long integer arithmetic, which I would like to use as default integer type for most application development. And unfortunately such facilities are not available in high level languages like C and Java. But it is possible to recover the carry bit from what is available in C or Java, with some extra cost of performance, but maybe neglectable, if the compiler does a good optimization on this. We might assume gcc on a 64-Bit-Linux. It should be possible to do similar things on other platforms.

So we add two unsigned 64-bit integers x and y and an incoming carry bit i\in\{0, 1\} to a result

    \[z\equiv x+y+i \mod 2^{64}\]

with

    \[0 \le z < 2^{64}\]

using the typical „long long“ of C. We assume that

    \[x=2^{63}x_h+x_l\]

where

    \[x_h \in \{0,1\}\]

and

    \[0 \le x_l < 2^{63}\]

. In the same way we assume y=2^{63}y_h + y_l and z=2^{63}z_h + z_l with the same kind of conditions for x_h, y_h, z_h or x_l, y_l, z_l, respectively.

Now we have

    \[0 \le x_l+y_l + i \le 2^{64}-1\]

and we can see that

    \[x_l + y_l + i = 2^{63}u + z_l\]

for some

    \[u\in \{0,1\}\]

.
And we have

    \[x+y+i = 2^{64}c+z\]

where

    \[c\in\{0,1\}\]

is the carry bit.
When looking just at the highest visible bit and the carry bit, this boils down to

    \[2c+z_h = x_h + y_h + u\]

This leaves us with eight cases to observe for the combination of x_h, y_h and u:

x_hy_huz_hc
00000
10010
01010
11001
00110
10101
01101
11111

Or we can check all eight cases and find that we always have

    \[c = x_h \wedge\neg z_h \vee y_h \wedge\neg z_h \vee x_h \wedge y_h \wedge z_h\]

or

    \[c = (x_h \vee y_h) \wedge\neg z_h \vee x_h \wedge y_h \wedge z_h.\]

So the result does not depend on u anymore, allowing to calculate it by temporarily casting x, y and z to (signed long long) and using their sign.
We can express this as „use x_h \wedge y_h if z_h=1 and use x_h \vee y_h if z_h = 0„.

An incoming carry bit d does not change this, it just allows for x_l + y_l + d < 2^{64}, which is sufficient for making the previous calculations work.

In a similar way subtraction can be dealt with.

The basic operations add, adc, sub, sbb, mul, xdiv (div is not available) have been implemented in this library for C. Feel free to use it according to the license (GPL). Addition and subtraction could be implemented in a similar way in Java, with the weirdness of declaring signed longs and using them as unsigned. For multiplication and division, native code would be needed, because Java lacks 128bit-integers. So the C-implementation is cleaner.

Share Button

Kommentarfunktion

Die Kommentarfunktion geht bei jedem Upgrade von WordPress verloren.
Damit sie funktioniert, werden Schreibrechte im Verzeichnis
/wp-content/plugins/si-captcha-for-wordpress/captcha/cache
benötigt. Die muss man nach jedem Softwareupdate überprüfen.
Jetzt sollte die Kommentarfunktion wieder gehen.

Share Button

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

2015

Frohes neues Jahr!
Happy New Year
Gott nytt år!
Godt Nyttår!
¡Próspero año nuevo!
Bonne année!
FELIX SIT ANNUS NOVUS
Felice Anno Nuovo!
Весёлого нового года!
السنة الجديدة المبتهجة
Een gelukkig nieuwjaar!

Share Button

Weihnachten 2014

weihnachtsmarkt-berlin-20141214_192259Frohe Weihnachten!
Merry Christmas!
God Jul!
¡Feliz Navidad!
Joyeux Noël!
Natale hilare!
С Рождеством!
ميلاد مجيد
Buon Natale!
God Jul!
Prettige Kerstdagen!

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

English or German / Englisch oder Deutsch

Currently I am writing blog articles in German and translate them to English, if I consider them interesting for a wider audience. I am considering to do it the other way round and write articles in English and provide a German translation of some of them. I am creating a poll for this.
Find the poll in the upper left corner of the Start page.

Zur Zeit schreibe ich alles auf Deutsch und übersetze Artikel auf Englisch, wenn sie von allgemeinerem Interesse sind. Ich überlege, es umgekehrt zu machen und die Artikel ab 1. Januar 2015 auf Englisch zu schreiben und bei Interesse einzelne auf Deutsch zu übersetzen. Ich starte eine Umfrage dazu.
Die Umfrage steht in der linken oberen Ecke der Startseite.

Share Button