TU Wien:Mathematik 1 UE (diverse)/Übungen WS07/Beispiel 7

SS08 Beispiel 4

Nach der sogenannten "abessinischen Bauernmethode“ werden zwei Zahlen, z.B. 21 und 17, wie folgt multipliziert:

  21     17
  10     34
   5     68
   2    136
   1    272
------------
        357

Dabei wird der erste Faktor laufend durch 2 dividiert (und der Rest dabei vernachlässigt), während der zweite Faktor stets verdoppelt wird. Nach dem Motto der abessinischen Bauern "Gerade Zahlen bringen Unglück" streicht man nun alle Zeilen, in denen die Zahl in der ersten Spalte gerade ist. Die Summe der verbleibenden Zahlen in der zweiten Spalte liefert dann das Ergebnis $21\cdot 17=357$ .

Man begründe, warum diese Methode zum richtigen Resultat führt. (Hinweis: Man gehe von einer Darstellung des ersten Faktors im Binärsystem aus.)

Lösung[Bearbeiten | Quelltext bearbeiten]

Man gehe bei diesem Bsp. von den Binärwerten der beiden Faktoren aus. Diese wären also:

17=10001 und 21=10101

Nun multipliziert man diese beiden Binärzahlen (Binärzahlen-Multiplikation):

10001 * 10101
10001
 00000
  10001
   00000
    10001
101100101 = 357 = 21*17

Hier könnte man aber auch so vorgehen:

10101      10001        21  17
 1010     100010        10  34
  101    1000100         5  68
   10   10001000         2 136
    1  100010000         1 272

Nun lässt man alle Zeilen Weg, die an der 1er-Stelle der 1. Spalte binär eine 0 haben und summiert die 2. Spalte auf:

10101      10001        21  17
  101    1000100         5  68
    1  100010000         1 272

       101100101           357

Im Prinzip sind wir so vorgegangen wie bei der binären Multiplikation: Für jede Ziffer des 1. Faktors (bei uns 21) wurde eine entsprechende Zahl zum Endergebnis addiert, die wenn die Ziffer 0 war, auch dem Wert 0 entsprach, und wenn die Ziffer 1 war, der Zahl des 2. Faktors (bei uns 17) im binären System um soviele Stellen nach links verschoben, wie die Position der entsprechenden Ziffer im 1. Faktor war, entsprach.

Allgemeine Lösung[Bearbeiten | Quelltext bearbeiten]

$a\cdot b=\left(\sum _{i}a_{i}\cdot 2^{i}\right)\cdot b=\sum _{i}a_{i}\cdot \left(2^{i}\cdot b\right)$

Da $a_{i}\in \{0,1\}$ entspricht das dem Wegstreichen der jeweiligen Zeile.

wie man es vielleicht einfacher "sieht"[Bearbeiten | Quelltext bearbeiten]

Das Folgende ist nur die allg. Lösung auf das Beispiel aus der Angabe angewendet. Zumindest seh ich persönlich so einfacher was passiert:
Man zerlege den ersten Faktor in die 2er- Potenzen: $21=2^{4}\cdot 1+2^{3}\cdot 0+2^{2}\cdot 1+2^{1}\cdot 0+2^{0}\cdot 1$ Dadurch wird die Multiplikation zu folgendem:
$21\cdot 17=\left(2^{4}\cdot 1+2^{3}\cdot 0+2^{2}\cdot 1+2^{1}\cdot 0+2^{0}\cdot 1\right)\cdot 17$
$=2^{4}\cdot 17+2^{3}\cdot 0\cdot 17+2^{2}\cdot 17+2^{1}\cdot 0\cdot 17+2^{0}\cdot 17=272+68+17=357$
Man erkennt hier, das die Zeilen die die Bauern gestrichen haben immer den Zeilen entsprechen, wo die 2er- Potenz einen Faktor Null dabei stehen hat. D.h. die erste Spalte ist nichts anders als die Umrechnung in das Binärsystem. Alle anderen (ungestrichenen) Zeilen werden 17 mit $2^{n}$ multipliziert. Was der Grund ist, warum die Bauern den 2. Faktor immer mit 2 multipliziert haben