乗算表

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)から始められる. こうして作ったのが最初にあった乗算表である.

TAOCP

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

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

方法はこうである. 2つの数をxとyとする. 減算ならz←x-y, 加算ならz←x+y+#e8c4c4c4fc18とする. 分の桁でいうと, xの分とyの分を足して60になるか60を超えたとき, 256の桁に1を送りたいので, 256-60=196=11000100₂=#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から引かれて,11111110 11111111が出来る. これとfc18の&をとることになり, うまい具合いにマスクが0になったビットは, cなので0であったわけだ.

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

乗算表

乗算の九々は一旦覚えてしまえば後は何の道具もいらないはずだが, 「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の桁が２になること, その左の楔の先が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である.

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

乗算表

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

私も詳しくは知らないが, 例えば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桁以上の除数で割るのと同様に面倒である.

3色合衆国

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

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

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

進んで戻って

いよいよ年末が迫る. 元日からの通日は360+αまで来た.

ずいぶん前になるが, 365歩のマーチという曲があり, その中に「3歩進んで2歩さがる」という文句があった. これを聞いて, 昼間に2メートル登り, 夜間に1メートル滑り落ちるカタツムリが, 地上から5メートルの電柱を登りきるのに何日かかるかというクイズを思い出す向きもあろう.

TAOCP V4F3に
"To take one step forward, take two steps forward, then one step backward; to take two steps forward, take one step forward, then another"
という禅問答のような記載があり, 私も直ぐには悟りえず, しばし悩んだことがある.

順列組合せと一緒にしていわれることが多いが, 組合せは, 0,1,...,n-1のn人から, s人を選ぶ方法のことである. これはn - s = t人を選ばない方法でもあるから, TAOCPでは(s,t)組合せという.

つまり, 0号室と1号室があり, 0号室の人数をs, 1号室の人数をtとする. 0番君からn-1番君のそれぞれが, どちらの号室にいるかを, nビットの二進数で表わす.

当然_s+tC_s=_s+tC_t組が作れるわけだ.

その組合せを書き出すのに, 常識的には辞書式順, あるいは昇順に並べる. 次は(3,3)組合せの例である.




この図の赤点は, 前後の組合せで異なる位置を示す. 二進数の位置を右から0,1,2,...とすると, 始めの方の最初の赤点は, 000111から001011になった時に, 2番君が1号室から0号室に, 3番君が0号室から1号室に移ったことを示す. 右下の最後の組合せの下に6つの赤点があるのは, 111000から最初の組合せ000111に戻るには, 全員が部屋を移る必要があるということである.

かくも大勢が右往左往しては, ドア回りが混雑するので, 回転ドア方式を考えた人がいる. 0号室と1号室の間に回転ドアがあり, 回転ドアを通って1人ずつだけが入れ替わるのである.



すなわち, この図で見るように, 赤点は常に2個である. なかなかうまく出来ている.

これは6ビットのGray codeを作り, 1のビットが3個のものだけリストして作った.

(define (gray bs)
 (define (xor a b) (modulo (+ a b) 2))
 (map xor bs (cons 0 (reverse (cdr (reverse bs))))))

(for-each (lambda (n) (for-each display n) (newline))
 (filter (lambda (x) (= (apply + x) 3))
  (map gray (map (lambda (n) (n2bs n 6)) (a2b 0 64)))))

ところでよく見ると, この赤点の間隔はいろいろだ. 2つ隣り同士のところが10, 間が1個空いているのが4, 2個空いているのが4, 3個空いているのが2で計20である.

この間の幅を0と1にしても出来るといい出した人がいるらしい.

がその1例である. 最後から最初に戻るのは別として, 途中の赤点はすべて隣り同士か1個空きである. このパターンをA₃₃という. しかし, こういうパターンはこれだけでなく, 次のB₃₃もそうなっている.


途中には目をつぶると, A₃₃は111000から始まり, 011100で終る. B₃₃は111000から始まり, 001110で終る. 一般にA_stは, 0がs個, 1がt個から始まり, 0が1個, 1がt個, 0がs-1個で終り, B_stは, 0がs個, 1がt個から始まり, 0が2個, 1がt個, 0がs-2個で終る.

AとBの漸化式も知られている.

A_st = 1B_s(t-1), 0A_(s-1)t^R;
B_st = 1A_s(t-1), 0A_(s-1)t.

これを図で示すと次のようになる. いまはs=t=3である.



左の組合せは, は下の黒文字の説明にあるように, B₃₃である. 上の漸化式に当てはめると, B₃₃ = 1A₃₂, 0A₂₃.

つまり, 左のB₃₃は, A₃₂の前に1を置いたものを並べ, 次にA₂₃の前に0を置いたものを並べると読む. 1や0の後に置く部品の組合せは赤で囲んである. 説明も赤文字である.

また, A₃₃ = 1B₃₂, 0A₂₃^R.

つまり, 右のA₃₃は, B₃₂の前に1を置いたものを並べ, 次にA₂₃の, 右肩にRがついているから, 上下逆転したものの前に0を置いたものを並べると読む.

たしかに左の下半分のA₂₃と右の下半分のA₂₃^Rは, 上下が逆である.

改めて右のA₃₃を見ると, 最初の111000は最後は011100になり, 111は右へ1歩進んだ. B₃₃では, 111は右に2歩進んだ. 部品を見るとA₃₂は11が右へ1歩進み, A₂₃は111が右へ1歩進み, B₃₂は11が右へ2歩進む. 右下のA₂₃^Rを上から下へ眺めると, 今度は01110が11100になるから, 111が1歩戻ったことになる.

これが最初の「一歩進む(A_st)には, 二歩進み(B_s(t-1)), 一歩戻る(A_(s-1)t^R). 二歩進む(B_st)には, 一歩進み(A_s(t-1)), もう一歩進む(A_(s-1)t)」の謎解きであった.

私がこの解釈に気づいたのは, 2008年の1月頃であった, 2008年の夏にKnuth先生に会った時, 「あの2歩前進, 1歩後退の意味は, 苦労したがついに分かった.」と報告した. Knuth先生は笑っただけであった.

微分解析機

今回は微分解析機といっても, トルクアンプ, 日本語では回転力増幅器の, それも図の話である.

微分解析機の積分機の出力は, 摩擦で生じる微少な力なので, これで他のものを駆動することは出来ない. ところがNewmanにより, トルクアンプが発明され, それによって微分解析機は実用になった.

トルクアンプは, 下の図のような構造である.



右のinputの軸の回転を, 左のoutputの軸から力を増幅して取り出すのである. その間にロープを書けたドラムが2組あり, ロープの端は, 入力と出力軸に取りつけたT字状のレバーの先に固定されている. ドラムは両端のプーリーにかけたベルトで, 矢印の方向に, 逆方向に回転している. 入力軸が回転しない時は, ロープはドラムの面を滑っている.

今, 入力軸が, 右に回転したとする. そうすると, 下のT字状のレバーが持ち上がり, 左のロープがドラムの上で締まり, ドラムとの間に摩擦が生じ, 上のT字状のレバーが押し下げられ, 出力軸が入力軸と同じ方向に回転する. 回転角が同じになれば, ロープは弛み, 再び滑り出す.

入力軸が反対に回る場合は, 右のドラムの摩擦が生じ, 出力軸はやはり入力軸と同回転する.

つまり, 回転するドラムが動力になり, 入力の微少な力を増幅するのである.

こういう仕掛けは船の碇を巻き上げる装置にもあるらしい.

さて, 上のような図で説明したが, 私としては, ロープを直線で描いたのが気に入らないのである. 図はなるべく正確に描きたいというからには, このようにドラムの縁で光の反射のような図はだめである.



そこで考えたのがこの図である. 上と下のT字状のレバーにロープが繋がっている点をAとEとする. 図の円はドラムの断面である. ロープは, AからBに至ってドラムに接し, BCDFBCDとドラムを1回とすこし回り, Dから離れてEでもう一方のT字状のレバーに辿り着く. 先ほどの図は, これを左から見たものだ. そうすると, ロープ上の点は, Aから下がり, ドラムの円の右半分を上がり, また下がるように見えるはずである. また左右の座標位置は, ロープの長さに比例して右へ移動するはずである.

その移動の様子を, 半径の右の, 点の列で示す. 赤はロープのAからBに対応する. 緑はBCDFBCDに対応, 最後の青はDからEである.

そういう解釈で, 最初の図を描き直すと下の絵になる.



ざっと見ると最初の図と左程違わないが, ドラム回りのロープは本当らしくなったのではないか.