Arithmetik in Stellenwertsystemen
aus Wikipedia, der freien Enzyklopädie
Als Arithmetik in Stellenwertsystemen wird das Ausführen der Grundrechenarten Addition, Subtraktion, Multiplikation und Division in Stellenwertsystemen bezeichnet. Zur Durchführung dieser Operationen können die aus der Schule für das Dezimalsystem bekannten Algorithmen leicht auf beliebige andere Stellenwertsysteme übertragen werden.
Für die Addition und die Subtraktion sind diese Algorithmen im Wesentlichen bestmöglich. Für die Multiplikation existieren aufwändigere aber effizientere Algorithmen, zum Beispiel der Karatsuba-Algorithmus, der Toom-Cook-Algorithmus oder der Schönhage-Strassen-Algorithmus.
Inhaltsverzeichnis |
[Bearbeiten] Grundlagen
[Bearbeiten] Operationen auf Zeichenketten
Die Algorithmen für Addtion, Subtraktion, Multiplikation und Division arbeiten auf Zahlendarstellungen. Diese können auch als Zeichenketten aufgefasst werden, deren einzelne Zeichen die Ziffern des Stellenwertsystems und ggf. das Minuszeichen als Vorzeichen beinhalten, um negative Zahlen zu markieren. Um auf diesen Zeichketten rechnen zu können, werden einige primitive Operationen auf diesen benötigt. Für die Addition und die Subtraktion werden im Wesentlichen die Operationen
- isEmpty(), welche genau dann wahr zurückliefert, wenn die Zeichenkette leer ist,
- cut_last(), welche das letzte Zeichen von der Zeichenkette abschneidet und als Ergebnis zurückliefert und
- cat_first(char), welche ein Zeichen char an den Anfang der Zeichenkette stellt,
verwendet.
[Bearbeiten] Operationen auf Zeichen
Neben den Operationen für die Zeichenketten werden auch Operationen auf Zeichen benötigt. Diese sind im Unterschied zu den Operationen auf Zeichenketten im vorherigen Abschnitt von der Grundzahl des Stellenwertsystems abhängig, in dem die Zahlen dargestellt sind. Diese Grundzahl sei im folgenden stets mit b bezeichnet.
Für die Addition und die Subtraktion werden vier Operationen benötigt. Die Operationen
- add_modulo(xchar, ychar, übertrag) und
- subtr_modulo(xchar, ychar, übertrag)
liefern als Ergebnis ein Zeichen zurück, das eine beliebige Ziffer des betrachteten Stellenwertsystems ist. Die Operationen
- add_übertrag(xchar, ychar, übertrag),
- subtr_übertrag(xchar, ychar, übertrag),
liefern als Ergebnis entweder wahr oder falsch zurück. Die Parameter xchar und ychar sind jeweils Zeichen, die beliebige Ziffern des betrachteten Stellenwertsystems enthalten. Der Parameter übertrag ist boolesch, das heißt er darf nur die Werte wahr oder falsch annehmen.
Sind xv und yv die Zahlen, die durch die Ziffern in xchar und ychar repräsentiert sind, und ist üv genau dann Null, wenn übertrag den Wert falsch entält und sonst Eins, so sei
- zva = xv+yv+üv und
- zvb = xv-yv-üv.
Das Ergebnis der Operationen add_modulo(...) ist dann die Ziffer, die dem Rest von zva beim Teilen durch b zugeordnet ist. Analog ist das Ergebnis der Operation subtr_modulo(...) die Ziffer, die dem Rest von zvb beim Teilen durch b zugeordnet ist. Die Operationen add_übertrag(...) bzw. subtr_übertrag(xchar, ychar, übertrag) liefern als Ergebnis genau dann falsch, wenn der ganzzahlige Anteil beim Teilen von zva bzw zvb Null ist. Andernfalls liefern diese Operationen als Ergebnis wahr.
| Addition | Subtraktion | |||||||||||||||||||||
| übertrag | falsch | wahr | übertrag | falsch | wahr | |||||||||||||||||
| ychar\xchar | 0 | 1 | 2 | 3 | 4 | 0 | 1 | 2 | 3 | 4 | ychar\xchar | 0 | 1 | 2 | 3 | 4 | 0 | 1 | 2 | 3 | 4 | |
| 0 | 0 | 1 | 2 | 3 | 4 | 1 | 2 | 3 | 4 | 0 | 0 | 0 | 1 | 2 | 3 | 4 | 4 | 0 | 1 | 2 | 3 | |
| 1 | 1 | 2 | 3 | 4 | 0 | 2 | 3 | 4 | 0 | 1 | 1 | 4 | 0 | 1 | 2 | 3 | 3 | 4 | 0 | 1 | 2 | |
| 2 | 2 | 3 | 4 | 0 | 1 | 3 | 4 | 0 | 1 | 2 | 2 | 3 | 4 | 0 | 1 | 2 | 2 | 3 | 4 | 0 | 1 | |
| 3 | 3 | 4 | 0 | 1 | 2 | 4 | 0 | 1 | 2 | 3 | 3 | 2 | 3 | 4 | 0 | 1 | 1 | 2 | 3 | 4 | 0 | |
| 4 | 4 | 0 | 1 | 2 | 3 | 0 | 1 | 2 | 3 | 4 | 4 | 1 | 2 | 3 | 4 | 0 | 0 | 1 | 2 | 3 | 4 | |
Die Operationen für die Addition und die Subtraktion lassen sich beispielsweise durch Tabellen realisieren. Die nebenstenden Tabellen zeigen dies für den Fall b=5.
Die weiß und grau unterlegten Einträge geben jeweils das Ergebnis der Operation add_modulo(...) bzw. subtr_modulo(...) an. Weiß hinterlegte Einträge bedeuten, dass die Operationen add_übertrag(...) bzw. subtr_übertrag(...) als Ergebnis falsch zurückliefern. Grau hinterlegte Einträge bedeuten hingegen, dass diese Operationen wahr als Ergebnis zurückliefern.
[Bearbeiten] Addition und Subtraktion
Die Algorithmen für die Addition und die Subtraktion zweier ganzer Zahlen x und y -- dargestellt in einem Stellenwertsystem mit Grundzahl b -- sind im Wesentlichen identisch. Sie vereinfachen sich erheblich, wenn man für die Addition zunächst nur den Fall betrachtet, dass die Summanden x und y natürliche Zahlen sind und für die Subtraktion zusätzlich annimmt, dass der Minuend x größer als der Subtrahend y ist.
[Bearbeiten] Addition natürlicher Zahlen
Seien x und y die Zeichenketten, die die beiden Summanden repräsentieren. Der Algorithmus für die Addition arbeitet dann wie folgt. Zunächst wird eine boolesche Variable übertrag auf den Wert falsch gesetzt und eine Variable z auf die leere Zeichenkette. Die Variable z soll am Ende das Ergebnis enthalten. Solange eine der beiden Zeichenketten x bzw. y noch Zeichen oder übertrag den Wert wahr enthält, wird die letzte Ziffer von x bzw. y mit cut_last() abgelöst und in xchar bzw. ychar gespeichert. Enthält x bzw. y kein Zeichen mehr, so wird xchar bzw. ychar die Ziffer '0' zugewiesen. Anschließend wird das Ergebnis von add_modulo(xchar, ychar, übertrag) innerhalb dieser Schleife als höchstwertige Ziffer mit cat_first() der Variablen z vorangestellt und übertrag auf das Ergebnis von add_übertrag(xchar, ychar, übertrag) gesetzt. Folgender Pseudocode im C-Stil soll dies verdeutlichen:
funktion Zeichenkette addition(Zeichenkette x, Zeichenkette y) {
// Initialisierung
Zeichen xchar, ychar;
Zeichenkette z = "";
Boolean übertrag = falsch;
// Schleife bis das Ende beider Zeichenketten erreicht ist
solange (!x.isEmpty() oder !y.isEmpty() oder übertrag)) {
// ggf. Null als Ziffer
falls (x.isEmpty())
xchar = '0';
sonst
xchar = x.cut_last();
// ggf. Null als Ziffer
falls (y.isEmpty())
ychar = '0';
sonst
ychar = y.cut_last();
z.cat_first(add_modulo(xchar, ychar, übertrag));
übertrag = add_übertrag(xchar, ychar, übertrag);
}
// Ergebnis zurückgeben
rückgabe z;
}
[Bearbeiten] Subtraktion natürlicher Zahlen mit positivem Ergebnis
Für die Subtraktion natürlicher Zahlen kann ein ähnlicher Algorithmus verwendet werden, sofern der Minuend x größer als der Subtrahend y ist. Es muss lediglich die Operation add_modulo(...) durch subtr_modulo(...) und die Operation add_übertrag(...) durch subtr_übertrag(...) ersetzt werden. Es ergibt sich also folgender Pseudocode:
funktion Zeichenkette subtraktion(Zeichenkette x, Zeichenkette y) {
// Initialisierung
Zeichen xchar, ychar;
Zeichenkette z = "";
Boolean übertrag = falsch;
// Schleife bis das Ende beider Zeichenketten erreicht ist
solange (!x.isEmpty() oder !y.isEmpty() oder übertrag)) {
// ggf. Null als Ziffer
falls (x.isEmpty())
xchar = '0';
sonst
xchar = x.cut_last();
// ggf. Null als Ziffer
falls (y.isEmpty())
ychar = '0';
sonst
ychar = y.cut_last();
z.cat_first(subtr_modulo(xchar, ychar, übertrag));
übertrag = subtr_übertrag(xchar, ychar, übertrag);
}
// Ergebnis zurückgeben
rückgabe z;
}
[Bearbeiten] Addition und Subtraktion beliebiger ganzer Zahlen
Für die Addition und Subtraktion beliebiger ganzer Zahlen können die oben dargestellten Algorithmen als Grundlage verwendet werden. Wie in der Tabelle dargestellt sind lediglich verschiedene Fälle in ihren möglichen Kombinationen zu unterscheiden.
| Fallunterscheidungen | ||||
| Operation | Bed. an x | Rel. zw. Beträgen | Bed. an y | Operation |
| Addition | nicht negativ | egal | nicht negativ | addition(|x|, |y|) |
| Addition | nicht negativ | | x | > | y | | negativ | subtraktion(|x|, |y|) |
| Addition | nicht negativ | | x | = | y | | negativ | 0 |
| Addition | nicht negativ | | x | < | y | | negativ | -subtraktion(|y|, |x|) |
| Addition | negativ | | x | > | y | | nicht negativ | -subtraktion(|x|, |y|) |
| Addition | negativ | | x | = | y | | nicht negativ | 0 |
| Addition | negativ | | x | < | y | | nicht negativ | subtraktion(|y|, |x|) |
| Addition | negativ | egal | negativ | -addition(|x|, |y|) |
| Subtraktion | nicht negativ | | x | > | y | | nicht negativ | subtraktion(|x|, |y|) |
| Subtraktion | nicht negativ | | x | = | y | | nicht negativ | 0 |
| Subtraktion | nicht negativ | | x | < | y | | nicht negativ | -subtraktion(|y|, |x|) |
| Subtraktion | nicht negativ | egal | negativ | addition(|x|, |y|) |
| Subtraktion | negativ | egal | nicht negativ | -addition(|x|, |y|) |
| Subtraktion | negativ | | x | > | y | | negativ | -subtraktion(|x|, |y|) |
| Subtraktion | negativ | | x | = | y | | negativ | 0 |
| Subtraktion | negativ | | x | < | y | | negativ | subtraktion(|y|, |x|) |
So ist die Addition auf die Subtraktion nach obigem Algorithmus zurückzuführen, falls genau einer der Summanden negativ ist. Umgekehrt wird die Subtraktion auf die Addition nach obigem Algorithmus zurückgeführt, falls genau einer der Operanden negativ ist. In jedem Fall sind die Operationen nach obigen Algorithmus immer auf die absoluten Beträge der Operanden anzuwenden.
Muss die Subtraktion nach obigem Algorithmus durchgeführt werden und ist der absolute Betrag des Minuenden kleiner als der absolute Betrag des Subtrahenden, so sind Minuend und Subtrahend zu vertauschen. Sind Minuend und Subtrahend gleich groß, so ist das Ergebnis immer Null.
Abschließend muss dem Ergebnis gegebenenfalls noch ein negatives Vorzeichen vorangestellt werden. Die in der Tabelle angegebene Negation des Ergebnis kann in diesem Sinne auch syntaktische statt arithmetische Operation interpretiert werden, da das Ergebnis der Addition bzw. Subtraktion nach obigen Algorithmen nie negativ ist und daher auch kein negatives Vorzeichen entfernt werden braucht.
In gleicher Weise kann auch das Bilden des absoluten Betrages syntaktisch durch Entfernen eines ggf. Vorhandenen neagtiven Vorzeichens erfolgen.
