乗算表

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²ⁿはFermat 2-powerといって, 特別の数である. 特別の数の2乗はそれを1.5倍する. 2²=3, 4²=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)から始められる. こうして作ったのが最初にあった乗算表である.