www.wikidata.de-de.nina.az

Russische Bauernmultiplikation Die auch Ägyptisches Multiplizieren Abessinische Bauernregel oder Verdopplungs Halbierung

Russische Bauernmultiplikation

Die Russische Bauernmultiplikation (auch Ägyptisches Multiplizieren, Abessinische Bauernregel oder Verdopplungs-Halbierungs-Methode genannt) ist ein einfaches Verfahren zur Multiplikation zweier natürlicher Zahlen. Schon im Altertum bekannt, war das Verfahren in Deutschland bis ins Mittelalter und in Russland bis weit in die Neuzeit üblich, woher auch der Name rührt.

Es ist gesichert, dass die Ägypter bereits eine analoge Methode zur Multiplikation verwendeten. Der Algorithmus ist auf dem Papyrus Rhind beschrieben.

Das Verfahren hat den Vorteil, dass man im Prinzip nur halbieren, verdoppeln und addieren können muss, das kleine Einmaleins wird nicht benötigt. Implizit wird eine schriftliche Multiplikation im Binärsystem durchgeführt.

Verfahren Bearbeiten

Beschreibung Bearbeiten

Das Verfahren besteht aus folgenden Schritten:

  1. Man schreibt die beiden zu multiplizierenden Zahlen nebeneinander.
  2. Auf der linken Seite (Multiplikator) werden die Zahlen jeweils halbiert (Reste abgerundet) und die Ergebnisse untereinander geschrieben, bis man zur 1 gelangt.
  3. Auf der rechten Seite (Multiplikand) werden die Zahlen verdoppelt und untereinander geschrieben.
  4. Die rechts stehenden (verdoppelten) Zahlen werden gestrichen, wenn die links stehende Zahl gerade ist.
  5. Die Summe der nicht gestrichenen rechts stehenden Zahlen ergibt das gesuchte Produkt.

Die Korrektheit der russischen Multiplikation kann durch vollständige Induktion bewiesen werden.

Beispiel Bearbeiten

Das Produkt aus 27 und 82 wird folgendermaßen errechnet:

Multiplikator Multiplikand zu addieren Multiplikator binär Multiplikand binär zu addieren
27  82  82  11011 1010010  1010010 
13  164  164  1101 10100100  10100100 
6  328  ---  110 101001000  ---
3  656  656  11 1010010000  1010010000 
1  1312  1312  1 10100100000  10100100000 
Produkt:  2214  Produkt binär:  100010100110 

Erklärung Bearbeiten

Die russische Bauernmultiplikation kann durch Zerlegung des Multiplikators in Zweierpotenzen nachvollzogen werden:

Die Summanden, die den Faktor Null enthalten, entsprechen den Zeilen, die gestrichen werden.

In der binären Repräsentation erkennt man eine gerade Zahl an der 0 an der rechten Stelle – dem niederwertigsten Bit.

Bemerkungen Bearbeiten

Es lassen sich mit diesem Verfahren auch Produkte von rationalen Zahlen berechnen. Auch dies war den Ägyptern bereits bekannt.

Um die Anzahl der Divisionsschritte zu minimieren, bietet es sich an, die Faktoren gegebenenfalls zu vertauschen.

Um die Anzahl der Additionsschritte zu minimieren, bietet es sich an, die Zahlen so zu vertauschen, dass der gerade Faktor halbiert wird.

Nutzung auf frühen Computersystemen Bearbeiten

Frühe CPUs konnten auf ihrer Arithmetisch-logischen Einheit nur einfache Operationen wie Addition und Subtraktion ausführen, normalerweise aber keine Multiplikation. Da sich der Algorithmus der sog. „Bauernmultiplikation“ durch Additionen und einfache Bitweise Verschiebungen und Bit-Tests in einer kleinen Schleife abbilden lässt, wurde sie häufig für ad-hoc Multiplikationen verwendet.

Analoges Verfahren: Binäre Exponentiation Bearbeiten

Dieselbe Idee kann auch benutzt werden, um Potenzen mit großen ganzzahligen Exponenten zu berechnen: Der Exponent wird schrittweise halbiert und die Basis quadriert, am Ende werden die Potenzen mit ungeraden Exponenten aufmultipliziert. Dieses Verfahren heißt binäre Exponentiation.

Siehe auch Bearbeiten

Literatur Bearbeiten

  • Otto Forster: Die russische Bauernregel der Multiplikation. In: Otto Forster: Algorithmische Zahlentheorie (= Lehrbuch.). 2., überarbeitete und erweiterte Auflage. Springer Spektrum, Wiesbaden 2015, ISBN 978-3-658-06539-3, S. 12–13.
  • Jens Gallenbacher: Die Äthiopische Multiplikation. In: Jens Gallenbacher: Abenteuer Informatik. IT zum Anfassen für alle von 9 bis 99 – vom Navi bis Social Media. 4. Auflage. Springer, Berlin u. a. 2015, ISBN 978-3-662-53964-4, S. 123–127.

Weblinks Bearbeiten

Einzelnachweise Bearbeiten

  1. Hans Wußing: 6000 Jahre Mathematik. Eine kulturgeschichtliche Zeitreise. Band 1: Von den Anfängen bis Leibniz und Newton. Springer, Berlin u. a. 2008, ISBN 978-3-540-77189-0, S. 116.
  2. James R. Newman (Hrsg.): The World of Mathematics. Band 1. Simon & Schuster, New York NY 1956, S. 170.
  3. James R. Newman (Hrsg.): The World of Mathematics. Band 1. Simon & Schuster, New York NY 1956, S. 173.
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Die Russische Bauernmultiplikation auch Agyptisches Multiplizieren Abessinische Bauernregel oder Verdopplungs Halbierungs Methode genannt ist ein einfaches Verfahren zur Multiplikation zweier naturlicher Zahlen Schon im Altertum bekannt war das Verfahren in Deutschland bis ins Mittelalter und in Russland bis weit in die Neuzeit ublich woher auch der Name ruhrt Es ist gesichert dass die Agypter bereits eine analoge Methode zur Multiplikation verwendeten 1 Der Algorithmus ist auf dem Papyrus Rhind beschrieben 2 Das Verfahren hat den Vorteil dass man im Prinzip nur halbieren verdoppeln und addieren konnen muss das kleine Einmaleins wird nicht benotigt Implizit wird eine schriftliche Multiplikation im Binarsystem durchgefuhrt Inhaltsverzeichnis 1 Verfahren 1 1 Beschreibung 1 2 Beispiel 1 3 Erklarung 1 4 Bemerkungen 2 Nutzung auf fruhen Computersystemen 3 Analoges Verfahren Binare Exponentiation 4 Siehe auch 5 Literatur 6 Weblinks 7 EinzelnachweiseVerfahren BearbeitenBeschreibung Bearbeiten Das Verfahren besteht aus folgenden Schritten Man schreibt die beiden zu multiplizierenden Zahlen nebeneinander Auf der linken Seite Multiplikator werden die Zahlen jeweils halbiert Reste abgerundet und die Ergebnisse untereinander geschrieben bis man zur 1 gelangt Auf der rechten Seite Multiplikand werden die Zahlen verdoppelt und untereinander geschrieben Die rechts stehenden verdoppelten Zahlen werden gestrichen wenn die links stehende Zahl gerade ist Die Summe der nicht gestrichenen rechts stehenden Zahlen ergibt das gesuchte Produkt Die Korrektheit der russischen Multiplikation kann durch vollstandige Induktion bewiesen werden Beispiel Bearbeiten Das Produkt aus 27 und 82 wird folgendermassen errechnet Multiplikator Multiplikand zu addieren Multiplikator binar Multiplikand binar zu addieren27 82 82 11011 1010010 1010010 13 164 164 1101 10100100 10100100 6 328 110 101001000 3 656 656 11 1010010000 1010010000 1 1312 1312 1 10100100000 10100100000 Produkt 2214 Produkt binar 100010100110 Erklarung Bearbeiten Die russische Bauernmultiplikation kann durch Zerlegung des Multiplikators in Zweierpotenzen nachvollzogen werden 82 27 82 2 0 2 1 0 2 2 2 3 2 4 82 2 0 82 2 1 82 0 82 2 3 82 2 4 82 164 0 656 1312 2214 displaystyle begin matrix 82 times 27 amp amp 82 times 2 0 2 1 0 times 2 2 2 3 2 4 amp amp 82 times 2 0 82 times 2 1 82 times 0 82 times 2 3 82 times 2 4 amp amp 82 164 0 656 1312 amp amp 2214 end matrix nbsp Die Summanden die den Faktor Null enthalten entsprechen den Zeilen die gestrichen werden In der binaren Reprasentation erkennt man eine gerade Zahl an der 0 an der rechten Stelle dem niederwertigsten Bit Bemerkungen Bearbeiten Es lassen sich mit diesem Verfahren auch Produkte von rationalen Zahlen berechnen Auch dies war den Agyptern bereits bekannt 3 Um die Anzahl der Divisionsschritte zu minimieren bietet es sich an die Faktoren gegebenenfalls zu vertauschen Um die Anzahl der Additionsschritte zu minimieren bietet es sich an die Zahlen so zu vertauschen dass der gerade Faktor halbiert wird Nutzung auf fruhen Computersystemen BearbeitenFruhe CPUs konnten auf ihrer Arithmetisch logischen Einheit nur einfache Operationen wie Addition und Subtraktion ausfuhren normalerweise aber keine Multiplikation Da sich der Algorithmus der sog Bauernmultiplikation durch Additionen und einfache Bitweise Verschiebungen und Bit Tests in einer kleinen Schleife abbilden lasst wurde sie haufig fur ad hoc Multiplikationen verwendet Analoges Verfahren Binare Exponentiation BearbeitenDieselbe Idee kann auch benutzt werden um Potenzen mit grossen ganzzahligen Exponenten zu berechnen Der Exponent wird schrittweise halbiert und die Basis quadriert am Ende werden die Potenzen mit ungeraden Exponenten aufmultipliziert Dieses Verfahren heisst binare Exponentiation Siehe auch BearbeitenDuplationLiteratur BearbeitenOtto Forster Die russische Bauernregel der Multiplikation In Otto Forster Algorithmische Zahlentheorie Lehrbuch 2 uberarbeitete und erweiterte Auflage Springer Spektrum Wiesbaden 2015 ISBN 978 3 658 06539 3 S 12 13 Jens Gallenbacher Die Athiopische Multiplikation In Jens Gallenbacher Abenteuer Informatik IT zum Anfassen fur alle von 9 bis 99 vom Navi bis Social Media 4 Auflage Springer Berlin u a 2015 ISBN 978 3 662 53964 4 S 123 127 Weblinks BearbeitenEric W Weisstein Russian Multiplication In MathWorld englisch und in WolframDemonstrationsProject engl Einzelnachweise Bearbeiten Hans Wussing 6000 Jahre Mathematik Eine kulturgeschichtliche Zeitreise Band 1 Von den Anfangen bis Leibniz und Newton Springer Berlin u a 2008 ISBN 978 3 540 77189 0 S 116 James R Newman Hrsg The World of Mathematics Band 1 Simon amp Schuster New York NY 1956 S 170 James R Newman Hrsg The World of Mathematics Band 1 Simon amp Schuster New York NY 1956 S 173 Abgerufen von https de wikipedia org w index php title Russische Bauernmultiplikation amp oldid 217920577