Motivation SS12

Aus ProgrammingWiki
< AuK
Archivierte Version vom 2012-02-17T18:43:45+00:00. Aktuelle Version

Inhaltsverzeichnis

Algorithmen zur Multiplikation


Multiplikation großer Zahlen

Es gibt eine bessere Methode zur Multiplikation zweier natürlicher Zahlen als die, die in der Schule gelehrt wird.

Was bedeutet "besser" und warum ist das wichtig?

  • Ein besserer Multiplikationsalgorithmus benötigt weniger Zeit als andere Verfahren mit gleichem Resultat.
  • Dadurch können alle Operationen, die große ganze Zahlen multiplizieren, viel schnelle durchgeführt werden. Beispiele sind: Computeralgebrasysteme und Geometrieprogramme.
  • Konsequenzen hat das auch für die Kryptografie.

Primitive Basisoperationen

Wir gehen davon aus, dass die folgenden beiden Elementaroperationen vorhanden sind und für die entsprechenden Eingaben stets mit konstantem Zeitaufwand ausgeführt werden.

  1. Addition dreier Ziffern (sog. Volladdierer)
    Eingaben: x und y sowie der Übertrag c
    Resultat: zwei Ziffern, nämlich die Ergebnisziffer und der neue Übertrag
  2. Multiplikation zweier Ziffern
    Eingaben: x und y
    Resultat: zwei Ziffern, nämlich die Ergebisziffer und der Übertrag

Für die beiden Operationen wird im Folg. je eine Scheme-Prozedur prim-add und prim-mult definiert. In diesen Definition wird die Basis B der Zahlendarstellung durch den Wert der Variablen basis festgelegt. Die Voreinstellung ist B=10. Für den Fall, dass ein anderes Stellenwertsystem verwendet werden soll, ist diese Angabe anzupassen.

Die primitive Addition zweier Ziffern und eines Übertrags liefert ein Paar, dessen erstes Element die Einerstelle und das zweite den neuen Übertrag darstellt. Beispielsweise wird für 7+8+0=15 das Paar (5 . 1) zurück gegeben.







Ein weiteres Aufrufbeispiel gilt der Multiplikation 9\cdot 8=72:


Da die beiden primitiven Operationen mit komplexeren Scheme-Sprachelementen definiert wurden, macht es keinen Sinn, zur Aufwandsanalyse darauf aufbauender Operationen eine Zeitmessung durchzuführen. Sinnvoll ist es, die Gesamtanzahl der Aufrufe primitiver Basisperationen zu ermitteln. Hierfür wird eine globale Variable anzahl-prim-op als Zähler bereitgestellt und mit 0 initialisiert.
Hinweis
Es ist zu beachten, dass anzahl-prim-op bei jedem Prozeduraufruf mit 0 initialisiert wird.



Addition und Multiplikation n-stelliger natürlicher Zahlen


Die Stelligkeit n einer natürlichen Zahl ist eine Eigenschaft, die von deren Darstellung abhängt. Bereits in der Grundschule lernt man eine Methode zur Zahldarstellung durch die entsprechenden Ziffern in einem Stellenwert- oder Positionssystem mit einer gewählten Basis B. Typische Beispiele sind B=10 (Dezimalsystem), B=2 (Dualsystem) und B=16 (Hexadezimalsystem).
Die allgemeine Darstellung ist:
a_{n-1}a_{n-2}\ldots a_1 a_0 = \sum_{i=0}^{n-1} a_i \cdot B^i, \text{ mit } n\in\mathbb{N}, n>0, \text{ und } a_i\in\{0,1,\ldots,B-1\}

Für B=2 gilt a_i\in\{0,1\}.
Für B=10 gilt a_i\in\{0,1,2,3,4,5,6,7,8,9\}.
Für B=16 gilt a_i\in\{0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F\}.
Mit zwei Ziffern können alle Zahlen aus dem Intervall [0,B^2-1] dargestellt werden, denn (B-1)\cdot B^1+(B-1)\cdot B^0=(B+1)\cdot (B-1)= B^2-1.
Wir führen nun die Addition und Multiplikation n-stelliger Zahlen auf diese primitiven Operationen zurück.
Addition zweier n-stelliger natürlicher Zahlen
Beispiel: n=7
Typische Handrechnung      Ausführlich: mit Übertrag
      1827634  a                 1827634  a
      8294678  b                 8294678  b
     --------                   11111110  c   Übertrag
     10122312  s                --------  
                                10122312  s
Jetzt ist klar, weshalb die primitive Addition für zwei Ziffern und eine Übertragsziffer ausgelegt wurde. Für die Addition a_i+b_i+c_i=s_i ergibt sich ein Übertrag c_{i+1}=1, wenn s_i\geq B, ansonsten ist c_{i+1}=0. Nehmen wir die größtmöglichen Summanden B-1 und B-1, gilt a_i+b_i-B=(B-1)+(B-1)-B=B-2, was offensichtlich mit einer Ziffer aus [0,B-1] darstellbar ist.
Die Operation add kann nun angewandt werden, um die obige simple Beispielrechnung auszuführen. Die Ziffern finden sich als Elemente einer Liste wieder:


Für die Addition zweier n-stelliger Zahlen werden n Elementaradditionen benötigt. Auch dies gilt für das Beispiel.


ÜA: Modifizieren Sie das Beispiel und evaluieren Sie die zugehörigen Additionen usw.
Multiplikation einer n-stelligen natürlichen Zahl mit einer einstelligen
Für die Multiplikation zweier n-stelliger natürlicher Zahlen benötigen wir einen Zwischenschritt, um die primitive Addition geeignet einzubeziehen. Wir betrachten zunächst die Multiplikation einer n-stelligen natürlichen Zahl mit einer einstelligen.
Beispiel: n=5
    25367 * 5
    ---------
    005505   links mit Null aufgefüllt, Primitivaddition zu ermöglichen
 +  121330   Übertrag, rechts mit Null aufgefüllt 
    ------
    126835   durch Elementaraddition gewonnen

Der Übertrag c_{i+1} kann hier größer ausfallen als bei der Addition. Offenbar gilt: 

z = a_i\cdot b_j \leq (B-1)^2 = B^2 - 2B +1 

z = c_{i+1}\cdot B + d_i \leq (B-2)\cdot B + 1

Der Kooeffizientenvergleich liefert c_{i+1}\leq B-2, d.h. 0\leq c_{i+1}\leq B-2. (Natürlich gilt c_0=0.)
Das obige Ergebnis für die Beispielrechnung erhalten wir auch mit der vorbereiteten Operation mult1. mult1 nimmt eine Liste mit den Ziffern des ersten Faktors a=a_{n-1}a_{n-2}\ldots a_1 a_0 und eine Ziffer b_j als zweiten Faktor und liefert das Produkt a\cdot b_j.   


Auch hierfür können wir die Zahl der Elementaroperationen (prim-add und prim-mult) bestimmen:


Wir rechnen nach:
  • n Elementarmultiplikationen
  • n+1 Elementaradditionen
Zusammen sind das 2n+1 primitive Basisoperationen, für n=5 sind das gerade 11 Stück.
Multiplikation zweier n-stelliger natürlicher Zahlen
Nun folgt der Übergang zur vollen Multiplikation. Wir erinnern uns an die Schulbuchmethode zur schriftlichen Multiplikation. Aufgrund des Taschenrechnereinsatzes wird sie nur noch selten ausgeführt.
Beispiel: n=4
  8643 * 9915
  -----------
   77787000   = mult1(8643,9) und rechts mit Nullen aufgefüllt  
   07778700   = mult1(8643,9) und links/rechts mit Nullen aufgefüllt
   00086430   = mult1(8643,1) und links/rechts mit Nullen aufgefüllt
   00043215   = mult1(8643,5) und links mit Nullen aufgefüllt
   -------- 
   85695345   = add(add(add(77787000,07778700),00086430),00043215) = mult(8643,9915)
Wir rechnen nach:


Natürlich interessieren wir uns für die Anzahl der primitiven Basisoperationen:
Die Multiplikation zweier n-stelliger natürlicher Zahlen nach der im Beispiel angewandten Methode führt zu n Summanden. Jeder Summand entsteht als Teilprodukt und erfordert - wie wir weiter oben gezeigt haben - 2n+1 Basisoperationen. Das ergibt für alle Summanden n\cdot (2n+1) = 2n^2+n Elementaroperationen.
Die n Summanden sind jeweils höchstens 2n-stellig, denn der erste Summand ist ohne Auffüllnullen höchstens n+1-stellig. (Im Beispiel ist das der Fall.) Dann folgen n-1 weitere Summanden und folglich ebenso viele Rechtsverrückungen um eine Stelle. Das ergibt zusammen: n+1+n-1=2n. Die Auffüllung mit Nullen ist notwendig, um die Summanden gleichstellig zu machen. 
Die n-1 Additionen je eines höchstens 2n-stelligen Summandens mit der jeweils aktuellen höchstens 2n-stelligen Zwischensumme erfordert (n-1)\cdot 2n = 2n^2-2n Elementaroperationen. 
Insgesamt bescheinigt diese Abschätzung der Schulbuch-Multiplikationsmethode für n-stellige Faktoren einen Aufwand von 2n^2+n + 2n^2-2n = 4n^2-n primitiven Basisoperationen.
Für unser Beispiel ergibt sich:


ÜA: Verwenden Sie die Prozedur zufallsliste zur Erzeugung von Zufallsfaktoren für die Multiplikation n-stelliger natürlicher Zahlen mittels mult> und ermitteln Sie den zugehörigen Berechnungsaufwand (Anzahl der primitiven Basisoperationen). Prüfen Sie die Übereinstimmung mit 4n^2-n.






Datenübergabe von Scheme an gnuplot klären.
Gnuplot-Diagramm