リレー加算器

以下は夏休み工作の記である.

前回の説明通り, 全加算器は4極双投のリレー2個で実現出来る. 田中君によると, 4極双投のリレーは市販されている, というので, 秋葉原へ出かけ, パナソニック電工の12volt駆動のAHJ3241(1個270円)を8個購入した. (写真はパナソニック電工のカタログから)


スイッチは, A₀,...,A₃, B₀,...,B₃の入力用8個の他, C_{0 in}も欲しい(最下段に入れる繰上げは, 減算で必要). 始めの8つはオンオフだが, 最後のCは, 切替えなので, 全部同じ切替えスイッチ9個を購入(1個130円). LEDはS₀,...,S₃の4個の他, C_{3 out}も含めて5個購入(12volt用 1個30円)した. 従って, 合計3480円也であった.




これが組立て用の図である. 下の方に8個のリレーがあり, 上下のリレーが対の全加算器が4個配置されている. 赤が12voltの線. 青がアースである.

上が操作パネルの裏側で, 上の方にLEDが5個. その下にスイッチが二進数A用に4個, B用に4個. 下から入れる繰上げC_in用に1個配置する.

スイッチは下向きを0, 上向きを1にしたい. 裏の端子では, スイッチを上向きにすると, 中と下が接続する. 従って, 左に書いてある繰上げ用スイッチは, 上の端子が¬C_in用である.

AのリレーのA₀,A₁,A₂,A₃の端子, BのリレーのB₀,B₁,B₂,B₃の端子, それぞれ操作パネルの対応するスイッチに, B₀リレーの9と10番の端子は, スイッチC_inの¬CとCに接続する.

Aの各リレーの10番の端子Sは, 対応するLEDへ, B₃リレーの12番の端子Cは, C_outのLEDに接続する.

この図では操作パネルの方が幅狭く描いてあるが, 実際はパネルは幅が100ミリ. リレーは1個の幅が21.5ミリ, 4個で86ミリであり, リレーの方が幅は狭い.

パネルの下の方, 裏面にリレーを固定してある.

電源は, パソコン用のアダプターを利用した.

完成した加算器の写真を以下に示す. (C_outのラベルのところは, LEDの基盤取りつけネジの穴と重なってしまった. LEDの取りつけ方は最後まで決らなかったので, こういうことに.)


表側


裏側

工作は私の属している研究所の工作室で行った. 電気回路をいじるのは実に久しぶりなので, 研究所の宇夫君に最新技術をいろいろ教えて貰った. 工作後一番の感想は, 視力がずいぶん落ちていることだが, 年のことを考えるとまぁ仕方ないか.

十六進乗算表

1985年頃, NTTの電気通信研究所でLispマシンの研究をしていた. そのマシンをELISという. Eは通研 (Electro Communication Laboratories) LISはLispである.

そのプロジェクトで作られた計算機の何台かが, JAIST(北陸先端科学技術大学)にあり, 8月7日から9日にかけて, JAISTでELIS復活祭というイベントが行われた. 20年くらい前の計算機の電源を入れ, もう一度走らせてみようというのである.

同時に多くの発表もあった.

私もLispプログラマなので, お誘いを受け, 参加し, 楽しい時を過している.

そのプロジェクトの最後の時期に TAO/SILENTというのがあり, その発表の時, 当時開発メンバーが十六進法をどう読んでいたかという話題になった. つまりFAB1を「エフエイビーイチ」ではなく, フタブイのように読むのである. これは面白いと思い, 早速(十進の九々に相当する)十六進の乗算表を作ってみた.

まず読み上げ方. 数の次が標準の読み方で, 読みにくい時はかっこ内が使える.

0 レ(オ)
1 イ
2 ニ
3 サ(ミ)
4 ヨ(シ)
5 ゴ
6 ロ(ム)
7 ナ
8 ハ(バヤ)
9 ク
A タ(カ)
B ブ(ボ)
C チャ
D ド
E テ(ケ)
F フ

とりあえず, 十六進数で乗算表を作ると, 次のようになる. 九々も0と1の段がないが, ここでも2の段から始まる. 最初は十六進でもニニガシである. 横に14個並ばないので, 縦長になり過ぎたが.

2204 2306 2408 250A 260C 270E 2810
2912 2A14 2B16 2C18 2D1A 2E1C 2F1E

3206 3309 340C 350F 3612 3715 3818
391B 3A1E 3B21 3C24 3D27 3E2A 3F2D

4208 430C 4410 4514 4618 471C 4820
4924 4A28 4B2C 4C30 4D34 4E38 4F3C

520A 530F 5414 5519 561E 5723 5828
592D 5A32 5B37 5C3C 5D41 5E46 5F4B

620C 6312 6418 651E 6624 672A 6830
6936 6A3C 6B42 6C48 6D4E 6E54 6F5A

720E 7315 741C 7523 762A 7731 7838
793F 7A46 7B4D 7C54 7D5B 7E62 7F69

8210 8318 8420 8528 8630 8738 8840
8948 8A50 8B58 8C60 8D68 8E70 8F78

9212 931B 9424 952D 9636 973F 9848
9951 9A5A 9B63 9C6C 9D75 9E7E 9F87

A214 A31E A428 A532 A63C A746 A850
A95A AA64 AB6E AC78 AD82 AE8C AF96

B216 B321 B42C B537 B642 B74D B858
B963 BA6E BB79 BC84 BD8F BE9A BFA5

C218 C324 C430 C53C C648 C754 C860
C96C CA78 CB84 CC90 CD9C CEA8 CFB4

D21A D327 D434 D541 D64E D75B D868
D975 DA82 DB8F DC9C DDA9 DEB6 DFC3

E21C E32A E438 E546 E654 E762 E870
E97E EA8C EB9A ECA8 EDB6 EEC4 EFD2

F21E F32D F43C F54B F65A F769 F878
F987 FA96 FBA5 FCB4 FDC3 FED2 FFE1

これはこんなプログラムで生成する.

(for-each (lambda (a)
(newline) (newline)
(for-each (lambda (b)
(display (string-append (number->string a 16) 
(number->string b 16)
(number->string (quotient (* a b) 16) 16)
(number->string (modulo (* a b) 16) 16) " "))) 
(a2b 2 9))
(newline)
(for-each (lambda (b)
(display (string-append (number->string a 16) 
(number->string b 16)
(number->string (quotient (* a b) 16) 16)
(number->string (modulo (* a b) 16) 16) " "))) 
(a2b 9 16))) (a2b 2 16))

関数 (a2b m n) は, (m m+1 ... n-1) のリストを作る. このプログラムを多少手直しすると, 九々ではなく, フフが得られる. 長い段は途中で折り返してあるので, 要注意.

気づている人もあろうが, 九々では積が1桁の場合, ニニガシのように, 「ガ」を挿入する. 下の表も「ニニガヨ」から始まる.


こんなもの, 使えるだろうか.

ニニガヨ ニサガロ ニヨガハ ニゴガタ ニロガチャ ニナガテ
 ニハイレ
ニクイニ ニタイヨ ニブイロ ニチャイハ ニドイタ ニテイチャ
 ニフイテ

サニガロ ササガク サヨガチャ サゴガフ サロイニ サナイゴ
 サハイハ
サクイブ サタイテ サブニイ サチャニヨ サドニナ サテニタ
 サフニド

ヨニガハ ヨサガチャ ヨヨイレ ヨゴイヨ ヨロイハ ヨナイチャ
 ヨハニレ
ヨクニヨ ヨタニハ ヨブニチャ ヨチャサレ ヨドサヨ ヨテサハ
 ヨフサチャ

ゴニガタ ゴサガフ ゴヨイヨ ゴゴイク ゴロイテ ゴナニサ
 ゴハニハ
ゴクニド ゴタサニ ゴブサナ ゴチャサチャ ゴドシイ ゴテシロ
 ゴフシブ

ロニガチャ ロサイニ ロヨイハ ロゴイテ ロロニヨ ロナニタ
 ロハサレ
ロクサロ ロタサチャ ロブシニ ロチャシハ ロドシテ ロテゴヨ
 ロフゴタ

ナニガテ ナサイゴ ナヨイチャ ナゴニサ ナロニタ ナナサイ
 ナハサハ
ナクサフ ナタシロ ナブシド ナチャゴヨ ナドゴブ ナテロニ
 ナフロク

ハニイレ ハサイハ ハヨニレ ハゴニハ ハロサレ ハナサハ
 ハハシレ
ハクシハ ハタゴレ ハブゴハ ハチャロレ ハドロハ ハテナレ
 ハフナハ

クニイニ クサイブ クヨニヨ クゴニド クロサロ クナサフ
 クハシハ
ククゴイ クタゴタ クブロサ クチャロチャ クドナゴ クテナテ
 クフハナ

タニイヨ タサイテ タヨニハ タゴサニ タロサチャ タナシロ
 タハゴレ
タクゴタ タタロヨ タブロテ タチャナハ タドハニ タテハチャ
 タフクロ

ブニイロ ブサニイ ブヨニチャ ブゴサナ ブロシニ ブナシド
 ブハゴハ
ブクロサ ブタロテ ブブナク ブチャハヨ ブドハフ ブテクタ
 ブフタゴ

チャニイハ チャサニヨ チャヨサレ チャゴサチャ チャロシハ
 チャナゴヨ チャハロレ
チャクロチャ チャタナハ チャブハヨ チャチャクレ チャドクチャ
 チャテタハ チャフブヨ

ドニイタ ドサニナ ドヨサヨ ドゴシイ ドロシテ ドナゴブ
 ドハロハ
ドクナゴ ドタハニ ドブハフ ドチャクチャ ドドタク ドテブロ
 ドフチャサ

テニイチャ テサニタ テヨサハ テゴシロ テロゴヨ テナロニ
 テハナレ
テクナテ テタハチャ テブクタ テチャタハ テドブロ テテチャヨ
 テフドニ

フニイテ フサニド フヨサチャ フゴシブ フロゴタ フナロク
 フハナハ
フクハナ フタクロ フブタゴ フチャブヨ フドチャサ フテドニ
 フフテイ

この方のプログラムは, 以下の通り.

(define kana0 '
("レ" "イ" "ニ" "サ" "ヨ" "ゴ" "ロ" "ナ"
 "ハ" "ク" "タ" "ブ" "チャ" "ド" "テ" "フ"))
(define kana1 '
("ガ" "イ" "ニ" "サ" "シ" "ゴ" "ロ" "ナ"
 "ハ" "ク" "タ" "ブ" "チャ" "ド" "テ" "フ"))
(define (foo n)
(display (list-ref kana1 (quotient n 16)))
(display (list-ref kana0 (modulo n 16))))
(define (bar n)
(display (list-ref kana0 n)))

(for-each (lambda (a)
(newline) (newline)
(for-each (lambda (b)
(bar a) (bar b) (foo (* a b)) (display " "))
(a2b 2 9))
(newline)
(for-each (lambda (b)
(bar a) (bar b) (foo (* a b)) (display " "))
(a2b 9 16)))
(a2b 2 16))

リレー加算器

リレーの話だ. 運動会とは関係ない. ここでいうリレーは電気部品で, 電気信号を継続するという意味から, 和語では継電器という.

私が学生時代に所属していた研究室では, 私が研究室に入る少し前までは, 論理回路の素子はリレーであり, それを使って, ディジタル抵抗計を試作したりしていた. 従って, 研究室にはリレーが沢山あった. 物理教室の実験室には, 直流電源が来ていたから, リレーの実験は簡単で, 私も電話交換機に使う回転スイッチを回して遊んだりしたものだ.

当時, 工学部にはリレー回路の講義があった. 私は大学院生になると, 応用物理学科の磯部教授の, William Keisterの教科書The Design of Switching Circuitsによる講義に出席した. もちろん当時は, その後で私もその学科のメンバーになるとは, まったく思わなかった.

私自身は, ちょうど後藤さんがパラメトロンを発明した直後だったから, 論理回路といえばパラメトロン一点張りであり, リレーの経験はない. そこで一度リレーで二進4桁くらいの加算器を作ってみたいと思っていた.

昨年の夏だったか, 日本橋学館大学の田中君が, リレーの加算器を見せてくれたのに刺激され, 私も実現に向け, 少しずつ進んだ.

まずリレーのおさらいを少々.

リレーには働きにより3種類あり, 左からmake, break, transferという. 下の箱にワイヤが巻いてあるのが電磁石で, 電流が流れると(1の時), その磁力により, 普段(0の時)はバネで上の位置にあるスイッチが下の位置になる.

makeは0の時, 左右の回線が切れ, 1の時, 繋がる. breakは0の時, 回線が繋がり, 1の時, 切れる. transferは, 0の時, 左の回線は右の上と繋がり, 1の時, 下と繋がる. このtransferは, 切替えの時, 左の回線は一旦, 上下のいずれとも切れるが, transferには, 一旦上下両方に繋がるタイプもある.

注意: リレーの回路は, このように, 電流が流れていない時(0の時)の図を描くことになっている.


こういうリレーを想定し, 2ヶ月程前, 二進加算器のリレー回路なんか簡単さと思って, 下のように設計した.


図が左右に長いので, 途中で分割してあり, 上の図の右が, 下の図の左に続く.

一番下の桁a₀, b₀の和がs₀で, 繰上げがc₁である. 次のa₁, b₁, c₁の和がs₁で, 繰上げがc₁である. のように見る.

そして, 田中君に意見を求めたところ, 繰上げにリレーを使うと遅くなるからよくないというコメントが早速来た. そしてZuseの回路(dual-rail-carry full adder)を教えてくれた.



これがニ進1桁分, いわゆる全加算器である. 1桁のaとbと, 下の桁からの繰上c_inを足す. この入力に対し, 出力はこの桁の和outと, 上の桁への繰上げc_outである.

この回路の最大の味噌は, 繰上げに裏回路があることだ. (dual circuitという.) つまりc_inと¬c_in, c_outと¬c_outがある. 回路図では, notは上線で表現するが, htmlでは書けないので, この説明では¬を使う.

左のb=0と書いてある上が, リレーbで動く(つまりbの値の0,1で動く)リレーで, 4回路のtransferになっている. 4極双投(four pole double throw)ともいう.

右手のa=0と書いてある上がのリレーaである. aとbは上下が反対になっているが, 図を簡単にするためだ.

この他, V+には, 出力を駆動する電源を繋ぐ. (常時1になっている.)

前述のように, aのリレーもbのリレーも0の時の図なので, この時の注目すべき回線を赤線で示す. つまりこの時は, V+の1が¬c_outを1にしている. c_in, ¬c_inはいずれかが1のはずだが, ¬c_inが1なら, その先はどこにも繋がっていないので, 関係なし. c_inが1なら, 下から繰上げがあり, outを1にする.

全加算器の真理値表は下のようだ. 計算機屋なら夢の中でも書けるはずだ.

入力   出力
a b c  s c ¬c
0 0 0  0 0 1
0 0 1  1 0 1
0 1 0  1 0 1
0 1 1  0 1 0
1 0 0  1 0 1
1 0 1  0 1 0
1 1 0  0 1 0
1 1 1  1 1 0

さてZuseの回路のチェックは次のようにする. まずoutが1になる条件を調べる. aとbの組合せを4通り書き, outが1になる条件を探す. つまりoutから逆にV+かc_inか¬c_inを見るわけである. 0 0ならc=1だ. 0 1ならbの節点を上に切替えてみると, ¬c_inに辿り着くからc=0だ. このようにして書くと

     a b c
Out= 0 0 1
     0 1 0
     1 0 0
     1 1 1

が得られ, 二進3変数の和であることが分かる. 同様にして, c_out, ¬c_outも書いてみる. xはそういうcはないこと, oはcに関係なく1になることを示す.

     a b c
cout 0 0   x
     0 1 1
     1 0 1
     1 1   o

     a b c
cnot 0 0   o
     0 1 0
     1 0 0
     1 1   x

というわけで, この全加算器回路は正しいことが分かる. 繰上げが伝搬する場合, aがすべて0, bがすべて1, 一番下のc_inが1なら, 右から来たc_inは左のc_outから出ていき, aとbのリレーの動作が終った途端に一番上のc_outを1にする.

ウェブページを探したら, リレーを使って計算機を作ったという, やはり物好きな報告を見つけた.
http://web.cecs.pdx.edu/~harry/Relay/RelayPaper.htmKonrad Zuseの全加算器の説明の後, "Except for the full adder, I designed all circuits used in my computer."と書いてあるから, この加算器は誰にも真似の出来ない完成品なのであろう.

Processingで描いたこの回路のシミュレータが, http://playground.iijlab.net/~ew/relayadder/relayadder.htmlにある. (ダウンロードには多少時間がかかります.) 右下のa,b,cの枠内をクリックすると, その値の0,1が反転する.
キーボードのキーを押しても値は変わる.

再帰曲線

ドラゴン曲線に関する最初のブログ(2009年6月19日)に書いたことだが,...

左折を+, 右折を-と表示すると
+ + - + + - - + + + - - + - -
になる. 記号は15個あるが, 中央の + が最初の折り目で, その両側はもともと重なっていたのを開いたから, 並び順が中央を中心にして対象で, しかも+と-が入れ替わっている.

これを X₂ + Y₂ と書くと,
X₂ = + + - + + - -
Y₂ = + + - - + - -
である. するとこの両枝は同じなので,
X₂ = X₁ + Y₁
Y₂ = X₁ - Y₁
X₁ = + + -
Y₁ = + - -
最後は
X₀ = +
Y₀ = -
この+と-のパターンはなんだろうと思っていたが, はたと思いついたのは, Gray codeであった.

下の図は通常の二進法とGray codeの対応を示す. Gray codeの右の+と-は, Gray codeの1の数が, すぐ上のcodeのそれと較べて, 増えたか減ったかを示す. これが上のパターンと同じなのである.




なぜかというと, 枠で囲った部分がX₂とY₂で, その間が, 一番左の桁が1になったことで + になっているのである.

この図からははみ出すが, 16番のところは右から5ビット目が1になり, +となり, 24番のところは右から4ビット目が0になり, -になるのである.

一方, 通常の二進法の右の小さい丸は, 右から1ビット目と2ビット目, 2ビット目と3ビット目のように, 連続して2つの1が続く状態が現れた場所を示す.

1が連続すると, Gray codeの作り方から分かるように, 排他的論理和をとるので, 1が減るのである.

従って, -が現れるのは, 4n+3か, 8n+6か, 16n+12か, ...である.

これだけ分かるとドラゴン曲線のプログラムは書ける.

(define (test n p)
 (cond ((= (modulo n 4) 3) #f)
       ((= (modulo n 8) 6) #f)
       ((= (modulo n 16) 12) #f)
       ((= (modulo n 32) 24) #f)
       ((= (modulo n 64) 48) #f)
       ((= (modulo n 128) 96) #f)
       ((= (modulo n 256) 192) #f)
       ((= (modulo n 512) 384) #f)
       (else #t)))

山場はこのtestだ. こういつまでも書くわけにはいかないから, nがどんなに大きくてもいいように, 下のプログラムでは書き直してある.

(define (moveto x y)
 (display (number->string x)) (display " ")
 (display (number->string y)) (display " moveto\n"))

(define (rlineto x y)
 (display (number->string x)) (display " ")
 (display (number->string y)) (display " rlineto\n"))

(define limit 64)

(define (test n p)
 (cond ((> p (* 2 n)) #t)
       ((= (modulo n p) (* 3 (/ p 4))) #f)
       (else (test n (* p 2)))))

(define (foo n dx dy)
 (rlineto dx dy)
 (if (< n limit)
  (if (test n 4) (foo (+ n 1) (- dy) dx)
                 (foo (+ n 1) dy (- dx)))))
(moveto 0 0)
(foo 1 20 0)

再帰曲線

このブログにドラゴン曲線のことを書いたのは, 1年くらい前のことである.

ウェブでドラゴン曲線の画像を眺めていたら, 4つのドラゴン曲線を組合わせて, 平面を埋めている絵があった. 早速描いてみることにした. 次がその戦果である.


もちろんドラゴン曲線は角で直角に曲がるのだが, 通過の仕方が分かるように, 四角の部屋を丸く掃く居候モードで描いてある.

問題は, それぞれの色のドラゴンが重ならないかということだ.

ちゃんと証明するのは面倒だが, ドラゴン曲線をフラクタルで描くステップを考えると, 当たり前のような気がする.

フラクタルでの描き方は次のようだ.



まず0次の線を赤のように引く. 左から右に向って引いている積りだ.
次に1次の線を青のように, 赤の線分を右に三角形に膨らませるように引く.
2次の線は, 橙のように, 青の線分を最初は右に, 次は左に膨らませる.
3次の線は, 緑のように, 橙の線分を右, 左, 右, 左と膨らませる.
これを適当な次数まで繰り返す.

描画アルゴリズムとしては, n次のフラクタルを描きたいというサブルーチンで始める. 次数が0なら始点と終点を引く. そうでないなら, n-1のフラクタルのサブルーチンを呼ぶのである.


このようにして描いた, 0次, 2次, 4次, 6次は次のとおりである. 8次の図はこのブログ先頭のものだ.






重ならない理由がなんとなく納得出来たであろうか.

ついでに10次と12次の図も示すと次のとおり.

ビットの反転と置換

Hacker's DelightにもTAOCPにもSchroeppelのビット反転法の話が登場する. もとはHAKMEMの167項の一部にある話である.

Hacker's Delightでは(102ページ), 64ビットレジスタで7ビットxの反転を((x*0x40100401)&0x442211008)%255 と書いてあり, TAOCP(V4F1,26ページ),0<=x<2^gの反転をt←((ax mod 2ⁿ)&b, y←((ct)mod 2ⁿ)>>(n-g) ただしn=g², 0≤x<2^g, a=(2^n+g-1)/(2^g+1-1), b=2^g-1(2ⁿ-1)/(2^g-1), c=(2^n-g-1)/(2^g-1-1) とある.

まずDelightの方.

((x*A)&B)%255
ただし A=0x40100401, B=0x442211008 と書き直す.

このAとBを二進にする.
A=100 0000 0001 0000 0000 0100 0000 0001
つまり4つの1の間に0が9個ある.
B=100 0100 0010 0010 0001 0001 0000 0000 1000

従って 7ビットgfedcbaにAを掛けると

                              gfedcba
      1000000000100000000010000000001  A
gfedcba000gfedcba000gfedcba000gfedcba  A*x
  10001000010001000010001000000001000  Bでマスクすると
  e   a    f   b    g   c        d     これらが残る
43210 6543210 6543210 6543210 6543210  8ビット内の位置
                             11111111  28-1で割った剰余
                              abcdefg  反転出来た.

ビットに右から番号をつけるとaの位置は0, bは1, ..., gは6.
Aを掛けるとaの位置は0,10,20,30になり, 8の剰余は0,2,4,6になる. Bで6のaを取る. bの位置の8の剰余は1,3,5,7で5のものを取る. そういう仕掛けである.

TAOCPの方は, 定数に(2^p-1)/(2^q-1)が多いが, これはqビットごとの1のあるパターンを作る常套手段である.

g=3とすると, n=9. 従って

a=100010001
b=100100100
c=10101

x=rqp
これにa=100010001を掛けると
rqp0rqp0rqp
2nでmodをとると
  p0rqp0rqp
b=100100100
でマスクする
  p00q00r00
c=10101を掛けると
    p00q00r00
  p00q00r00
p00q00r00
p0pqpqrqr0r00
2nでmodをとると
    pqrqr0r00
n-gビット右シフトすると
          pqr
と反転出来る.

これは, 反転すべきパターンを位相をずらして複製し, 必要な部分を取り出し, Delightのように2ⁿ-1で割った剰余で揃えるか, TAOCPのように(割り算は出来ない)cをかけて混ぜ合わせ, 途中に出来た部分を取り出すかである.


TAOCPのやり方で, もっと一般的な置換が出来ないか考えたのが, 今回のブログのテーマである. 例として64ビットレジスタで8ビットのパターンを任意に置換する.

x=76543210 (ビットの名前)
とする.
置換は (0,1,2,3,4,5,6,7)->(3,2,4,1,6,0,5,7)
つまり75061423にしたい.

次のようにする.
a=0x8040201008040201
b=0xbfdfeff7fbfdfeff
y=(xa % 2^64) & b
c=0x0101010101010101
d=0x4020100804020100
z= ((xc % 2^64) >> 1) & d
m=0x14012000000a4080
(((y|z & m) * c) & (2^64-1)) >> 56

Schemeでは
(define (genperm x m)   ;m permutation mask
 (let* ((a #x8040201008040201) (b #xbfdfeff7fbfdfeff)
        (c #x0101010101010101) (d #x4020100804020100)
        (y (band (modulo (* x a) (expt 2 64)) b))
        (z (band (>> (* x c) 1) d)))
  (>> (band (* (band (bor y z) m) c) (- (expt 2 64) 1)) 56)))
(define m #x14012000000a4080)
実行してみると
(genperm #b11110000 m) => #b11010100
(genperm #b11001100 m) => #b10010011
(genperm #b10101010 m) => #b11001001

yはこうなる.

y=      mask
76543210 ff 64ビットの内 最右の8ビット
6543210x fe
543210x7 fd
43210x76 fb
3210x765 f7
210x7654 ef
10x76543 df
0x765432 bf 最左の8ビット x: ドントケアビット

xc>>1 はこうなる.

07654321
07654321
07654321
07654321
07654321
07654321
07654321
?7654321   ?: 右シフトで左から挿入されたビット

z= ((xc mod 2^64) >>1) & d

z=      mask
xxxxxxxx 00
xxxxxxx1 01
xxxxxx2x 02
xxxxx3xx 04
xxxx4xxx 08
xxx5xxxx 10
xx6xxxxx 20
x7xxxxxx 40

y|z は各列に0から7を1つずつ含む.

y|z & 0x14012000000a4080 <= 置換用マスク

76543210 7        80
65432101  5       40
54321027     1 2  0a
43210376          00
32104765          00
21057654   0      20
10676543        3 01
07765432    6 4   14
         75061423

0x0101010101010101を掛ける.

          7
          75
          75  1 2
          75  1 2
          75  1 2
          750 1 2
          75061 23
          75061423

modulo 2^64 >> 56 => 75061423

完成!

置換用マスクの作り方.

00 09 18 27 36 45 54 63
08 01 10 19 28 37 46 55
56 17 02 11 20 29 38 47
48 57 26 03 12 21 30 39
40 49 58 35 04 13 22 31
32 41 50 59 44 05 14 23
24 33 42 51 60 53 06 15
16 25 34 43 52 61 62 07

y|zの行列を眺めながら作った上の表は, 0を0へ移動するには0にマスクを置く. 0を1へ移動するには9にマスクを置く. ... 0を7へ移動するには63にマスクを置く. ...7を7へ移動するには7にマスクを置く. のように読む

この表は pをqに移動するマスク位置を計算するプログラムでも計算出来る.

(define (pq p q)
(cond ((< p (+ q 1)) (+ (* -8 p) (* 9 q)))
      ((= p (+ q 1)) (+ (* 8 p) q))
      ((> p (+ q 1))  (+ 72 (* -8 p) (* 9 q)))))

上の例 0->5 1->3 2->1 3->0 4->2 5->6 6->4 7->7

(number->string
 (apply +                              
(map (lambda (p q) (expt 2 (pq p q)))
  ;from pos          to pos
 '(0 1 2 3 4 5 6 7) '(5 3 1 0 2 6 4 7))
) 16)
=> "14012000000A4080"

再帰曲線

第1回のArtificial LifeのProceedings(1987年)を見ていたら, 下のようなフラクタルの絵があった.



当然どう描くのか不思議であるが, Wikipediaに85度というヒントがあったので, 描いてみたら, 何とも簡単であった.



をまず描くのである. この4本の線をまたフラクタルにすると,





と細かくなり, 何段目かで最初の図になる.



原点からx軸に沿い, 長さdの線を描くとする. その線を途中で折曲げて上のように描きたいから, まずd1を計算する. d1=d/(2+2*cos 85)なのは容易に分かる. 従ってdの線を描く代りに, x軸に沿い, 長さd1の線を描き, 原点を(d1,0)へ移し, そこで85度回転する. また新しいx軸に沿い,長さd1の線を描き, 原点を(d1,0)へ移し, 今度は-170度回転する. 後は図に従い, 同様にやる.

長さdの線を描く代りに, 短い線を何本か描くので, 再帰呼出しになっている. 当然どこかで止めなければならない. nなるパラメータを1つ用意し, 下請けを呼ぶ時, nを1引く. nが0で呼ばれたら, dの直線を直接引く.

PostScriptのプログラムは以下の通り.

/draw {4 dict begin
/n exch def /d exch def %パラメータを取り込む
n 0 gt                  % n>0なら
{/d1 d 85 cos 1 add 2 mul div def /n1 n 1 sub def
gsave                   %環境を待避
d1 n1 draw
d1 0 translate
85 rotate
d1 n1 draw
d1 0 translate
-170 rotate
d1 n1 draw
d1 0 translate
85 rotate
d1 n1 draw
grestore}               %環境を回復
{0 0 moveto d 0 lineto stroke} ifelse end} def % n=0なら直接描く

40 40 translate
400 6 draw              %起動

最終の姿は, 予想もしないものだ.