Horner-Schema

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

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.

Erklärung

Die Idee dahinter 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 alls vorhher, 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

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