正則コラッツ木生成ツールに“Running test”機能を追加

正則コラッツ木生成ツールに“Running test”という機能を追加した.これはコラッツ木生成論理の正当性を広い領域で検証するためのツールで,Get the sequence と Get the number を組み合わせてコラッツ数列の生成とその逆演算が一致することを確認するというものだ.この検査を2^64までの範囲で実行することができれば,我々の手法の正当性はほぼ確実と言える.しかし,現実問題としてはかなり難しい.現在2^32までのテストを仕掛けているのだが,一晩掛かっても22408073までしか進んでいない.2^32=4294967296なので進捗率は0.5%!

image

この処理ではメモリは28MBくらいしか使っていないので,アルゴリズム的にもほとんど改良の余地がない.しかし,このくらいならどのマシンでも動くので予備機に移植して放置しておくという手もある.まだ,仕上がっていないので一旦ここで終了しておこう.

モヒティに頼んでいる計算式はあまり当てにならないが,それに代わる方法を考えた.現在のアルゴリズムのネックはノード番号を格納するために使っている配列が巨大なものになってしまうという点にあるが,再帰関数を使うことでこの欠陥を除くことができる.いま走らせているテストでは樹高は263まで伸びているが,ノード数のオーダーと比べれば比較にならないくらい小さな数だ.

再帰処理にすれば木の高さに比例したヒープがあればよいということになるので,相当大きな木を扱うことができるようになるだろう.仕掛りになっている「ランニングテスト」が一段落したら,コラッツ木生成処理の再帰関数化に取り組むことにする.この2つができたらほぼこのツールは鉄壁と言えるものになるだろう.

▲Max degreeを与える最大ノード番号の表示がおかしい.つねにその時点における最大値を表示しているはずなのだが,ときどき小さくなってしまうことがある.⇒対処した.

▲S=1, D=1, H=1という設定で,ノード配列サイズオーバーというエラーになった.MIN=1になっている.このエラーメッセージは日本語で表示されている.⇒配列サイズ計算論理を調整して対処した.

現行では,Max DegreeとTree heightを与えるノード番号はテストのときにしか更新されないようになっている.⇒処理を追加した.これでコラッツ木構成原理の検証ツールはほぼ完成した.一旦バックアップを取ってから,コラッツ木生成論理を再帰関数化する作業に移ることにしよう.まず,例外処理などは本体に残して,ループの部分をそっくり取り出して関数化してみよう.

関数内部で参照している変数はすべて大域変数なので問題なく動作している.この処理では途中で停止して再開するということができるようになっているが,再帰関数でそれを行うというのはかなり難しいのではないか?既成処理では大きい配列を使って,①ノードを生成する,②ノードを取り出して展開するという2段階に分かれていたため,①と②のポインタがわかれば直ちに処理を再開することができたのだが,再帰関数実行中に処理を中断して外部に制御を渡し,事後にまたその位置から開始するというのはかなり難しいと思われるので,とりあえずのところ,「処理の中断・再開」は実装しないということにする.この処理では以下のことを実行している.

開始パラメータとして,①ルートノード番号(デフォルトは1)N,②枝数D,③樹高Hが与えられ,それに従って,Nをルートとし,高さHのD-正則コラッツ木を生成し,その枝リストを出力する.その他にいくつかの統計を取っている.現行出力では,枝リストはルートから最下層まで水平に走査するような手順で出力されているが,再帰関数では垂直に下降するような動作になると考えられるので,枝リストの出力順序はこれまでとは異なるものになることは避けられない.

処理の核となる再帰関数は,あるノードを指定して,そのノードの下にD個の子ノードを生成し,それらを主語にして関数を再帰実行するようなものになると考えられる.ただし,実際にはオブジェクトは生成せず,単に枝リスト1個を出力するだけのものになるはずだ.処理自体はかなり単純なものなので簡単に書き下せるのではないだろうか?基本は下記のコラッツ木構造図に示すもの以上でも以下でもない.

image

おまけとして,ゼルコバの木のCSVフォーマットで出力するという機能が付いているが,処理が混み合ってしまうので廃止することにする.枝リスト出力はタブ区切りになっているはずだから,別途それ用のツールを作ってゼルコバの木フォーマットに変換するようにした方がよい.あるいは,ゼルコバの木で直接,枝リストファイルをインポートできるようにすることも考えられる.

再帰関数自体は仕上がった.あとは,各種のレポートを整備するだけだ.⇒終わった.ゼルコバの木へのエクスポートも組み込んだ.あとは,キャンセルボタンの始末だけだ.これは,B面のVerifyボタンの仕様と同様だ.Verify→Stop→Verifyのような動作になっている.

再帰実行中に中断するというのはかなり厄介なので,単純に打ち切るということにする.つまり,Go→Stop→Goという動作になると思われる.キャンセルボタンはつねにQuitということになるのではないだろうか?⇒できた.少し走らせてみよう.

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

CAPTCHA