Schnelle Multiplikation

Verfasst von F. Mäser

Inhalt	Schnelle Multiplikation - Verfahren von Karatsuba
Schultyp	Gymnasium, technische Berufsschule, Fachhochschule
Voraussetzung	Elementare Programmierkenntnisse, Exponentialfunktion und Logarithmen
Zeitbedarf	45-60 Minuten

Worum geht es?

Wie schnell können zwei n-stellige Zahlen miteinander multipliziert werden? Die Schulmethode benötigt dafür n^2 einstellige Multiplikationen und einige Additionen. 1962 entwickelte Karatsuba ein Verfahren, das nur O(n^1.59) einstellige Multiplikationen benötigt. Der Posten erklärt Karatsubas Verfahren und die ihm zugrunde liegende Programmiertechnik des "Divide and Conquer". Die Schülerinnen und Schüler studieren zuerst die Theorie. Dann lösen sie ein einfaches Beispiel "von Hand". Schliesslich "messen" sie die Effizienz des Algorithmus, indem sie mit einem Computer oder programmierbaren Taschenrechner O(n^2) und O(n^1.59) vergleichen. Grundoperationen wie die Multiplikation zweier Zahlen werden in einem Computerprogramm zu Tausenden ausgeführt. Es ist deshalb wichtig, dass solche Operationen effizient implementiert werden. Nach Bearbeiten des Postens kennen die Schülerinnen und Schüler das Verfahren von Karatsuba für die Multiplikation von zwei n-stelligen Zahlen. Sie können das Verfahren an einfachen Beispielen selbst "von Hand" anwenden. Sie können auch darlegen, weshalb es der Schulmethode vom Aufwand her überlegen ist. Ausserdem lernen sie die Programmiertechnik "Divide and Conquer" kennen. Sie können erklären, wie diese Technik funktioniert, und bei welchen Problemen sie angewandt werden kann.

Downloads

Werkstattposten

PDF [52 KB] · Word [202 KB]