Conditional-Sum-Addition

Betrachtet man eine zwei Zahlen als Bit-Folgen der länge 3n, wobei n eine natürliche Zahl ist, so kann man diese Zahlen leicht nach dem allgemeinen Schuladditionsalgorithmus addieren.

Benutzt man jedoch Conditional Sunm Addition, so kann man etwas "Zeit sparen" und zwar in dem man das Problem in Teilprobleme aufteilt. Die Idee die dahinter steck, basiert auf der Tatsache, dass man bei Bit-Folgen immer nur einen Übertrag von 1 oder 0 haben kann. Man berechnet also während man die Summe der ersten 2n Bit berechnet gleichzeitig die Summe der letzten n Bit, und zwar für Übertrag 1 bwz. 0 so muss man das Ergebnis nur noch für den tatsächlichen Übertrag ergänzen. Vorlage:Stub