コラッツ木上の任意の整数ノードに一意のアドレスを与えるユニバーサルコードシステム

コラッツ木上の偶数を含む任意の整数ノードに一意のアドレスを与えるユニバーサルアドレスコードシステムを確立した.これは,コラッツ予想問題が実質的に完全に解かれたことを意味する.実装はほぼ完了して,コラッツ数列取得・枝番→番号変換,幹線木図ではすでに動作しているが,検証テストではまだ不具合が発生している.どこかに未整備のところが残っている模様だが,シューティングは難しくないはずだ.不一致が発生しているのはN=3のケースだ.

検証テストではテストのたびにStart numberを更新し,その値から検査を実施しているが,このテキストボックスの内容が更新されていない.これを行うのは枝番→番号変換だが…コラッツ数列取得では3のアドレスを(1.1)と出力している.これは正しい.また,枝番→番号変換ではこのアドレスから3を計算している.⇒いや,手抜かりがあるのは枝番→番号変換ではなく,コラッツ数列取得の方だ.枝番号リストが空になっている.⇒検証テスト中,枝番号列が更新されていない.⇒対処した.

動作するようになったが,いきなり遅い.なぜだろう?実行速度にここまで影響するような処理は追加していないつもりだが…コンソールにダンプを出していた.⇒2^5は一瞬で完了するようになった.2^13では14秒掛かっている.以前は10秒内外で完了していたような気がするのだが…リリース版に切り替えても速くならない…検証テスト中不要な処理を止めてもさして効果は出ない.完全木では15秒掛かっている.まぁ,こんなものと思うしかないだろう…

検定を偶数を含めた整数全体に拡張してみよう.これは結構興味深いテストだ.一般木で17秒掛かった.完全木で19秒だ.検証テストの出力では一般木と完全木のトポロジーは完全に一致する.実際,一般木と完全木では同一のアドレスコードを適用しているのだから,同じにならなければおかしい.逆に言うと,少なくともB面では一般木と完全木を区別する必要がなくなったと考えられる.完全木には2倍数と3倍数は含まれないので,A面では一般木と完全木は完全に区別される.

ここまでやった以上,A面出力に全体木というオプションを追加することが考えられる.全体木とは偶数を含むすべての整数をノードとするコラッツ木だ.一つの奇数ノードの下に無数の偶数ノードがぶら下がることになるので,図面的にはやや冗長なものになる可能性はあるが,出力する意味はあるのではないだろうか?試してみる価値はあるような気がする.仕様の拡張になるが,B面の検証テストには奇数のみ/すべての整数というオプションがあってもよいと思う.

1-6-4 460点の一般正則木を生成して,最大数の6949574919509が孤立点になった.このノードのアドレスは 4. 4. 4. 4 でコラッツ数列は

6949574919509→5090020693→7456085→5461→1

5090020693というノードがグラフから落ちている.CSVファイルには入っている.この図面は6-正則木なのですべてのノードが枝を6本持たなくてはならないところだが,一部のノードは数が少なくなっている.カード数は460で上限にはほど遠いが,カード番号はInt32の範囲に入らなくてはならないため,どこかでカットされているのではないだろうか?しかし,最大数が6949574919509でそれ以上の数がないとしたら,おかしい.6949574919509は画面に表示されているのだから…⇒ゼルコバの木の一覧表フォーマットファイルには入っている.このファイルには511点のカードが登録されている.一覧表のインポートで失敗しているのだろうか?

インポートファイルはShift-JISとして処理されている.また,デリミタはカンマになっている.SJISに変換したものを読み直してみたが同じだ.ファイルは読み込まれ,レコードはDLLに送られているが,DLLで失敗しているのだろう.そこまでは情報はすべてテキストで受け渡ししているため,損なわれていないが,データベース登録のところで整数化する時点で落ちているのだろう.巨大数を読み込んで整数範囲に収まるように圧縮するようなうまい方法はあるだろうか?番号の重複を無視すればそのような方法は複数考えられるが…これは結局ハッシュということと意味的には同じと考えられる…もし,ゼルコバの木コラッツ特注版を本気でリリースするというのであれば,この対策は必須ではないか?

レコードを送っているのは,Z.mSendRecordDataという関数だ.mSendRecordDataでは受信テキストを最長256文字の語句に分割して送り出している.受けているのはSendUpdateDataという関数だ.参照番号への変換は, long long(atoi(item[_REFNUM]))で実行される.atoiには類似関数として,atol, atollがある.まず,これらを試してみよう. “3379676501”という値が,-915290795に変換された.この値は16進でC971C555となるので最上位ビットが1になり,負値とみなされる.最大数の6949574919509はこれよりもっと大きいので到底longには入らない.さて,どうしたらよいか?longをulongに変えても1ビットしか増えないので焼け石に水だ.Int64というのはC++ではlong longに該当する.ゼルコバの木を64ビット対応に再編成できれば,それも不可能ではないが,いま即応するというのは無理だ.やはり,ハッシュで切り抜けるしかないのではないだろうか?方法を考えてみよう.

  1. 参照番号がlongの範囲内である場合は,現行通りとする.
  2. 参照番号がlongより大きい場合には,ハッシュ関数を呼び出して新参照番号の割当を受ける
  3. ハッシュ関数には,参照番号の計算値Nと氏名文字列Tを渡す
  4. Tという名前を持つカードがすでに存在する場合には,その番号を返す
  5. 無登録の場合には,Nを縮小してlongの範囲内の数値N’を得る
  6. N’という参照番号が登録されている場合には,N’+1を次候補とする
  7. これを未登録番号N*を見つけるまで繰り返す

通常のハッシュとはやや異なる手続きになっているが,まぁ動作するのではないか?この参照番号をあとから参照する場合にも,まったく同じ手続きが必要になる.通常,このような場合にはすでに既存カードとして登録してあるはずだから,上記のステップ4で応答することになる.この手続きでは氏名はかならずユニークで重複がないことを仮定している.コラッツ木の場合にはすべてのノードにはユニークな番号が名前として割り付けられているので問題ないが,一般の場合については,別途考えることにする.というか,一般の場合は参照番号を「与えられる」という手順になっているので,いまのところ考えなくてもよいと思う.

一つ問題がある.未登録のカードを登録する場合はこれでよいが,登録済みの場合,レコード情報には,父番号・母番号・配偶者番号は含まれるが,その氏名情報は含まれていない.つまり,これはハッシュしてダブったらアウトということになってしまう.⇒大きい数を下からカットすれば重複する可能性はほとんどないと見てよいのではないか?よほどの偶然がない限り滅多にそのようなことは起こらないような気がする.もし,この理屈が通るのなら,値を検索しないで最初から確定することができる.単純に上位ビットをカットするだけで望みの値を得ることができるだろう.とりあえず,これでやってみよう.

きれいに片付いたような気もするが,ちょっとおかしいところもある.登録カード数は498点だ.有効ノード数は511点だから,13点少なくなっている.どこへ行ってしまったのだろう?6949574919509というカードは登録されて親の5090020693も存在する.参照番号は5090020693だ.下位桁はそのまま残るのかと思ったが,まったく異なる数字列になっている.まぁ,これは仕方ないだろう.十進の数字を残すには10で割るなどの操作が必要になり,計算量が増えてしまう.

このサンプルは6-正則木として生成されているが,子ノードが1つ少ないノードがいくつかある.291157,1164629,4951381,39612757は2つ少ない.3段目で1少ないノードもある.116053だ.この段で1個消えると7個分が消滅する.3段目で2個少ないノードもある.232789だ.これで一挙に14個が消えることになる.この逆に高さ4という設定なのに6段目に子どもを持つノードが2つある.3474786993493と6949574919509だ.前者が子ども3人,後者が4人持っている.

多分これで収支はあっているのではないかと思われる.これらはすべて下位31ビットが同じカードが複数存在したために発生したものと推定されるが,対策はあるだろうか?⇒ある.上記では氏名は不明としているが,少なくともコラッツ木では「氏名」=参照番号となっているから,突き合わせは不可能ではない.しかし,これほど小さい範囲でこれだけの重複が発生するというのはかなり驚異だ.モヒティは「バイナリ操作の方法には望みがある」のようなことを言っていたが,ここまで気付いていただろうか?ちょっと上の手順を書き直してみよう.

  1. 参照番号がlongの範囲内である場合は,現行通りとする.
  2. 参照番号がlongより大きい場合には,ハッシュ関数を呼び出して新参照番号の割当を受ける
  3. ハッシュ関数には,参照番号Nをlong long で渡す
  4. Nの上位ビットを切り捨てて31ビットの番号N’を生成する
  5. N’がすでに登録されている場合:名前とNが一致している場合はN’を返す
  6. N’の登録があり名前とNが一致しない場合,N’+1を新規参照番号とする
  7. これを未登録番号N*を見つけるまで繰り返す

これでよいのではないだろうか?このハッシュ関数Fにはlong long が参照番号として渡される.Fはカードテーブルにアクセスできる必要があり,戻り値としてlongの参照番号を返すものとする.コストは結構掛かりそうだが已むを得ないだろう.

▲選択領域の部分図への追加がうまく動作しない.エラーが発生してSUWになってしまう.

▲一覧画面で行をクリックして,系図画面で移動が発生しない(場合がある).動く場合もある.

非常に奇妙なファクトを発見した.3倍数を含む一般コラッツ木で1-6-4という正則木を生成し,ゼルコバの木にインポートするとき,ノード番号が長整数の範囲を超えているため32ビット以上のビットをカットする「ハッシュ」を実行しているが,わずか511点というグラフの中でハッシュ値の衝突が13件も発生している.つまり,下位31ビットが完全に一致するノードの組が複数存在している.

一見したところ,このような一致がこれほど高い頻度で発生するなどということはあり得ないように思われるのだが…このような一致は枝番の大きいところで起きる傾向があり,ほとんどは枝番6のところで発生している.このようなノードには3倍数も含まれている.このようなことが起きる理由ないしメカニズムはいまのところまったく分からない.条件を緩和して下位15ビットが一致する場合としても,発生件数には変化はない.少なくとも言えることは,コラッツ木上の数の配置はランダムにはほど遠いものがあるということではないだろうか?

コメントを残す

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

CAPTCHA