Motivation SS12

Aus ProgrammingWiki

Archivierte Version vom 2012-02-05T17:53:39+00:00. Aktuelle Version

Motivation

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"?

Primitive Basisoperationen

Wir gehen davon aus, dass die folgenden beiden Basisoperationen vorhanden sind und jeweils einen konstanten Zeitaufwand zur Ausführung erfordern.

Addition dreier Ziffern (sog. Volladdierer)
Resultat: zwei Ziffern, nämlich die Ergebnisziffer ... und der Übertrag ...
Multiplikation zweier Ziffern
Resultat: zwei Ziffern, nämlich ...

Für die beiden Operationen wird im Folg. die Scheme-Prozedur prim-op definiert. In deren Definition wird die Basis B der Zahlendarstellung durch den Wert der Variablen basis angegeben. Für den Fall, dass ein anderes Stellenwertsystem zugrunde liegt, ist diese Angabe anzupassen.

(define prim-op
  (let ((anzahl 0) (basis 10))
    (lambda (op x y . c)
      (cond 
        ((eqv? op 'add) 
         (let ((res (+ x y (car c))))
           (if (< res basis)
             (cons res 0)
             (cons (- res basis) 1))))
        ((eqv? op 'mult)
         (let ((res (* x y)))
           (cons (remainder res basis)(quotient res basis))))
        ((eqv? op 'anzahl) anzahl)))))

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

(prim-op 'add 7 8 0)

(prim-op 'add 2 5 1)

(prim-op 'add 9 8 1)

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

(prim-op 'mult 9 8)

Um die Aufwandsanalyse durch diese Definitionen nicht zu verfälschen, wird nicht die Ausführungszeit von prim-op-Aufrufen gestoppt, sondern die Gesamtanzahl der Aufrufe primitiver Basisperationen ermittelt.

(prim-op 'anzahl 'dummy 'dummy)

Es spielt keine Rolle, welche Argumente an zweiter und dritter Stelle verwendet werden.

Motivation SS12

Motivation

Multiplikation großer Zahlen

Primitive Basisoperationen

Suche