Schriftliche Addition

Eine schriftliche Addition mit dreistelligen Zahlen

Die schriftliche Addition ist ein einfacher mathematischer Algorithmus, den man in der Grundschule lernt. Dieser Algorithmus wird auch vom Ripple-Carry-Adder umgesetzt, der in den Rechenwerken moderner Prozessoren verbaut ist.

Idee

Große Zahlen kann man addieren, indem man sie stellenweise von rechts nach links betrachtet. Dabei werden immer nur zwei Ziffern aufaddiert. In der Abbildung rechts werden zum Beispiel zuerst die rechten Ziffern der beiden Summanden addiert: $2+1=3$. Die einzelne Summe dieser ziffernweisen Addition wird dann notiert.

Wenn das Ergebnis einer dieser Additionen mehr als eine Ziffer hat, wird nur die letzte Ziffer des Ergebnisses aufgeschrieben. Die erste Ziffer wandert als Übertrag in die nächste Addition hinein. In der Abbildung wird eine Stelle weiter $5+7=12$ addiert. Die 2 wird hingeschrieben, die 1 als Übertrag in die nächste Addition gezogen.

Ausnahme hiervon ist die linke Stelle: Wenn hier ein zweistelliges Ergebnis herauskommt, gibt es keinen Übertrag, sondern es werden beide Ziffern aufgeschrieben: $6+4+1\text{(Übertrag)}=11$.

In anderen Zahlsystemen

Dieses Verfahren kann genau so auch auf binäre oder hexadezimale Zahlen angewendet werden. Hier muss man nur beachten, dass auch die einzelnen Summen in diesem Zahlsystem ausgerechnet werden müssen.

Beispiel: Binärsystem

Wie viel ist $11101+101100$? Für diese Addition schreiben wir die beiden Summanden wie bekannt übereinander:

		1	1	1	0	1
+	1	0	1	1	0	0

Schritt 1

		1	1	1	0	1
+	1	0	1	1	0	0
						1

Wir beginnen ganz rechts und addieren die beiden rechten Ziffern: $1+0=1$.

Schritt 2

		1	1	1	0	1
+	1	0	1	1	0	0
					0	1

Auch die Stelle davor wird addiert: $0+0=0$.

Schritt 3

		1	1	1	0	1
+	1	0	11	1	0	0
				0	0	1

An der nächsten Stelle ist Vorsicht geboten: hier entsteht ein Übertrag! Denn im Binärsystem gilt $1+1=10$. Die 0 schreiben wir als Ergebnis hin, die 1 geht als Übertrag in die nächste Addition mit ein.

Schritt 4

		1	1	1	0	1
+	1	01	11	1	0	0
			1	0	0	1

Auch bei der nächsten Addition entsteht ein Übertrag. Wir addieren die beiden Summandenziffern und den Übertrag $1+1+1=11$. Eine 1 schreiben wir ins Ergebnis, eine als Übertrag an die nächste Stelle.

Schritt 5

		1	1	1	0	1
+	11	01	11	1	0	0
		0	1	0	0	1

Wir addieren die Summandenziffern und den Übertrag: $1+0+1=10$ und schreiben wieder Ergebnis und Übertrag auf.

Schritt 6

		1	1	1	0	1
+	11	01	11	1	0	0
1	0	0	1	0	0	1

Wir sind an der linken Stelle angekommen. Wieder entsteht ein zweistelliges Ergebnis, aber da es keine weitere Stelle gibt, schreiben wir es nicht als Übertrag auf.

Laufzeit

Für jede Ziffer in den Summanden muss genau eine kleine Addition durchgeführt werden. Bei $n$ Ziffern sind das also $n$ Additionen. Die Laufzeit liegt in ${𝒪}(n)$