山の八合目からの眺望:8進数で眺めると

だいぶわかってきた.ほとんど山の八合目辺りまでは登り詰めたのではないかと思う.あともう少しで頂上を踏むことができる.そのときの眺望を君は想像できるだろうか?ここまで来られたのはほとんど奇跡と言ってよい.というのは,ここまで来るまでの道筋は自力で開いたものというより,すべて「偶然」による展開であるからだ.ノード番号を16進表記するというアイディアはわたしが考え抜いた末に見出した方法ではない.モヒティのようにバイナリ操作に主要な興味があれば,その方向に進んだ可能性は十分あるが,わたしは早い時期にこのような方向を放棄している.それではなぜ「16進表記」のようなことを思いついたかというと,まさに「必要に迫られて」そうしたというに過ぎない.必要に迫られたというのは,ゼルコバの木のキャパシティ的な限界による.

ゼルコバの木は基本的に32ビットOS上のシステムなので,最大整数はInt32の範囲に限定される.カードを一意に識別するための「参照番号」には便宜的にそのノードのノード番号を流用しているが,ノード番号が巨大化してくると当然その範囲に収まらなくなるため,なんらかのハッシュ関数を使って番号を32ビットの範囲に収めなくてはならなくなった.もっとも簡単なハッシュ関数は対象となる数をNとしてN’=N mod Max とする方法だ.今の場合は,32ビット以内に収めればよいので,下位31ビットまで切り詰めればよい.

ところが,予想に反してこの簡便なハッシュ関数によって異常なほど多数のハッシュ衝突が発生することがわかったというのがその端緒である.ラマヌジャンは「わたしは女神が教えてくれた答えを声にしているだけだ」と言っているが,わたしの感覚もそれに近い.そのような「偶然」の度重なる助けがなければ,ここまで来ることはなかったと思う.

この問題の理想的な解決があるとすれば,与えられたノード番号のバイナリ表現を分節して,

ノード番号=親ノードのバイナリ表現
          +ノード固有の枝番を示すバイナリ表現

とすることだろう.これができれば,この等式を再帰的に適用することによって一意のアドレスコードを取得し,そのノードのアドレスコードつまりコラッツ木上の位置を完全に特定することができるようになる.現時点では,

ノード番号=長子ノードのバイナリ表現
          +ノード固有の枝番を示すバイナリ表現

として定式化することはできるようになったが,まだこれでは木構造を構成することはできない.「長子ノードのバイナリ表現」を「親ノードのバイナリ表現」に変換する操作を定式化する必要がある.問題は,「長子ノードのバイナリ表現」の方が「親ノードのバイナリ表現」より長い場合があるという点だ.これから見ても,

親ノードのバイナリ表現=長子ノードのバイナリ表現+X

のようなものにならないことは明らかだ.長子ノード番号Sを親ノード番号Pに変換する関数Fは以下の式で与えられる.

2^c*P=3S+1

このとき,cの値は1, 2, 4のいずれかであることはわかっているので,

P=F(S)=(3S+1)/2   c=1の場合:S=…011, …111の場合
    =(3S+1)/4   c=2の場合:S=…001の場合
    =(3S+1)/16  S=5=101の場合

のように記述することができる.非長子ノードMはすべてM=…b101のように表記される.ただしbは空ではないとする.LSB=0の場合は偶数なので除外できるから,上記で場合を尽くしていることは明らかだ.任意のノードNが与えられたときの親ノードPは簡単な計算で得ることができる.ノード番号を3進数として表記してみよう.Nを3進数として表記した場合の最大のメリットはそのノードが3倍数であることが末尾1桁を見るだけでわかるという点にあるが,もう一つ,3S+1という計算をシフトとインクリメントだけで構成できるという点がある.しかし,バイナリとターナリの混合計算というのはできないので,3進数に変換しても大したメリットは得られないような気がする.

もちろん,これらの相互変換を高速実行できるようなコンピュータが存在すれば,また別だ.かつてソ連には3進コンピュータというのがあったという…ノード番号を3進数表記したら,また別の見え方になるだろうか?やってみるだけの価値があるだろうか?実装はそれほど難しくはないと思われるが,3進数表記するとテキストが長くなり過ぎて巨大数を表示するのにはかなり無理があるような気がする…ハッシュ衝突の発生は枝数を少なくとも6くらいにしないと見えてこない.枝数6というと相当巨大な数字を扱わなくてはならなくなる…確かに末尾1桁を見ただけで3倍数であるか否かを判別できるというだけでも興味は湧いてくるが…

むしろ,8進数で見た方がおもしろいのではないだろうか?8進数で見ると,少なくとも長子→親ノード変換のパラメータが末尾1桁で決定できることになる.確かにこれは言えるかもしれない.8進数で表示すると使われるアルファベットは0~7でうち偶数を除くと,1, 3, 5, 7の4種だけだ.上の変換関数でc=1の場合というのは,末尾3と7に該当し,末尾1ならc=2ということになる.末尾が5というのが(きっかり5の場合を除き)非長子ノードであり,明快に分類できる.3S+1という計算を実施することによってDNA配列は完全に暗号化されてしまうから,それを復号化するためにはFの逆演算をやるしかない…しかし,S ⇔ 3S+1は完全に1対1対応しているので,計算自体には何の支障もない.C++にはstd::octというクラスがあるので,試してみることにしよう.

かなりいい感じだ!目で見て(計算しなくとも)長子ノードと非長子ノードが区別できるというのはうれしい.

image

長子ノードになるのは末尾が1, 3, 7の場合だが,これらのノードには特に規則性のようなものは看取できない.3倍数(ピンク)の分布も兄弟枠内で3つ置きという以外の規則性を見出すことはできなかった.3N+1を計算すれば,cがいくつになるのかはそのノードの末尾桁だけで決まるので,長子ノードから親ノードを即決で求めることができるようになった.すでに長子木というオプションは廃止してしまったが,これを見ればなにかわかることがあるかもしれない.ともかく,3本の木をもう一度復活させることにしよう.⇒その前に少しZTのバグを取っておこう.

▲人名枠幅を変えても画面に反映されない.

▲再描画ボタンを押して,GetPageCountで(treeview()->validcard && !NearZero(wholeH % GH))というエラーが発生する.wholeHは1210,GHは292で商は4,余り42だ.この誤差がどこで発生したのかが問題だ.wholeH には以下のような値が入っている.wholeH = treeview()->relative().Height() + treeview()->bottomcut bottomcutには10という値が入っている.


コメントを残す

メールアドレスが公開されることはありません。

CAPTCHA