Quelltext der Seite 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 <math>2</math> verwendet, funktioniert dieses Schema aber für jedes andere beliebige Zahlsystem.

== Umrechnung ins Dezimalsystem ==

=== Motivation ===
Intuitiv würde man eine Binärzahl wie <math>10111110001011100011110010010101</math> so ins Dezimalsystem umrechnen:

<math>\begin{align}
&\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{align}
</math>

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 <math>1000101</math>:

'''Schritt 1:''' Wir betrachten die erste Ziffer: <math>1</math>. <math>1</math> ist <math>1</math>. Mit der <math>1</math> rechnen wir weiter.

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

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

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

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

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

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

=== Mathematischer Hintergrund ===
Der mathematische Hintergrund ist, große komplizierte Summen wie <math>1 \cdot 2^5 + 1 \cdot 2^4 + 1 \cdot 2^3 + 1 \cdot 2^2 + 1 \cdot 2^1 + 1 \cdot 2^0</math> schrittweise nach dem [[Distributivgesetz]] auszuklammern und so in eine Reihe von kleineren Multiplikationen zu überführen.

<math>\begin{align}
&\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{align}
</math>

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 <code>=</code>.
{|
|<math>1 \cdot 2 + 1</math>
|<code>=</code>
|3
|
|
|
|
|
|
|
|
|
|
|
|
|-
|
|
|<math>\hookrightarrow</math>
|<math>\cdot 2 + 1</math>
|<code>=</code>
|7
|
|
|
|
|
|
|
|
|
|-
|
|
|
|
|
|<math>\hookrightarrow</math>
|<math>\cdot 2 + 1</math>
|<code>=</code>
|15
|
|
|
|
|
|
|-
|
|
|
|
|
|
|
|
|<math>\hookrightarrow</math>
|<math>\cdot 2 + 1</math>
|<code>=</code>
|31
|
|
|
|-
|
|
|
|
|
|
|
|
|
|
|
|<math>\hookrightarrow</math>
|<math>\cdot 2 + 1</math>
|<code>=</code>
|63
|}

== Umrechnung aus dem Dezimalsystem ==

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

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

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

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

Indem man nun die Ausgangszahl immer wieder [[Division mit Rest|mit Rest durch <math>2</math> teilt]] und diese Reste dann rückwärts liest, erhält man die binäre Repräsentation der Zahl.

<math>\begin{align}
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{align}</math>

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

{{:Horner-Schema/Beispiele}}

[[Kategorie:Zahlsystem]]