2011年6月30日木曜日

多面体描画道楽

Archimedesの多面体はまだsnub cubeとsnub dodecahedronの2つが残っている. 今回は前者 変形立方体に挑戦.

元は立方体である. その各面の正方形を縮小し, どちらかに多少回転する. その方向により, 2つの相対の形がある.

どのくらい縮小するか, どのくらい回転するかを計算しなければならない. そこで次の図のように考える.



3つの似たような図があるが, 上が平面図(z方向から見た), 右下が側面図(y方向から見た), 左下が正面図(x方向から見た)である.

この立体は6の正方形と32の正三角形で被われる. 正方形と正三角形は辺を共有するから, すべての辺は同じ長さになる. それをdとする.

また, 座標の中心を立方体の中心にし, 立方体の1辺の長さを2とすると, A, B, C, Dの座標はそれぞれ

A(1,a,b)
B(1,-b,a)
C(a,b,1)
D(b,-a,1)

である. ABの距離の2乗はd2=(a+b)2+(a-b)2=2a2+2b2.

ACの距離の2乗はd2=(1-a)2+(1-b)2+(a-b)2.
従って, a+b+ab=1.

ADの距離の2乗はd2=(1-b)2+(2a)2+(1-b)2.
従って, 2b-a2=1, b=(1+a2)/2.

このbを上の式に入れると, a3+a2+3a=1. 3次式だから, 実数解はあるはずと思い, WolframAlphaの解いてもらうと, a=0.295598, 従ってb=0.543689, 念のため a+b+abを計算する.

(define a 0.295598)
(define b 0.543698)
(+ a b (* a b)) => 1.0000120414040001

計算は存外簡単であった. 球に内接の件は, どの頂点の座標も, 1とaとbで出来ているから, 当然である.

これさえ分かれば, 変形立方体を描くのはわけけない. いや1点落とし穴があった. 手前の面の座標から, 向こうの面の座標を得るのに, ついyz軸面の鏡面対称を使ったが, 正方形がが傾いているから, z軸に対して180度回転しなければならなかった.



ところで, Archimedesたちが, こういう形になぜ気づいたかは不思議だ.

2011年6月29日水曜日

多面体描画道楽

Archimedes多面体には, もう1つの二十・十二面体がある. 英語ではtruncatedicosidodecahedronとかgreat rhombicosidodecahedronという. 日本語では切頭二十・十二面体であろう. 図を描くのは存外難しかった. (いや, さらに難物が今後に控えている.)

これは正十二面体の12の正五角形を正十角形にし, その隙間に20の正六角形と30の正方形を詰めたものである.

まず, 正五角形に内接する正十角形を作らなければならない. それには, 下の図のように考える.



左のPOは, もとになる正十二面体の1つの正五角形を横(y軸)方向から見たものだ. この下の稜線上にx方向から見える正方形があり, その1辺の長さを2xとする. このxは, 正五角形の面内では, yの長さになる. 面のなす角をαとすると, y=x/sin αだ. 但し, tan α=(3+√5)/(1+√5).

右は, 正五角形の右下を法線方向から見たものだ. Aの所に54°の三角形があり, その縦はy+x sin 36°, 横はOAが1だから, 1-x-x cos 36°であり, この比がtan 54°なので, xが解ける.

この代表の正十角形の各点のx, y, z座標は

x y z
0 2.4180339887498947 -.3236067977499789 .32360679774997897
1 2.218033988749895 -.8472135954999578 .6472135954999579
2 1.8944271909999162 -1.0472135954999577 1.1708203932499366
3 1.5708203932499372 -.8472135954999578 1.6944271909999156
4 1.3708203932499372 -.32360679774997897 2.0180339887498944
5 1.3708203932499372 .3236067977499789 2.0180339887498944
6 1.5708203932499372 .8472135954999578 1.6944271909999156
7 1.8944271909999162 1.0472135954999577 1.1708203932499366
8 2.218033988749895 .8472135954999578 .6472135954999578
9 2.4180339887498947 .3236067977499789 .3236067977499789


と計算出来る. Archimedesの多面体も, 各頂点は球に内接するから, 上の座標からx2+y2+z2 を計算したのが下だ.


0 2.4609614157580197
1 2.46096141575802
2 2.46096141575802
3 2.4609614157580197
4 2.4609614157580197
5 2.4609614157580197
6 2.4609614157580197
7 2.46096141575802
8 2.46096141575802
9 2.4609614157580197


まぁ, よかろう. あとは隙間の面を指定するだけである.

そうして描いたのがこの図である.

2011年6月19日日曜日

多面体描画道楽

Archimedes多面体というのがある. 切頭八面体とか切頭二十面体とかはその仲間だ. その中に, 斜方二十・十二面体という長い名前のものがあった. 英語ではrhomb icosi dodecahedronという. rhombが斜方, icosiが二十, dodecaが十二, hedronが面体の単数だ.

これば難しそうだ. 図面を何日も眺めたが, アタックの入口が見つからない. 空しく過しているうちに, やっと解決の糸口が見えてきた. 次の図で説明しよう.



左は正十二面体をx軸方向から見たもので, 真下のXと書いた上の点がX軸である. 右はそれをy軸方向から見た図である.

斜方二十・十二面体には, 五角形が12, 四角形が30, 三角形が20ある. 一方, その元になる正十二面体は, 面Fが12, 頂点VがHamiltonianの巡礼で分かるように20, 辺Eが30ある. Eulerの式 V+F=E+2である.

つまり, 五角形は面が, 四角形は辺が, 三角形は頂点に対応している.

正十二面体の頂点は, 3つの面が合わさっているから, それを削っていけば, 三角形が現れるが, それでは五角形が十角形になる切頭十二面体が出来るだけである.

下の左の図で, 正五角形ABCDE(面が傾いているから, 上下がつぶれて見える)を中心に向って縮小すると, 下の辺と下にある五角形の対応する辺で作る四角形が正方形になる時点があるはずで, その時, 同じ辺の長さを持つ正五角形A'B'C'D'E'と正方形が出来る.

というわけで, A', B', C', D', E'の右方向へのy座標と, 上方向のz座標が計算出来る. 各点のz座標が分かると, 右の図のようにして, x座標も決る.

AEの距離を2とした時, A',B',C'の座標は次の通りである.



こうして描いた多面体は次の通り.



もっともらしいではないか.

2011年6月14日火曜日

ビットスワップ

MOR命令4つで完全シャッフルをするのは超絶技巧だ. Schemeで書いたMORのシミュレータを使い, 実際にシャッフルしてみる.

MMIXのMORは$Yと$ZをMORして$Xに置くが, Schemeは関数なので, MORした値を返す.

まず行列の転置の関数がいる.

(define (tr m) ;行列mの転置
(map (lambda (i)
(map (lambda (b) (list-ref b i)) m))
(a2b 0 (length (car m)))))
;(tr '((1 1 1 1) (0 0 1 0) (0 1 0 0) (1 1 1 1)))
;=>((1 0 0 1) (1 0 1 1) (1 1 0 1) (1 0 0 1))

真理値に0,1を使うor関数もいる.

(define (or x y) (quotient (+ x y 2) 3))
;(or 0 0)=>0, (or 0 1)=>1, (or 1 0)=>1, (or 1 1)=>1

するとmorは

(define (mor y z)
(let ((zb (map (lambda (n) (n2bs n 8)) (n2bytes z 8)))
(yb (tr (map (lambda (n) (n2bs n 8)) (n2bytes y 8)))))
(bytes2n
(map bs2n
(map (lambda (z)
(map (lambda (y)
(fold-right or 0 (map * z y))) yb)) zb)))))

と書ける. (n2bs n w)は整数nをwビットのリストにする. n2bytesはバイトのリストにする.

あと, MUX関数も必要だ.

(define (mux m y z)
(let ((ms (n2bs m 64)) (ys (n2bs y 64)) (zs (n2bs z 64)))
(define (mx m y z)
(if (null? m) '()
(cons (if (= (car m) 1) (car y) (car z))
(mx (cdr m) (cdr y) (cdr z)))))
(bs2n (mx ms ys zs))))

この準備のもとで, 完全シャッフル関数は

(define (perfectshuffle z)
(let ((t (mor z #x8008400420021001)) (u 0))
(set! t (mor #x8020080240100401 t))
(set! u (mor t #x4080102004080102))
(set! u (mor #x4080102004080102 u))
(mux #xaa55aa55aa55aa55 t u)))

である. どのビットがどこへいったかを調べるには,

(define bin '(
#xffffffff00000000
#xffff0000ffff0000
#xff00ff00ff00ff00
#xf0f0f0f0f0f0f0f0
#xcccccccccccccccc
#xaaaaaaaaaaaaaaaa))

を次々とシャッフルし, 結果を二進法で出力する. それには

(define (bs x)
(substring (number->string (+ x (expt 2 64))2) 1 65))

を使う.

(map (lambda (n) (display (bs (perfectshuffle n))) (newline))
bin)

をやってみると,


が得られる. つまり, 左から元の位置は63, 31, 62, 30,...,32,0であったことが分かる.

2011年6月13日月曜日

ビットスワップ

TAOCP V4F0にはビット交換の技法がいろいろ書いてある. その大方の仕掛けはδスワップだが, TAOCPのベースのRISCマシン, MMIXにはMORとMXORという大形命令が存在し, それを巧みに利用する例題も多い.

これらの命令の説明はややこしく, なかなか覚えられないが, 今回のブログはその機能を覚えるためのものでもある.

MORはmultiple orのことで, 命令MOR $X, $Y, $Zは, 64ビットのレジスタ$Yと$Zのビットに演算を施し, レジスタ$Xに置くものである. TAOCP V1F1では,

m($X) ← m($Z)vxm($Y)

と説明する. レジスタ$Zと$Yの順が命令での順と逆なことに注意. この演算は, 64ビットレジスタをそれぞれ8ビットの行が縦に8行並んだ8 × 8の行列とみて, 2つの行列の乗算のような演算をするのである.

行列の乗算では, 積のi,j要素は, 被演算子の左の行列のi行と, 右の行列のj列の要素を次々と掛けて全体を足すのであった. それを2つの行列の間の演算+xで表わす.



今は要素は0か1である. それを次々と掛けて全体のor(v)を取るのである. MXOR命令は全体のxorを取る.

使い方の例として, TAOCPには
$Z = #0102040810204080
とすると, $Yのバイトの順が逆になるというのがある. つまり(abcdefgh)256が(hgfedcba)256になる. それを説明するのが, 次の図の上だ.



まず$Xの左上, X0,0は, $Zの0行目, 000...01と$Yの0列目のそれぞれを掛けるが, 1が最後にしかないので, ここに来るのはhのバイトの左端のビットである. その右隣りX0,1も, 同じ0行目と掛けるから, hのさっきのバイトの右隣りになる. 同様にした結果, $Xの0行目はhのバイトになる.

$Xの1行目は, $Zの1行目が000...10, つまり最後の1つ前にだけ1があるから, gの行が来る.

hの行が0行へ移った理由を再確認すると, Zの0行目の1が右端にあるからだ. つまり0行目へ置きたい$Yのバイトの位置を1にする. 赤矢印が0行目へ来るバイトの位置を示す.

そういう次第で, このパターンを使うと, $Yのバイトが逆転するのである.

下の図は左右逆転, つまりバイトの順は同じだが, バイトのビットを逆転する方法を示す. 上と同じで, $Xの0列目は, $Yの0列目の最後だけが1なので, hの各ビットが移動してきて, hになる. そして結局左からhgf...aと並ぶ.

ビット交換では, Yの0列の1の位置がXの0列に持ってきたいビットの位置である. (赤矢印)


これだけ分かると, V4F0にある完全シャッフルの問題(演習問題7.1.3-204)が解ける.

64ビットのレジスタzは

z = (x31...x1x0y31...y1y0)2

である. それを

w = (x31y31...x1y1x0y0)2

にしたい. ヒントがあって,

t = (x31x27x30x26x29x25x28x24y31y27y30y26y29y25y28y24...
    x7x3x6x2x5x1x4x0y7y3y6y2y5y1y4y0)2

u = (y27y31y26y30y25y29y24y28x27x31x26x30x25x29x24x28...
    y3y7y2y6y1y5y0y4x3x7x2x6x1x5x0x4)2

を中間結果とし, tとuを

MOR t,z,p; MOR t,q,t; MOR u,t,r; MOR u,r,u;

で作り,

PUT rM,m; MUX w,t,u;

とすると, 6命令で完全シャッフルが出来る. パターンp, q, r, mは何かという問題である.

このうちMUX命令は多重化マスクレジスタrMを見ながら, そのビットが1の所は$Yから, 0の所は$Zからデータを取る. PUT rM,mはパターンmをrMへ設定する命令だ. そうすると,

w31はx31にしたいからtから取る.
w30はy31にしたいからuから取る.
w29はx30にしたいからtから取る.
...
28まで行くと, 取るレジスタが交代する. 従って, 1010101001010101の繰り返しになるのだ. m = #aa55aa55aa55aa55


さて, zとtとの関係は, 次の図の上半分にある通り. バイトの交換とビットの交換をしている. 命令列の最初はMOR t,z,p;なので, $Zの方がパターンになり, バイトの交換だ. バイト位置の0,1,2,3,4,5,6,7に持ってきたいのは, それぞれ0,4,1,5,2,6,3,7だから, 下に示す行列のようになり, p = #8008400420021001でよかろう.



次の命令はパターンが$Yにあるから, ビット交換である. ビットの取り先は同じ関係だが, 縦と横が違うから転置のパターンにしなければならない.



q = #8020080240100401.

最後にtからuへの変換も, バイト交換とビット交換になっている. これはどちらも隣り同士の交換なので, パターンは同じである.

r = #4080102004080102.

TAOCPの演習問題には解答があるから覗いてみると, 正解であった.

2011年6月6日月曜日

Banbury Road

前のブログ(グラフの描き方)に英国の道の図を載せた.

それにBanbury Rdの表示がある. Banbury RoadはOxfordから北の方Banburyへ行く道である. さらに北へ進むとCoventryへ至る.

英国の初期の計算機研究の中心はもちろんCambridge大学のComputer LaboratoryとOxfordのComputing Laboratoryであった. まぁEdinburghとかNew Castle upon TyneとかManchesterとかImperial Collegeとか他にもあるにはあるが.

CambridgeはWilkes. OxfordはLeslie Foxがリーダーであった.

私は1971年にIFIPの会議でWarwick大学へ行ったとき, OxfordのChristopher Stracheyがいて, 当時のMiniの後の座席に私を押し込み, 助手席にBrian Randellを乗せ, 大柄な自分も運転席へ潜り込むように乗り込み, John Buxtonの1400年頃に出来た家へ, 田舎道を走った.

ところで, そのBanburyという町は, Mother Gooseの詩

Ride a cock horse to Banbury Cross
To see a fine lady upon a white horse
With rings on her fingers and bells on her toes
She shall have music wherever she goes

で有名である. Banbury Crossは十字路ではなく, 十字架というか, 記念碑である. 私は1998年, Oxfordにいったついでに, Banburyまで列車で行き, Banbury Crossを見てきた.

Baring-GouldのThe Annotated Mother Gooseによると, このa fine ladyはElisabeth I女王か, Coventryが近いのでLady Godivaかとか書いてあるが正確なことは分からない.

Coventryには町の中心にLady Godivaの像がある. また私がBanburyに行った時はなかったが, いまはCrossの近くに, a fine ladyの像があるらしい.

Banbury Roadという住所に思い出があるのは, 1974年に私が訪ねたころの, Oxford大学のComputing LaboratoryがBanbury Roadの何番地かにあったからだ. 大学の研究所とは思えない, 普通の家であった. そこで, StracheyとJoe StoyのOS6をコピーを手にいれた. その後, Computing Laboratoryは, 大きなビルに移転し, Banbury Roadとは無縁になった.

今でもBanbury Roadは懐かしい道だ.

2011年6月5日日曜日

曜日の計算

5月25日の私のブログにある2番目のh(m)の表は

m 1月 2月 3月 4月 5月 6月 7月 8月 9月10月11月12月
h 2 5 5 8 3 6 1 4 7 2 5 0

となっており, 1月2月は別として, 3月以降は奇数月の値は奇数, 偶数月に値は偶数になっていて, 一見美しい. だが待てよ. 大小の月は, 大体交互だが, 7, 8月と大の月が並ぶ. さてはこの表は間違っているかと一瞬疑った.

ある月が小の月, 30日だと次の月は 30 mod 7=2だから, 2だけ増え, 大の月, 31日だと31 mod 7=3だけ増えるはずである. そうすると小の月の後では偶奇は変らず, 大の月の後では変るはずである. しかし, 奇数の除数7で mod 7を取っているので, 商が1増えた時, 今の関係は反対になるわけだ.

3月を5, 4月を8にしたことが, 効いているかも知れないが, どこで商が増えるかにも注意して, もう一度きちんと計算してみたい.

その結果が次の表である. Aの行は月, Bの行はその大小. Cは3月を5として, 大の月には3, 小の月には2を足したものである. ところどころの赤の縦線は, 7のmodを取ると, その前で商が1増えることを示す. DはCの偶奇を示す.



さて, 前回述べたように, 7のmodをとるについて, 4月の1は8に, 9月の0は7にした. 従って, Eの行に示すような値になり, 商が増える場所を赤の長い縦線で示す. FはEの偶奇である.

この赤線で囲まれた区間は, 交互にDの偶奇と同じ, 反対を繰り返す. つまり3, 4月はDとFは同じ, 5, 6月は反対, 7, 8, 9月は同じ, 10, 11月は反対, 12月は同じである. この区間の境界は, Dの行で, 偶偶, 奇奇と並んでいる間にある. 従って, Fの行では偶奇が交互に現れるのであった.

要は4月を8, 9月を7にして, 商の増えるのを1ヶ月遅らせたところに, 仕掛けがあったのだ.

こう検討してみると, あの表はいよいよ忘れ難くなるわけだ.

2011年6月4日土曜日

グラフの描き方

Frank HararyのGraph Theoryに下のような図があり, 読者を悩ませる. つまり頂点の黒丸が小さいので, 中央の線の集まったところに頂点があるようなないような.




説明を読むと, 上のFig.12.8はA uniquely 3-colorable graph having no triangles, 下のFig.12.9はA uniquely 3-colorable planer graphだから, 上は頂点なし, 下は頂点ありだ.

回路図の上で線が交差する場合, そこが接続されているか, 別の線なのかを表わすのに, 下のA, B2つの流儀がある.



どちらも左は別の線, 右は接続である. 用心深い人は, 接続には黒丸をつけ, 別線の時は飛び越えるように描く. 私は, 接続する場合は丁字に描き, 十字路は別線とするようにしていた.

英国の田舎の道は, 細い道が太い道と交わるとき, 細い方が必ず少し食い違いになっていて, 停車せず突っ切れないようになっている. 私のやり方と同じである. 都会の横断歩道にもそんな感じだったりする.



しかし, 私の流儀は回路図だから出来るので, グラフ理論では, 次数3の頂点までしか表示出来ず, 実用にならぬ.

例えば, 別の線が2本以上, 1点で交わらないように描くというのはどうか. 上の図の中央のW9のようなところを, そのように描いたのがこれだ.



描いてはみたが, センスあるとは申せない. もう1工夫必要だ.

最初の図は, uniquelyに3色塗り分け可能という. どう塗り分けられるか. 以前のブログのプログラムを使って, 塗り分けたのが下だ.




ところで, 上の図は, 中央に頂点があっても3色塗り分け可能である.



この程度に頂点がしっかり描いてあれば, 悩むことはないのだが.