2011年1月24日月曜日

乗算表

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

2011年1月16日日曜日

TAOCP

TAOCP V4F1にこういう問題があった(7.1.3-102).

日, 時, 分, 秒, ミリ秒がそれぞれ3, 1, 1, 1, 2バイトに収まっている. 3バイトで日を表わすと, 224/365=45964年分だから, ここはどうでもいい. こういう時間データ2つを足したり引いたりする方法である. その解答の最後に「`fc81'の`c'が偶数なのは運が良かった.」とあるのはなぜか.

方法はこうである. 2つの数をxとyとする. 減算ならz←x-y, 加算ならz←x+y+#e8c4c4c4fc18とする. 分の桁でいうと, xの分とyの分を足して60になるか60を超えたとき, 256の桁に1を送りたいので, 256-60=196=110001002=#c4を足す. しかし和が60に満たない時はどうするか. 60はバイトサイズ256の半分以下なので, バイトの先頭のビットが1なら繰上げはなかった, 0なら繰上げがあったが分かる. なかった場合は先ほどの#c4を引かなければならない. 従って, 先頭のビットが1ならそのバイトを#c4に, 0ならそのバイトを0にしたものが欲しい. それは簡単だ. バイトを#80で&をとる. その1を左に1ビットシフトしたものから, その1を右に7ビットシフトしたものを引けば, 11111111か00000000になるので, これを#c4を&したものを引く. 時, 分, 秒はそれで良い. ミリ秒はどうするか.

2バイトのミリ秒の区域の先頭が1のとき, 上の伝では 11111111 0000000になってしまう. そこで, 先頭が1の時, この区域ではさらに1を引くのである. するとこの右端の1から引かれて,11111110 11111111が出来る. これとfc18の&をとることになり, うまい具合いにマスクが0になったビットは, cなので0であったわけだ.

なるほど. 運がよかった.

2011年1月15日土曜日

乗算表

乗算の九々は一旦覚えてしまえば後は何の道具もいらないはずだが, 「Napier の骨(Napier's Bones)」のような乗算用具もあるから, 九々を諳じない人も多いかもしれない.



これは以前自作したNapierの骨で, 中央に3本, 2と5と6の棒を置いてみた. 見ての通り, 各棒にはその段の九々が書いてある. 256を4倍するには, 左のIVの行に注目. /8 2/0 2/4になっている. 右端の4から, 積の1の桁は4. その分子の2と, 左隣りの分母の0を足し, 10の桁は2. さらにその分子の2と, 左隣りの分母の8を足し, 100の桁は10. すなわち1024が得られるの図だ.

つい先頃, 「Genailleの棒(Genaille's Rods)」というものがあると教わった. これは九々を図にしたものである.

6×8は以下のとおり.



左に6, 上に8と見出しがあるので, 6×8なのが分かる. 中央の箱の右に上から890123とあるが, 一番上の8が積の1の桁の8を示す. そこから左へ楔状の影があり, その先に4とあるのが積の10の桁の4を示す. その4の上と下の012...は繰上げの数で, 10の桁が4というのは, 繰上げが4と言うことだ. 一方1の桁の8の, その4の高さに2があるのは, 下から4の繰上げがあると, 6×8に繰上げを足すと, 1の桁が2になること, その左の楔の先が5になっているのは, その時の繰上げは5であることを示す.

私も小学生の上級になると, 繰上げ4を思い出しながら, ロクハチゴジュウニなどと唱えたものだが, そういう乗算表になっている.

次の図は, 4×256を示す.



2と5と6の棒を並べ, 4の段を見る. 6の棒の4の段の一番上の4から出発し左へ進む. 楔の影に入ったら, 楔の先に進む. そして通過する数字を読み取る. 従って, 4×256は下の桁から, 4,2,0,1なことが分かる.

これで分かるように, 被乗数は何桁でもよいが, 乗数は1桁である. また被乗数に同じ数字があると, それだけ同じ棒が必要で, そこにこの種の道具の限界が存在する.

棒による乗算とは別に, 棒を順に並べると, 九々の表が出来る. それが下の図だ. 九々の範囲は2から9だが, 被乗数に0もあることから, 棒には0も1もある.



棒に書いてある乗数は, Wikipediaの図などでは1から始まっているが, 乗数1はいらないので, 2から始まるのも目につく. この表も2から9である.

インターネットで探していたら, 除算表というのも見つけた. これも面白い.

2011年1月12日水曜日

乗算表

その名を聞いた人ももうあまりないであろうが, 計算機のほとんどない頃, 乗算表といものがあった. 九々の表の大親分みたいなものである.

私も詳しくは知らないが, 例えば3桁掛ける3桁というのもあったであろう. つまり000×000から999×999までの積が印刷された表である.

最後の方はこういう風だったろう.



例えば 123456×987654を計算したいなら, 下3桁 456×654の積298224を表で引く. 算盤にその298224を置く.

次に456×987の積450072を3桁ずらして足す.

298224
+ 450072
-------------
450370244

次に123×654=80442を3桁ずらして足す.

450370244
+ 80442
-------------
530812244

次に123×987=121401を6桁ずらして足す.

530812244
+121401
-------------
121931812244

検算すると,
(* 123456 987654)=>121931812224
となる. 日本人は算盤を補助に使えるから, 積が簡単に求まるのである.

私も自分で乗算表を持っていたわけではない. 立教大学の島内剛一先生がお持ちで, 見せて頂いた. 島内さんは「乗算は簡単にできるが, 乗算表は正しかったのかと一抹の不安が残る」と笑われた.

除算も出来る.
9876543210を123で割る場合を見よう. 下から6桁を外した9876と除数123を乗算表で見る.

(* 123 81)=>9963
(* 123 80)=>9840

なので, 最初の商は80, 最初の剰余は

9876543210
-9863
-----------
36543210

下3桁を外して

(* 123 298)=>36654
(* 123 297)=>36531

従って次の商は297, 剰余は

36543210
- 36531
-----------
12210

(* 123 100)=>12300
(* 123 99)=>12177

従って次の商は099, 剰余は

12210
- 12177
-----------
33

確かに,

(quotient 9876543210 123)=>80297099
(modulo 9876543210 123)=>33

要するに, 我々が十進1桁でやっていることを, 十進3桁でやっているに過ぎない. さらに長い除数で割るには, 日常で2桁以上の除数で割るのと同様に面倒である.

2011年1月3日月曜日

3色合衆国

TAOCPには, グラフの例として, 連なっている合衆国(contiguous USA)が登場する.

ある演習問題に, 3色塗分け可能な誘導部分グラフを作れというのがあった. そんなにたやすい問題ではない. 解答を見ると意外にも, カリフォルニア州とオハイオ州を除くと, 3色で塗分けられるらしい.

そこまで分かると, 実際の塗分けは, 最初の2つの色を決めれば, その後の色は次々と決るので, あっという間の作業であった.