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



=== 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 werden im Folgenden Scheme-Prozeduren definiert. Die dabei verwendeten eingebauten Scheme-Sprachelemente verursachen im Allg. einen Gesamtaufwand, der von den Argumenten beim Aufruf abhängt, der also nicht konstant ist. Deshalb ist bei Aufwandsuntersuchungen von Prozessen, die diese primitiven Operationen verwenden, von Zeitmessungen abzusehen. Aussagekräftig ist dagegen die jeweilige Anzahl aufgerufener Basisoperationen. Hierfür stellen wir einen Zähler als globale Variable bereit. Dieser Zähler muss vor jedem Aufruf mit 0 initialisiert werden.

<code id="4f2e6547da27e">(define primitive-operationen 0)</code>

In der Definition von <tt>primitiv-add</tt> 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 betrachtet wird, ist diese anzupassen.

<code id="4f2e6547da2f9">
(define primitiv-add
  (lambda (x y c)
    (set! primitive-operationen (+ primitive-operationen 1))
    (let ((basis 10)(res (+ x y c)))
      (if (< res basis)
        (cons res 0)
        (cons (- res basis) 1)))))
</code>
<run id="4f2e6547da47c">(primitiv-add 2 5 0)</run>
<run id="4f2e6547da4d3">(primitiv-add 7 8 0)</run>
<run id="4f2e6547da53d">(primitiv-add 7 8 1)</run>

Nun können wir nach der Anzahl der inzwischen ausgeführten Basisoperationen fragen
<run id="4f2e66adbd4e5">primitive-operationen</run>
und den Zähler anschließend wieder zurücksetzen:
<run id="4f2e6547da38e">(set! primitive-operationen 0)</run>