補数の役割と計算機

1.　補数とは

「補数（complement）」には、「基数の補数」と「減基数の補数」がある。

基数の補数とは、「元の数」と「補数」を足した場合に桁上がりが発生する数のうち「最小」の数のこと。
減基数の補数とは、「元の数」と「補数」を足すと桁上がりが発生しない数のうち、「最大」の数のこと。

十進法においては、基数の補数は「10の補数」、減基数の補数は「9の補数」
二進法においては、基数の補数は「2の補数」、減基数の補数は「1の補数」
となる。

コンピュータが負の数を保持する際に「2の補数」を用いることが有名。

参考
https://proengineer.internous.co.jp/content/columnfeature/6254#section102
https://qiita.com/satellitesat/items/340de8a946ddd2bac24e

2.　なぜ補数が必要なのか

補数を使うと、引き算を足し算(加算回路)で行えるようになるから

補数を使うと引き算を加算用の回路で行うことができ、減算用の回路が不要になる。
計算機は、回路が多くなればなるほど構造が複雑になるため、回路を減らすことにメリットがある。
歯車式の計算機から現代のコンピュータにいたるまで、計算機に補数が利用されるのはそのためである。

3.　具体例

3.1.　パスカリーヌ

3.1.1.　最古の機械式計算機

17世紀初頭、フランスの数学者でもあり哲学者のブレーズ・パスカルが構想・設計・製作した計算機。徴税官であった父親の作業を軽減するために16歳のときに考案し製作したという。

歯車によって構成されたこの機械式計算機は、9の補数を用いることで、加算と減算を一つの機構で実現している。
パスカリーヌは現存する最古の機械式計算機である。

3.1.2.　パスカリーヌが応用した補数の原理

数値Aの9の補数(CP(A)と記載する)を定式化すると以下になる。

$$CP(A)=10^n-1-A$$

上記の式を応用して、数値Aから数値Bを引いた値の9補数(CP(A-B))を考えると以下のように表せる。
$$CP(A-B)=10^n-1-(A-B)$$

この式は以下のように整理できる。

\begin{align}
CP(A-B) &= 10^n-1-(A-B)\\
&= 10^n-1-A+B\\
&= CP(A)+B
\end{align}

つまり、数値Aから数値Bを引いた値の9の補数(CP(A-B))は、数値Aの9の補数に数値Bを足すことで求めることができる。
数値Aから数値Bを引いた値の9の補数がわかれば、数値Aから数値Bを引いた値もわかる。

3.1.3.　パスカリーヌへの補数入力

パスカリーヌでは減算を行う際、利用者自身が引かれる数（上記では数値A）の9の補数を入力しなければならなかった。
つまり、数値A-数値Bを行う場合は、利用者は数値Aではなく、数値Aの9の補数を入力する。
そうすることで、上記の式で表される「CP(A)+B」を実現している。(数値Bはそのまま入力)

計算される結果も9の補数(上記の式でいうCP(A-B))であったが、求めたい値(A-B)への変換はパスカリーヌに表示された値で把握できた。

参考
https://en.wikipedia.org/wiki/Pascal%27s_calculator
https://www.wizforest.com/gear/pascal/pascal2.html

3.2.ノイマン型コンピュータ

3.2.1.　2の補数である負の値

コンピュータの父とも呼ばれるジョン・フォン・ノイマンは「First Draft of a Report on the EDVAC」(1945年)でノイマン型コンピュータを提唱する。その中で、コンピュータ内部の負の値は、2の補数で保持することとしている。
この考え方は現代のコンピュータにも引き継がれており、今でも負の値は2の補数で保持されている。

参考

http://www.yamamo10.jp/yamamoto/lecture/2005/3E/3rd/html/node3.html

当時のコンピュータは、構成する部品数の多さから、構築、保守・メンテナンスに多大な労力を要することが問題であった。
そのため、減算を加算回路でおこなうことで構造を単純化し構成部品の削減を目指した。