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/>  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. 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))
    (lambda (x y c)
      (let ((res (+ x y c)))
        (if (< res basis)
            (cons res 0)
            (cons (- res basis) 1))))))

(define prim-mult
  (let ((basis 10))
    (lambda (x y)
      (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 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-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.
<nowiki>Hinweis: Es ist zu beachten, dass diese Initialisierung bei jedem Prozeduraufruf erneut ausgeführt wird.</nowiki>