先読み桁上げ

足し算では桁上げが数全体に波及することがある。999,999 + 1では6桁にわたって桁上げが起きる。1桁ずつ処理すると最悪の場合は桁数と同じだけの手順がかかり、50桁を扱う予定だったチャールズ・バベッジの解析機関にとっては、とても許容できない遅さだった。

そこでバベッジは、どこで桁上げが必要になるかを事前に感知し、一度の動作でまとめて実行する機構を考案した。これにより桁上げの所要時間は桁数にほぼ依存しなくなる。この先読み桁上げ機構は解析機関の中でも特に巧妙で手間のかかる部品のひとつで、すべての桁上げを先に並列計算するという発想は、1世紀余り後の現代のプロセッサ内部にあるキャリールックアヘッド加算器そのものである。