Motivation SS12
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 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.
In der Definition von primitiv-add wird die Basis B der Zahlendarstellung durch den Wert der Variablen basis angegeben. Für den Fall, dass ein anderes Stellenwertsystem betrachtet wird, ist diese anzupassen.