AuK/Motivation SS12

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
== 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.

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

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

<code id="4f2e6547da2f9">
(define anzahl-prim-op 0)

(define prim-add
  (let ((basis 10))  ; B = 10
    (lambda (x y c)
      (set! anzahl-prim-op (+ anzahl-prim-op 1))
      (let ((res (+ x y c)))
        (if (< res basis)
            (cons res 0)
            (cons (- res basis) 1))))))

(define prim-mult
  (let ((basis 10))  ; B = 10
    (lambda (x y)
      (set! anzahl-prim-op (+ anzahl-prim-op 1))
      (let ((res (* x y)))
        (cons (remainder res basis)(quotient res basis))))))
</code>

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 <math>7+8+0=15</math>
das Paar <tt>(5 . 1)</tt> zurück gegeben.
<run id="4f2e6547da47c">(prim-add 7 8 0)</run>
<run id="4f2e6547da4d3">(prim-add 2 5 1)</run>
<run id="4f2e6547da53d">(prim-add 9 8 1)</run>

Ein weiteres Aufrufbeispiel gilt der Multiplikation <math>9\cdot 8=72</math>:
<run id="4f2ec22340228">(prim-mult 9 8)</run>

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 <tt>anzahl-prim-op</tt> als Zähler bereitgestellt und mit 0 initialisiert.
<popup name="Hinweis"> Es ist zu beachten, dass <tt>anzahl-prim-op</tt> ''bei jedem'' Prozeduraufruf mit <tt>0</tt> initialisiert wird.</popup>


=== Addition und Multiplikation n-stelliger natürlicher Zahlen ===

<code id="4f32729c5ab7c" hidden>
(define add
  (lambda (a b)
    (letrec
        ((helper
          (lambda (a b c)
            (if (null? a) 
                (list c)
                (let ((res (prim-add (car a) (car b) c)))
                  (cons (car res) (helper (cdr a) (cdr b) (cdr res))))))))
      (reverse (helper (reverse a)(reverse b) 0)))))

(define mult1
  (lambda (a bj)  ; Liste, Ziffer
    (let ((res (map (lambda (ai) (prim-mult ai bj)) a)))
      (add
       (append '(0) (map car res))
       (append (map cdr res) '(0))))))

(define mult
  (lambda (a b)
    (let* ((lls (map (lambda (bj) (mult1 a bj)) b))
           (n (- (length lls) 1)))  ; Laenge der Faktoren = Anzahl der Summanden
      (letrec ((helfer 
                (lambda (lls k)
                  (if (null? lls)
                      '()
                      (cons (append (NullenListe (- n k)) (car lls) (NullenListe k)) 
                            (helfer (cdr lls) (- k 1))))))
               (hilfsadd
                (lambda (lls)
                  (if (null? (cdr lls))
                      (car lls)
                      (add (car lls) (hilfsadd (cdr lls)))))))
        (hilfsadd (helfer lls n))))))

; ---  Hilfsprozeduren ---

(define NullenListe
  (lambda (n)
    (map (lambda (str) (string->number (string str))) (string->list (make-string n #\0)))))

(define zahl->liste
  (lambda (zahl)
    (map (lambda (z) (string->number (string z))) (string->list (number->string zahl)))))
</code>

Die Stelligkeit <math>n</math> 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 <math>B</math>. Typische Beispiele sind <math>B=10</math> (Dezimalsystem), <math>B=2</math> (Dualsystem) und <math>B=16</math> (Hexadezimalsystem).

Die allgemeine Darstellung ist:
<math>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\}</math>

Für <math>B=2</math> gilt <math>a_i\in\{0,1\}</math>.
Für <math>B=10</math> gilt <math>a_i\in\{0,1,2,3,4,5,6,7,8,9\}</math>.
Für <math>B=16</math> gilt <math>a_i\in\{0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F\}</math>.

Mit zwei Ziffern können alle Zahlen aus dem Intervall <math>[0,B^2-1]</math> dargestellt werden, denn <math>(B-1)\cdot B^1+(B-1)\cdot B^0=(B+1)\cdot (B-1)= B^2-1</math>.

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 <math>a_i+b_i+c_i=s_i</math> ergibt sich ein Übertrag <math>c_{i+1}=1</math>, wenn <math>s_i\geq B</math>, ansonsten ist <math>c_{i+1}=0</math>. Nehmen wir die größtmöglichen Summanden <math>B-1</math> und <math>B-1</math>, gilt <math>a_i+b_i-B=(B-1)+(B-1)-B=B-2</math>, was offensichtlich mit einer Ziffer aus <math>[0,B-1]</math> darstellbar ist.

Die Operation <tt>add</tt> kann nun angewandt werden, um die obige simple Beispielrechnung auszuführen. Die Ziffern finden sich als Elemente einer Liste wieder:

<run id="4f327428d1a7b">(add '(1 8 2 7 6 3 4) '(8 2 9 4 6 7 8))</run>

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

<run id="4f3e4b209a5ca">
(add '(1 8 2 7 6 3 4) '(8 2 9 4 6 7 8))
anzahl-prim-op
</run>

Ü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 <math>c_{i+1}</math> kann hier größer ausfallen als bei der Addition. Offenbar gilt: <br/>
<math>z = a_i\cdot b_j \leq (B-1)^2 = B^2 - 2B +1 </math><br/>
<math>z = c_i\cdot B + d_i \leq (B-2)B + 1</math><br/>
Der Kooeffizientenvergleich liefert <math>c_i\leq B-2</math>, d.h. <math>0\leq c_i\leq B-2</math>.

Das obige Ergebnis für die Beispielrechnung erhalten wir auch mit der vorbereiteten Operation <tt>mult1</tt>. <tt>mult1</tt> nimmt eine Liste mit den Ziffern des ersten Faktors <math>a=a_{n-1}a_{n-2}\ldots a_1 a_0</math> und eine Ziffer <math>b_j</math> als zweiten Faktor und liefert das Produkt <math>a\cdot b_j</math>.   

<run id="4f327428d1b74">(mult1 '(2 5 3 6 7) 5)</run>

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

<run id="4f3e7a288f64b">
(mult1 '(2 5 3 6 7) 5)
anzahl-prim-op
</run>

Wir rechnen nach:
* n Elementarmultiplikationen
* n+1 Elementaradditionen
Zusammen sind das 2n+1 primitive Basisoperationen, für <math>n=5</math> sind das gerade 11 Stück.




==== Multiplikation zweier n-stelliger natürlicher Zahlen ====




<run id="4f327428d1bf3">(mult '(2 3 4) '(4 5 6))</run>