Bedeutung des Multiplikationsalgorithmus

Automatisierung des Rechnens

Das Rechnen mit Zahlen ist eine bedeutende Kulturleistung der Menschheit, die gewaltige Auswirkungen hat. Viele Bereiche unseres Lebens wären kaum noch oder gar nicht denkbar, wenn sie nicht von Zahlen und Berechnungen mit diesen Zahlen begleitet wären.

Schon sehr früh hat man versucht, das Rechnen mit Zahlen zu automatisieren. So sind z.B. unsere Verfahren zum schriftlichen Rechnen Verfahren, die man schematisch durchführen kann, ohne sie im geringsten Maße verstanden zu haben. Diese Form der Automatisierung ermöglicht es, sehr viele Berechnungen ohne Nachdenken schnell auszuführen.

Algorithmen wurden also schon entwickelt und benutzt, lange bevor es Computer gab. Zu diesen algorithmischen Verfahren gehört auch das von den Ägyptern benutzte Verfahren zur Multiplikation von Zahlen. Ohne algorithmische Rechenverfahren wäre es den Ägyptern wohl kaum möglich gewesen, eine funktionierende Gesellschaft aufzubauen, die sogar in der Lage war, riesige Pyramiden zu bauen.

Vom Multiplikations- zum Potenzierungsalgorithmus

Obwohl das Multiplikationsverfahren der Ägypter heute kaum noch benutzt wird, hat der Algorithmus und die dahinter steckende Idee nichts an ihrer Bedeutung verloren. Die Idee wird heute beim "schnellen Potenzieren" benutzt.

Aufgabe 1

In der freien Enzyklopädie Wikipedia findet man unter dem Stichwort schnelles Potenzieren die folgende Verfahrensbeschreibung:

Der Exponent wird schrittweise halbiert (das Ergebnis wird abgerundet) und die Basis schrittweise quadriert. Man streicht die Zeilen mit geradem Exponenten. Das Produkt der nichtgestrichenen rechten Zahlen ist die gesuchte Potenz.

  1. Teste erst einmal dieses Verfahren zum schnellen Potenzieren.
    Hilfe: Klicke hier, um ein Beispiel zu sehen.
  2. Entwickle anschließend ein Struktogramm zur Beschreibung des Verfahrens. Du kannst dich am Algorithmus zur ägyptischen Multiplikation orientieren.
  3. Implementiere den Algorithmus als Funktion in Python.
  4. Erweitere deinen Algorithmus, so dass er auch die Anzahl der Multiplikationen mit ausgibt.
    Vergleiche mit der Anzahl bei "normalem" Potenzieren x·x·x·x... (hohe Exponenten!).
  5. Gib Testfälle an, mit denen du die Funktion prüfen kannst.
X

Fehler melden

X

Suche