- ペアノの公理は「0」と「後者関数S」だけで自然数を定義し、Common Lispのリスト構造でも直接実装できます。
- ただ、足される数が 0 になるまでS(n)をたどる再帰的な計算は、非効率です。
- 人間が足し算をするときには、一桁の和を覚え、繰り上がりを次の桁に渡すことで、桁数に比例した処理に抑えています。
- 実は、コンピュータの加算器も同じ構造で、2進数表現と全加算器の組み合わせが計算効率を支えています。
1. 1+1をCommon Lispで証明する
大学の数学で、自然数の定義として出てくる「ペアノの公理」。
ふだんの算数で使う数字とはまったく違う、数のとらえかたにびっくりします。
しかし、ペアノの数と算数、そして計算機をつないで考えてみると、「データ表現がアルゴリズムを決める」という別の話が見えてきます。
1.1. ペアノの公理とCommon Lispによる実装
自然数を厳密に定義する方法の一つがペアノの公理です。
必要な概念は二つだけで、
一つは自然数の出発点である 0、
もう一つはある自然数nの「次の数」を返す後者関数 S(n)です1。
たとえば、1はS(0)、2はS(S(0))、3はS(S(S(0)))のように、この組み合わせで、すべての自然数が表現できます。
自然数加法は、この後者関数を使って再帰的に定義されます。
「BにS(n)を足す」を「A+Bの結果にSを適用する」に置き換え続け、Bが0になったときAが答えです。
このペアノの公理をCommon Lispのリストで直接表現し、加法が定義できることを確認します。
空のリスト'()を 0 とみなし、consを後者関数として、実装してみます。
;; 0の定義
(defparameter *zero* '())
;; 後者関数：リストの先頭に要素を追加して「次の数」にする
(defun succ (n) (cons nil n))
;; 前者関数：後者関数の逆
(defun pred (n) (cdr n))
;; 0判定
(defun peano-zero-p (n) (null n))
;; 加法の定義
(defun peano-add (a b)
(if (peano-zero-p b)
a
(peano-add (succ a) (pred b))))Code language: Lisp (lisp)このように定義して、2+3=5を確認するなら、
;; 1から9の定義（後者関数を積み上げる）
(defparameter *one* (succ *zero*))
(defparameter *two* (succ *one*))
(defparameter *three* (succ *two*))
(defparameter *four* (succ *three*))
(defparameter *five* (succ *four*))
(defparameter *six* (succ *five*))
(defparameter *seven* (succ *six*))
(defparameter *eight* (succ *seven*))
(defparameter *nine* (succ *eight*))
;; 1 + 1 = 2 の確認
(equal (peano-add *one* *one*) *two*) ; => T
(equal (peano-add *two* *three*) *five*) ; => TCode language: Lisp (lisp)(add *one* *one*)は*two*と等しくなります。
ペアノの公理に従って、1+1=2が証明できました。
それぞれの式を評価すると、Tの数が数値を表すリストになっていることがわかります。
*zero*
;=> NIL
*one*
;=> (NIL)
*two*
;=> (NIL NIL)
(peano-add *one* *one*)
;=> (NIL NIL)
(peano-add *two* *three*)
;=> (NIL NIL NIL NIL NIL)Code language: Lisp (lisp)このようなリストを見るのは大変なので、一応検算のために変換関数を導入しておきます。
;; ペアノ式の数を整数に変換する（検算用）
(defun peano->integer (n)
(if (peano-zero-p n)
0
(1+ (peano->integer (pred n)))))
(peano->integer *five*)
;=> 5Code language: PHP (php)余談ですが、ローマ数字は 1進数表記 です。
さすがに、 I だけが並ぶと読みにくいので、5の区切りに V や X が挿入されます。
I I I I V I I I I X I I I I V I I I I ...このような書き方だから、IV で 4 を表すのですね。
1.2. 10進数とペアノ式の対応
さて、このまま *eleven* など続けていくのは大変なので、10以上の数は桁のリストで表現することにします。
上の位からの順に並べ、たとえば、
10は(list *one* *zero*)、
15は(list *one* *five*)と表現します。
この桁リストがペアノ式の単一の数と対応することを確認するために、変換関数を用意しておきます。
;; 10のペアノ式表現
(defparameter *ten* (succ *nine*))
;; 桁のリストをペアノ式の単一の数に簡約する（上位桁が先頭）
;; (list *one* *five*) => *one* * *ten* + *five* = 15
(defun digits->peano (digits)
(digits->peano-acc digits *zero*))
(defun digits->peano-acc (digits acc)
(if (null digits)
acc
(digits->peano-acc
(cdr digits)
(peano-add (peano-add-times acc *ten*) (car digits)))))
;; a を n 回加算する
(defun peano-add-times (a n)
(if (peano-zero-p n)
*zero*
(peano-add a (peano-add-times a (pred n)))))Code language: Lisp (lisp)digits->peanoの動作確認として、*nine*の次の数が桁リスト(*zero* *one*)と等しいことを確かめます。
9の次が10進数で繰り上がることをペアノ式の中で確認する形です。
;; *nine*の次と (list *one* *zero*)は同じ
(equal (succ *nine*)
(digits->peano (list *one* *zero*))) ; => T
(digits->peano (list *one* *five*))
;=> (NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL)
(peano->integer (digits->peano (list *one* *five*)))
;=> 15Code language: Lisp (lisp)2. 現実の計算はペアノ式ではない
ペアノ式の加法がなぜ非効率なのか、データ表現の側面から見てみます。
ペアノの公理で定義された数は「美しい」です。
*one*は(NIL)、*two*は(NIL NIL)というリストで、
数字を使わずにリスト構造だけで自然数が表現できています。
しかし、さすがに「非効率」です。
100という数を表現するには要素が100個のリストが必要です。peano-addはBが0になるまでpredでBを削りながらsuccでAを積み上げるので、100+100の計算には200ステップかかります。
(peano->integer (peano-add
(digits->peano (list *one* *zero* *zero*))
(digits->peano (list *one* *zero* *zero*))))
;=> 200 Code language: Lisp (lisp)Nが大きくなるほど計算量がNに比例して増える、O(N)の処理です。
もちろん、現実の手計算でも計算機でも、こんなことは起きていません。
100+100を計算するのにステップ数が100に比例することはない。
では、何が違うのでしょうか。
2.1. 一桁の和はパターンの暗記
小学校で最初に習う足し算を思い出してください。
1+1、2+3、7+8。
これらを計算するとき、はじめは指折り数えましたが、指折りは、S(S(S(…)))に相当します。
しかし、すぐに「計算」できるようになります。
これは、一桁同士の足し算のパターンは全部で100通りしかないからです。
つまり、8+7=15という答えは想起です。
パターンを暗記することで、一桁の加法を定数時間O(1)の操作に変えています。
Lisp でも、表引きで一桁の加法を定数時間の操作に変えられることを示します。
足し算表を、*zero*から*nine*をキーとして使い、連想リストで書いてみます。
;; 一桁の足し算表：結果も桁のリストで表現する
;; 答えが10未満なら一要素のリスト、10以上なら二要素のリスト
(defparameter *addition-table*
`(((,*zero* ,*zero*) . (,*zero*))
((,*zero* ,*one*) . (,*one*))
;; ... 中略 ...
((,*seven* ,*eight*) . (,*one* ,*five*)) ; 7+8=15
((,*eight* ,*seven*) . (,*one* ,*five*)) ; 8+7=15
((,*eight* ,*eight*) . (,*one* ,*six*)) ; 8+8=16
;; ...
((,*nine* ,*nine*) . (,*one* ,*eight*)))); 9+9=18
;; 表から探す
(defun assoc-digit-add (a b)
(cdr (assoc (list a b) *addition-table* :test #'equal)))Code language: Lisp (lisp)計算ではなくあらかじめ全パターンを記述しておくことが「暗記」の意味です。assoc-digit-addは、一桁の足し算なら表を一回引くだけで答えが返ります。
;; 動作確認
(assoc-digit-add *eight* *seven*)
;=> ((NIL) (NIL NIL NIL NIL NIL))
(digits->peano
(assoc-digit-add *eight* *seven*))
;=> (NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL)
(peano->integer (digits->peano
(assoc-digit-add *eight* *seven*)))
;=> 15Code language: Lisp (lisp)peano-addで、8+7に15ステップかかったのと対照的です。
2.2. 繰り上がりと位取りの合成
それでは、二桁以上の足し算はどうでしょう。
たとえば、37+48を計算するとき、
まず一の位で8+7の表を引いて(*five* *one*)を得て、*five*をその桁の答えとして置き、*one*を繰り上がりとして十の位に送ります。
十の位では3+4+繰り上がり1を処理して8が出ます。
暗記した一桁の和と繰り上がりを組み合わせると、多桁の加算が桁数に比例した処理になります。assoc-digit-addでは桁を引き、結果の先頭をその桁の値、残りを繰り上がりとして次に送っています。
;; 桁のリストa, bを上位桁から足し合わせる（ビッグエンディアン）
;; 例： (list *three* *seven*) + (list *four* *eight*) = 37 + 48
(defun human-add (a b)
(human-add-acc (reverse a) (reverse b) nil '()))
;; 桁和の結果から繰り上がりを取り出す
(defun carry-of (result)
(if (cdr result) (car result) nil))
;; 桁和の結果から桁の値を取り出す
(defun digit-of (result)
(car (last result)))
(defun human-add-acc (a b carry acc)
(cond
((and (null a) (null b) (null carry))
acc)
(t
(let* ((da (if a (car a) *zero*))
(db (if b (car b) *zero*))
(partial (assoc-digit-add da db))
(with-carry
(if carry
(assoc-digit-add (digit-of partial) carry)
partial))
(digit (digit-of with-carry))
(next (carry-of with-carry)))
(human-add-acc (if a (cdr a) '())
(if b (cdr b) '())
next
(cons digit acc))))))
;; 動作確認： 37 + 48 = 85
(human-add (list *three* *seven*)
(list *four* *eight*))
;; => ((NIL NIL NIL NIL NIL NIL NIL NIL) (NIL NIL NIL NIL NIL))Code language: Lisp (lisp)peano-addでは、Bが0になるまでひたすらSをたどりましたが、human-addは表引きで各桁を処理して繰り上がりだけを次に渡します。
連想リストのキーとして計算を暗記して、位取りの合成を使うと、このように計算できます。
2.3. データ表現がアルゴリズムを制約する
計算効率は依存関係グラフの形で決まります。
peano-addを見直すと、各ステップは前のステップの結果に依存していました。
peano-add の依存関係（直列）
add(2,3)
└─ add(3,2)
└─ add(4,1)
└─ add(5,0) → 5
各ステップが前の結果を待つ。Bが大きいほど鎖が伸びる。peano-addでは、step N+1の引数が必ずstep Nの結果です。(succ a)と(pred b)を得てからでないと次の呼び出しが始まらない。
この「前の結果が次の入力になる」連鎖が直列の依存関係で、Bの大きさだけステップが並ぶため O(N) になります。
一方、位取り記数法は、Nという数をlog(N)桁で表現します。
100は3桁、1,000,000は7桁です。
数が大きくなっても、構造のサイズはゆっくりしか増えません。
もう一つの重要な違いは、桁という「まとまり」が表現の中に存在することです。
このため、桁同士を対応させる操作が定義でき、一の位は一の位と、十の位は十の位と処理できます。
human-add の依存関係
[3] [7] [4] [8]
↓ ↓ ↓ ↓
一の位: 7+8 ─carry→ 十の位: 3+4+1
↓ ↓
5 8
→ 85Code language: CSS (css)各桁は表を一回引くだけ。
桁数分だけ横に並ぶ。
渡すのは繰り上がり1ビットだけで、桁の数だけ処理すれば答えが出ます。
3. 2進数表現と半加算器
コンピュータの加算器でも、この「桁ごとに独立して処理できる」という構造を利用しています。
ペアノ式はnilの個数で数を表す1進数でした。
しかし、使えるシンボルがtとnilの2種類に増えるだけで、表現の可能性は飛躍的に向上するからです。
各要素が1ビットになり、リストが2進数の桁列になります。
たとえば、15は、(nil nil nil nil nil t t t)と書けます。
もちろん、実際にはリストではなく回路上の電圧の高低がtとnilに対応します。
しかし構造は同じで、シンボルの種類を2つにしただけで、表現サイズがNからlog(N)に変わります。
ペアノ式で255個並んでいたnilは、8ビットの値に収まります。
3.1. 半加算器と真理値表
一桁同士の和は有限個のパターンなので、回路には足し算表のような真理値表があります。
これが半加算器で、1ビット同士を加算して結果と繰り上がりを出力する最小単位の回路です。
半加算器の真理値表
A | B | Sum | Carry
---+---+-----+------
0 | 0 | 0 | 0
0 | 1 | 1 | 0
1 | 0 | 1 | 0
1 | 1 | 0 | 1
Sum = XOR(A, B)
Carry = AND(A, B)Code language: PHP (php)加算器の動作を Common Lispで再現すると、
;; XOR： 入力が異なるとき真
(defun xor (a b) (and (or a b) (not (and a b))))
;; 半加算器： 2ビットを加算して和と繰り上がりを返す
(defun half-adder (a b)
(list :sum (xor a b) ; 和のビット
:carry (and a b))) ; 繰り上がりCode language: Lisp (lisp)3.2. 全加算器と繰り上がり
半加算器を組み合わせ、繰り上がり入力も処理できるようにしたものが「全加算器」です。
半加算器は二つの入力ビットしか扱えませんが、実際の加算では前の桁からの繰り上がりも受け取ります。
この全加算器を桁の数だけ横に並べると多ビットの加算器になります。
一の位から順に繰り上がりを次の桁に渡していく、筆算と同じ構造です。
;; 全加算器： 2ビット＋前段からの繰り上がりを加算する
(defun full-adder (a b carry-in)
(let* ((h1 (half-adder a b))
(h2 (half-adder (getf h1 :sum) carry-in))
(carry (or (getf h1 :carry) (getf h2 :carry))))
(list :sum (getf h2 :sum)
:carry carry)))
;; 動作確認： 1 + 1 + 繰り上がり1 = 和1、繰り上がり1
(full-adder t t t) ; => (:SUM T :CARRY T) つまり 1+1+1=3、2進数で11Code language: Lisp (lisp)full-adderの各呼び出しは独立した桁の処理で、前段から受け取るのはcarry-inだけです。
3.3. 8bitの加算機
半加算器は2ビットを足して和と繰り上がりを出します。
全加算器は半加算器を2つ組み合わせて、繰り上がり入力も処理できるようにしたものです。
8ビット加算器では全加算器を8個横に並べます。
ここでは、入出力を先頭が上位のt/nilのリストで表現します。
たとえば、
7は(nil nil nil nil nil t t t)、
8は(nil nil nil nil t nil nil nil)です。
;; 8ビット加算器（ビッグエンディアン、t/nilのリスト）
(defun adder-8bit (a b)
(let ((result (adder-acc (reverse a) (reverse b) nil '())))
(values (cdr result) ; 8ビットの和
(car result)))) ; オーバーフロービット
(defun adder-acc (a b carry acc)
(if (and (null a) (null b))
(cons carry acc)
(let* ((da (if a (car a) nil))
(db (if b (car b) nil))
(fa (full-adder da db carry))
(sum (getf fa :sum))
(next (getf fa :carry)))
(adder-acc (if a (cdr a) '())
(if b (cdr b) '())
next
(cons sum acc)))))Code language: Lisp (lisp)adder-accの再帰は、全加算器を「横に並べる」ことに対応しています。
最後に残った繰り上がりは、ビット目のオーバーフロービットになります。
;; 動作確認： 7 + 8 = 15
(multiple-value-bind (sum overflow)
(adder-8bit '(nil nil nil nil nil t t t)
'(nil nil nil nil t nil nil nil))
(list :sum sum :overflow overflow))
;; => (:SUM (NIL NIL NIL NIL T T T T) :OVERFLOW NIL)Code language: Lisp (lisp)adder-8bitは、まず下の位から計算するために、入力を両方をreverseします。
a reversed: (t t t nil nil nil nil nil)
b reversed: (nil nil nil t nil nil nil nil)adder-accが下位ビットから1ビットずつ処理します。
1ビット目：(full-adder t nil nil)。 sum=t、 carry=nil。
2ビット目：(full-adder t nil nil)。 sum=t、 carry=nil。
3ビット目：(full-adder t nil nil)。 sum=t、 carry=nil。
4ビット目：(full-adder nil t nil)。 sum=t、 carry=nil。
5ビット目：(full-adder nil nil nil)。sum=nil、carry=nil。
6〜8ビット目：同様に0。
sumの部分をつないで逆順にすると(nil nil nil nil t t t t)、
0b00001111なので、15です。
検算用の変換関数を作るなら、
;; t/nilのビットリスト（ビッグエンディアン）を整数に変換する
(defun bits->integer (bits)
(reduce (lambda (acc b) (logior (ash acc 1) (if b 1 0)))
bits
:initial-value 0))
(bits->integer '(nil nil nil nil t t t t))
;=> 15
;; ビット演算を使わないなら
(defun bits->integer-by-arithmetic (bits)
(loop for b in bits
with result = 0
do (setf result (+ (* result 2) (if b 1 0)))
finally (return result)))Code language: Lisp (lisp)もちろん、これは Lisp の連結リストによる冗長な実装です。
しかし、コンピュータのCPUの中にある加算器も、原理的には人間の繰り上がり計算と同じことをしていることが理解できると思います。
4. 公理の簡潔さとアルゴリズムの効率
ペアノの公理は、自然数を最小限の空リストの連結で定義しました。
一方、計算機は、数を 0 と 1 の 2進数で表現します。
どちらも原子的表現ですが、操作の粒度が変わります。
アルゴリズムの効率は、データ表現をどう選ぶかでほぼ決まってしまいます。
計算機の効率性は、数学的な純粋さではなく、「位取り記数法」という発明によって支えられているわけです。
実は、私たちが小学校1年の算数で足し算を学んだとき、すでにこの構造を体で覚えていたわけですね。