Horner-Schema

Das Horner-Schema ist eine Methode, um große Zahlen aus einem beliebigen Zahlsystem ins Dezimalsystem und umgekehrt umzurechnen.

Im Folgenden wird die ganze Zeit mit dem Binärsystem gerechnet. Wenn man andere Multiplikatoren bzw. Divisoren als $2$ verwendet, funktioniert dieses Schema aber für jedes andere beliebige Zahlsystem.

Umrechnung ins Dezimalsystem

Motivation

Intuitiv würde man eine Binärzahl wie $10111110001011100011110010010101$ so ins Dezimalsystem umrechnen:

${\begin{aligned}&\quad \;10111110001011100011110010010101\\&=1\cdot 2^{31}+0\cdot 2^{30}+1\cdot 2^{29}+1\cdot 2^{28}+\cdots +1\cdot 2^{0}\\&=1\cdot 2147483648+0\cdot 1073741824+1\cdot 536870912+1\cdot 268435456+\cdots +1\cdot 1\\&=3190701205\\\end{aligned}}$

Wie unschwer zu erkennen ist, werden hier ziemlich große Zahlen jongliert. Beim Versuch, diese Summe mit Zettel und Papier oder mit einem einfachen Taschenrechner auszurechnen, wird man unweigerlich kleine Fehler machen, die das Ergebnis grob verfälschen können.

Stattdessen kann aber auch das Horner-Schema angewendet werden. Das Horner-Schema ist eine einfache Möglichkeit, mit wenigen überschaubaren Schritten zwischen zwei Zahlsyst

Idee

Die Idee ist, die Zahl von der größten bis zur kleinsten Stelle sozusagen stellenweise aufzudecken. Nehmen wir als Beispiel die Zahl $1000101$:

Schritt 1: Wir betrachten die erste Ziffer: $1$. $1$ ist $1$. Mit der $1$ rechnen wir weiter.

Schritt 2: Wir nehmen die nächste Ziffer dazu: $10\Longrightarrow 1\cdot 2+0=2$. Mit der $2$ rechnen wir weiter.

Schritt 3: Wir nehmen die nächste Ziffer dazu: $100\Longrightarrow 2\cdot 2+0=4$. Mit der 4 rechnen wir weiter.

Schritt 4: Wir nehmen die nächste Ziffer dazu: $1000\Longrightarrow 4\cdot 2+0=8$. Mit der $8$ rechnen wir weiter.

Schritt 5: Wir nehmen die nächste Ziffer dazu: $10001\Longrightarrow 8\cdot 2+1=17$. Mit der 17 rechnen wir weiter.

Schritt 6: Wir nehmen die nächste Ziffer dazu: $100010\Longrightarrow 17\cdot 2+0=34$. Mit der 34 rechnen wir weiter.

Schritt 7: Wir nehmen die nächste (und letzte) Ziffer dazu: $1000101\Longrightarrow 34\cdot 2+1=69$. Damit haben wir unser Ergebnis: die binäre $1000101$ entspricht der dezimalen $69$.

Mathematischer Hintergrund

Der mathematische Hintergrund ist, große komplizierte Summen wie $1\cdot 2^{5}+1\cdot 2^{4}+1\cdot 2^{3}+1\cdot 2^{2}+1\cdot 2^{1}+1\cdot 2^{0}$ schrittweise nach dem Distributivgesetz auszuklammern und so in eine Reihe von kleineren Multiplikationen zu überführen.

${\begin{aligned}&\quad \;1\cdot 2^{5}+1\cdot 2^{4}+1\cdot 2^{3}+1\cdot 2^{2}+1\cdot 2^{1}+1\cdot 2^{0}\\&=\underbrace {1\cdot 2\cdot 2\cdot 2\cdot 2\cdot 2+1\cdot 2\cdot 2\cdot 2\cdot 2+1\cdot 2\cdot 2\cdot 2+1\cdot 2\cdot 2+1\cdot 2} _{\text{haben alle 2 als Faktor; 2 wird ausgeklammert}}+1\\&=(\underbrace {1\cdot 2\cdot 2\cdot 2\cdot 2+1\cdot 2\cdot 2\cdot 2+1\cdot 2\cdot 2+1\cdot 2} _{\text{haben alle 2 als Faktor; 2 wird ausgeklammert}}+1)\cdot 2+1\\&=((\underbrace {1\cdot 2\cdot 2\cdot 2+1\cdot 2\cdot 2+1\cdot 2} _{\text{2 wird ausgeklammert}}+1)\cdot 2+1)\cdot 2+1\\&=(((\underbrace {1\cdot 2\cdot 2+1\cdot 2} _{\text{2 wird ausgeklammert}}+1)\cdot 2+1)\cdot 2+1)\cdot 2+1\\&=((((1\cdot 2+1)\cdot 2+1)\cdot 2+1)\cdot 2+1)\cdot 2+1\\\end{aligned}}$

Das sieht jetzt vielleicht eher noch komplizierter aus als vorher, lässt sich aber wesentlich einfacher in den Taschenrechner eintippen: öffnende Klammern ignoriert man und bei einer schließenden Klammer drückt man auf =.

$1\cdot 2+1$

=

3

$\hookrightarrow$

$\cdot 2+1$

=

7

$\hookrightarrow$

$\cdot 2+1$

=

15

$\hookrightarrow$

$\cdot 2+1$

=

31

$\hookrightarrow$

$\cdot 2+1$

=

63

Umrechnung aus dem Dezimalsystem

Motivation

Naiv würde man eine große Dezimalzahl wie $12345$ folgendermaßen angehen: man sucht sich die größte Zweierpotenz, die noch in die $12345$ hineinpasst, das wäre $8192=2^{13}$. Dann bleiben noch $12345-8192=4153$ übrig, die umzurechnen wären. Und wieder sucht man die nächstgrößere Zweierpotenz und findet $2^{12}=4096$, bleiben noch $4153-4096=57$ übrig. Als nächstes findet man $2^{5}=32$, bleiben $57-32=25$ übrig. Als letztes findet man dann $25=16+8+1=2^{4}+2^{3}+2^{0}$. Damit bleibt als binäre Repräsentation $11000000111001$.

Idee

Was man jeder Dezimalzahl sofort ansieht, ist die letzte Ziffer ihrer binären Repräsentation. Diese ist nämlich $0$ für gerade und $1$ für ungerade Zahlen. Und alle führenden Ziffern entsprechen der abgerundeten Hälfte der ursprünglichen Zahl. Die Zahl $1000101=69$ endet mit einer $1$, d.h. sie ist ungerade, und beginnt mit den Ziffern ${\textstyle 100010=34=\lfloor {\frac {69}{2}}\rfloor }$.

Dahinter steckt die Tatsache, dass $\underbrace {100010} _{=34}\underbrace {1} _{=1}=34\cdot 2+1=69$.

Und für die 34 gilt genau so $\underbrace {10001} _{=17}\underbrace {0} _{=0}=17\cdot 2+0=34$.

Indem man nun die Ausgangszahl immer wieder mit Rest durch $2$ teilt und diese Reste dann rückwärts liest, erhält man die binäre Repräsentation der Zahl.

${\begin{aligned}123:2&=61&{\textrm {Rest}}~1\\61:2&=30&{\textrm {Rest}}~1\\30:2&=15&{\textrm {Rest}}~0\\15:2&=7&{\textrm {Rest}}~1\\7:2&=3&{\textrm {Rest}}~1\\3:2&=1&{\textrm {Rest}}~1\\1:2&=0&{\textrm {Rest}}~1\\\end{aligned}}$

Die binäre Repräsentation der Zahl ergibt sich aus den Resten, von oben nach unten: $123=1111011$.

Beispiele

Im folgenden sind einige Beispiele für die Umrechnung von Zahlen mit dem Horner-Schema angegeben. Die Summanden auf der rechten Seite jeder Gleichung sind farblich hervorgehoben, ebenso die dazugehörigen Ziffern auf der linken Seite jeder Gleichung in derselben Farbe.

$${\begin{aligned}{\textrm {1}}&=\color {blue}{1}\\{\color {blue}{\textrm {1}}}{\color {orange}{\textrm {0}}}&={\color {blue}{1}}\cdot 2+{\color {orange}{0}}={\color {green}{2}}\\{\color {green}{\textrm {10}}}{\color {red}{\textrm {1}}}&={\color {green}{2}}\cdot 2+{\color {red}{1}}={\color {purple}{5}}\\{\color {purple}{\textrm {101}}}{\color {royalblue}{\textrm {0}}}&={\color {purple}{\textrm {5}}}\cdot 2+{\color {royalblue}{0}}={\color {gray}{10}}\\{\color {gray}{\textrm {1010}}}{\color {orchid}{\textrm {1}}}&={\color {gray}{\textrm {10}}}\cdot 2+{\color {orchid}{1}}={\color {brown}{21}}\\{\color {brown}{\textrm {10101}}}{\color {seagreen}{\textrm {0}}}&={\color {brown}{\textrm {21}}}\cdot 2+{\color {seagreen}{0}}=42\end{aligned}}$$

Horner-Schema/Beispiele/Hexadezimal nach Dezimal

Horner-Schema/Beispiele/Dezimal nach binär

Horner-Schema/Beispiele/Dezimal nach hexadezimal