AuK/Motivation SS12

Wiki-Quelltext dieser Seite.

<language>Scheme</language>

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



<language>Scheme</language>
<language>Scheme</language>
=== 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) <br/> Resultat: zwei Ziffern, nämlich die Ergebnisziffer ... und der Übertrag ... 
# Multiplikation zweier Ziffern <br/> Resultat: zwei Ziffern, nämlich ...

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

<code id="4f2e6547da2f9">
(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))))) 
</code>

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

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

Um die Aufwandsanalyse durch diese Definitionen nicht zu verfälschen, wird nicht die Ausführungszeit von <tt>prim-op</tt>-Aufrufen gestoppt, sondern die ''Gesamtanzahl'' der Aufrufe primitiver Basisperationen ermittelt. 
<run id="4f2ec223402c3">(prim-op 'anzahl 'dummy 'dummy)</run>
Es spielt keine Rolle, welche Argumente an zweiter und dritter Stelle verwendet werden.