TAOCP V4F1にnim multiplicationという話題がある(演習問題7.1.3-10).
結論からいうとこういう乗算表を作るのだ.
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
2 0 2 3 1 8 10 11 9 12 14 15 13 4 6 7 5
3 0 3 1 2 12 15 13 14 4 7 5 6 8 11 9 10
4 0 4 8 12 6 2 14 10 11 15 3 7 13 9 5 1
5 0 5 10 15 2 7 8 13 3 6 9 12 1 4 11 14
6 0 6 11 13 14 8 5 3 7 1 12 10 9 15 2 4
7 0 7 9 14 10 13 3 4 15 8 6 1 5 2 12 11
8 0 8 12 4 11 3 7 15 13 5 1 9 6 14 10 2
9 0 9 14 7 15 6 1 8 5 12 11 2 10 3 4 13
10 0 10 15 5 3 9 12 6 1 11 14 4 2 8 13 7
11 0 11 13 6 7 12 10 1 9 2 4 15 14 5 3 8
12 0 12 4 8 13 1 9 5 6 10 2 14 11 7 15 3
13 0 13 6 11 9 4 15 2 14 3 8 5 7 10 1 12
14 0 14 7 9 5 11 2 12 10 4 13 3 15 1 8 6
15 0 15 5 10 1 14 4 11 2 13 7 8 3 12 6 9
乗算法は
ここにある.
2と4と16と...,つまり2
2nはFermat 2-powerといって, 特別の数である. 特別の数の2乗はそれを1.5倍する. 2
2=3, 4
2=6,... 特別の数同士の積は, 通常の積で計算する. 2.4=8.
0×n=0, 1×1=nである. 残りは分配則やnim addition(二進法の排他的論理和)で計算する.
こうなるかと思い, 始めの方を計算してみる.
赤字はnim additionのところだ.
2の段:
2.2=3, 2.3=2.(2+1)=2.2+2=3+2=
11+10=1, 2.4=8, 2.5=
2.(4+1)=8+2=
1000+10=10, 2.6=2(4+2)=8+2.2=8+3=11, 2.7=2(4+2+1)=8+2.2+2=8+3+2=
1000+11+10=9, 2.8=2.2.4=3.4=(2+1)4=8+4=12, 2.9=2(2.4+1)=12+2=
1100+10=14, 2.10=2(2.4+2)=12+2.2=12+3=15, 2.11=2(2.4+3)=
12+2.3=12+1=13, 2.12=2(2.4+4)=12+8=
1100+1000=4, 2.13=2(2.4+5)=12+10=6, 2.14=2(2.4+6)=12+11=
1100+1011=7, 2.15=2(2.4+7)=12+9=
1100+1001=5.
3の段:
3.3=(2+1)(2+1)=2.2+2+2+1=3+1=
10+1=2, 3.4=2(2+1)=2.2+2=
3+2=
11+10=1, 3.5=(2+1)(4+1)=2.4+2+4+1=8+2+4+1=15,
3.6=(2+1)(4+2)=2.4+2.2+4+2=8+3+4+2=
1000+11+100+10=13, 3.7=(2+1)(4+3)=2.4+2.3+4+3=8+1+4+3=14, 3.8=(2+1)8=
2.8+8=
1100+1000=4, 3.9=(2+1)(8+1)=2.8+2+8+1=
1100+10+1000+1=7, 3.10=(2+1)(8+2)=2.8+2.2+8+2=
1100+11+1000+10=5, 3.11=(2+1)(8+3)=2.8+2.3+8+3=
1100+1+1000+11=6, 3.12=(2+1)(8+4)=2.8+2.4+8+4=
1100+1000+1000+100=8, 3.13=(2+1)(8+5)=2.8+2.5+8+5=
1100+1010+1000+101=11, 3.14=(2+1)(8+6)=2.8+2.6+8+6=
1100+1011+1000+110=9, 3.15=(2+1)(8+7)=2.8+2.7+8+7=
1100+1001+1000+111=10.
すでに計算した積の値は利用している.
ところで, 上の表はこのようにして作ったものではない. TAOCPの方法を説明しよう. この方法が, なぜ上の乗算法と同じになるかは, 今は私の理解の範囲外である.
演習問題7.1.3-8に, 非負の整数の有限集合Sのminimum excludantというのがある.
mex(S) = min {k | k ≥ 0 and k ∉ S}
つまり mex({0,1,2})=3, mex({0,1,2,3,5,7})=4.
これを使い nim multiplication x ⊗ y は
x ⊗ y = mex {(x ⊗ j) ⊕ (i ⊗ y) ⊕ (i ⊗ i) | 0 ≤ i < x, 0 ≤ j < y}
で計算する.
上の図で, x ⊗ y (赤丸)を計算するには, 緑の範囲内の i と j に対して, 青丸で示す x ⊗ j, i ⊗ y, i ⊗ iのnim和をとり, その緑の範囲のすべての値のmexをとると, それが赤丸の値になるのである.
上から順に横向きにnim productが計算してあれば, 赤丸まで来たとき, オレンジ色の値はすべて分かっているから, 再帰計算はせずに済む.
mexはこう計算する.
(define (mex xs) ;関数mex
(define (mx n)
(if (member n xs) (mx (+ n 1)) n))
(mx 0))
表の(x,y)の値をとる関数を(get x y)とすると, nim productは以下のようだ.
(define (nimprod x y)
(let ((s '()))
(do ((i 0 (+ i 1))) ((= i x))
(do ((j 0 (+ j 1))) ((= j y))
(set! s (cons (bxor (bxor (get i j) (get x j)) (get i y)) s))))
(mex s)))
表の0 ≤ j < 16 の(0,j)を0, (1,0)も0にし, (1,1)から始められる. こうして作ったのが最初にあった乗算表である.
