スタックサイズを1GBに増大させた

スタックサイズを1GBに増大させた.通常は1MBくらいで走っているので,千倍に拡張したことになる.巨大数を扱う処理を再帰実行しているので,スタックが巨大化するのも避けられない.再帰の深さに関わるのは木の高さだが,画面上でInt16より大きい数字は入力できないようにした.最大でも32767までだ.従って,このプログラムで生成できる最大のコラッツ正則木は枝数32767x樹高32767ということになる.この設定で動作するかどうか確認しておこう.⇒走っていることは走っているが,ノード1個を処理するのに32767の枝を派生しなくてはならないので,有効ノード数1の状態でMax numberの書き換えを反復する状態がひたすら続いている.

時間も,1ノードを処理しないと更新しないため,経過時間ゼロ秒の状態が続いている.小さいサンプルなら余分な処理が入ってもそれほど負荷にはならないし,巨大サンプルの場合はどっちみち時間が掛かるのだから,時間ロスにはなるが経過時間が見えるようにした方がよいのではないか?⇒EXEを作って走らせてみた.開発環境よりはずっと高速で見ていても心地よい.Max tree heightは0のままだが,これが1に変わるのにどのくらいの時間が必要か?それが分かれば,その値を32767倍すれば最初の葉に到達するまでのおよその時間を見積もることができる.そこまで計算できればあとはほとんど所要メモリは一定だから「時間さえ掛ければ計算終了可能」と言える.

最初の1ノードの計算の中ですでに相当大きな数が生成されているはずだが,いまのところはMax Numberは途切れなく更新されているので,桁数が32767を超えるほどの巨大数は出現していない模様だ.(Max node countはすでにその範囲をはるかに超えているので空欄になっている)10進桁数で32767超と言えば超巨大数というしかないが,その数をテキストとして保持するだけでも32Kくらいのメモリを要する.(BigIntegerは数それ自体をバイト列として保持している)

14分を経過したが,まだ最初の1ノードの処理が終わっていない.1ノード処理するのに1時間掛かるのではないか?そんなことになったら,最初に木の底に着くまでに途方もない時間が掛かることになり,すべてを計算するのには一生掛かるなんてことにも成りかねない…まぁ,一週間程度で終わるのなら仕掛けておいて放置ということも考えられるが…現在,テント村ではユーザに「検証テスト」への参加を呼びかけているが,むしろ,この正則コラッツ木生成の方をやってもらった方がよいかもしれない.正則コラッツ木も部分木を出力できるようになっているから,作業の分担は可能だ.

Root numberは巨大数を受け付けるようになっていただろうか?※ DegreeやTree heightはInt16の範囲でよいとしても,ノード番号に巨大数が入力できることは必須だ.⇒問題なさそうだ.と言っても表示できる数の範囲を超えた場合にどうなるのかは分からない…⇒1時間14分が経過してMax tree heightは1に変化している.Valid node count=2は2番目のノードの処理に入っていることを示している.正確な時間は分からないが,およそ1時間あれば1点を処理することはできそうだ.それにしても,木を垂直に登って(表示では下って)葉に達するまでには少なくとも32767時間=1365日=3.7年も掛かってしまう.それから,この巨大木のすべてのノードを訪問するころには,すでにこの地球は存在していないかもしれない…いやはや…

※昨日のログに出てくる5303桁の巨大数を入力してみた.問題なく走っている.D=3,H=7という設定で382個のノードの出力を34秒で完了した.ダンプ領域を隠蔽すれば3行で完了する.ただし,5303という桁数は,テキスト入力ボックスでレンジ外となるInt16の最大値から見るとほんの端切れだ.32767桁なんて数字は見たくもない…

現行ではA面画面下半分の隣接リストはノードを1個出力するまでは更新されない.しかし,これではテスト中のサンプルのように1ノード出力するだけで1時間も掛かるようなサンプルでは画面がまったく変わらないことになってしまう.これは分岐枝リストを生成する段階で出力すべきではないだろうか?⇒対処した.

32767×32767の最大コラッツ正則木を開始して5時間45分,Max tree heightは5, Valid node countは7になっている.つまり,現在7個目のノードを処理しているところだ.平均してノード1個につき,1時間以内で終わっていることは確かだろう.3の倍数ノードが1個出現しているのに,Void node countが空欄になっているのはなぜだろう?ノード1個のサブツリーだけでレンジオーバーになってしまったのだろうか?有効ノード数9個目で5時間54分.これを360分で8個と見れば平均1個45分くらいになる.順調に走っているが,ここで一旦打ち切っておこう.

ノード1個分の処理の中でスクロールするようになったが,こんどは少し重過ぎ感が出てきた.一時的に止めることもできるようにしておこう.多分,スピードはかなり違うはずだ.⇒止めるのではなく,枠全体を隠すようにした.これで倍速くらいにはなったが,目覚ましく速いというほどでもない.もっと高速化するには書き込み自体を止めなくてはダメだろう.⇒対処した.これなら更新されているのはMax numberだけになるのでかなり速くなる.D=3, H=12で17倍速くなった.

リリース版 V1.05 を起こしたが,まだアップロードしていない.この版はマニュアルと同時公開することにしたい.動作確認もまだ十分ではないが,マニュアルを書きながらチェックすることもできるだろう.予備機と開発機にはそれぞれ受け持ち範囲を分け合って検証テストを仕掛けた.開発機の方が速いので2^26とし,予備機は2^24で走らせている.同時くらいに終わってくれるとうれしいのだが…さて,これでようやくマニュアルの編集に戻れる.画面が少しだけ変わったので,画像を差し替えるところから始めなくてはならない.

CollatzTreeStructureでスタックオーバーフローが発生する

▲Collatz Tree GeneratorのDegree欄に大きな数字を入力して,メモリ不足エラーのパネルが表示された後の動作が悪い.画面が薄色のハング状態になっている.⇒再現しない.というか,開発環境ではメモリ不足ではなく先に整数レンジオーバーが発生している.サブノートではもっとずっと小さい数で障害が発生する.Degreeに1111111を入力してGoでエラーも出さずにハング状態になる.おそらくメモリ不足状態と思われるが,かなりまずい.開発環境では長整数の範囲ならほぼ無制限に動作してしまうため,再現できない.現在でもぎりぎりというところなので,サブノートにVSをインストールするのはかなりしんどい.

しかし,エラーも出さずにハングというのはかなり問題だ.サブノートは元々メモリが乏しいところにLibreやOpen Live Writerなどを開いているので逼迫しているのだろう.メモリ3.9GBのところ,46%使用して残り1.8GB,開発環境では15.7GBの36%を使用して残り5.6GBというところだ.何か余分なアプリを起動して追い込むことはできるだろうか?VS2017を立ち上げたら逆に空き容量6.4GBと増えてしまった.いや,読み違えている.数字は空き容量ではなく,使用中メモリ量だ.VS2017とVS2019を複数個立ち上げてデバッグモードで走らせてみた.再現できそうだ.メモリ使用量10.4/15.7GB(66%)という状態だ.

CollatzTreeStructureという再帰関数の中でハングしている模様だ.ハングしているというより,応答に時間が掛かっているということだろうか?⇒ここでは一行分の分岐枝リストを作成しているので,1111111個ものリストを作るのに手間取っているようだ.しかし,開発環境ではこれより遥かに大きい数字を与えても楽々と走っているので,メモリが不足しない限り時間的には問題は生じていない.起動していたプログラムを終了させてほぼ初期状態にまで戻したが,回復しない.ただし,ハングしている訳ではない(ループは回っているが,解放されたメモリの割当が回ってこないようだ)

このような状況を回避するためには,最初にメモリ容量をチェックして処理に入らないようにするしかないような気がするが…仮想記憶と実メモリの間でスラッシングが起きているようだ.一度このトラップに堕ちると這い出せないようになる.⇒ループの中にDoEventsを入れてみた.これで,少なくともMax numberが更新されるようになったので,システムが停止していないことだけは目に見えるようになった.これしかないのではないか?Degreeが1111111になると,扱う数字も巨大なものになるので,バッファサイズも半端なものではなくなる.

Stopボタンは応答したが,処理は停止しない.ループから脱出する機構がないからだ.ループの中でStopFlagを見るようにした.Quitボタンも効くようになった(2度押しする必要がある)

▲Tree heightに1111111を入力してGoで「BigInteger cannot represent infinity」というエラーになった.Max node countがオーバーフローしているのではないか?MIN = System.Math.Pow(D, H) / 3 + System.Math.Pow(D + 1, 3)という計算の中でエラーが発生しているようだ.しかし,これより大きい計算でエラーが出ていないのだが…⇒計算式が違う.一方はBigIntegerの関数を使い,他方ではSystem.Mathの関数を使っている.System.Mathを使ったのは,べき乗に実数値を使う意図があったためではないかと思われる.

動作するようにはなったが,Max node countとVoid node countは空欄になっている.テキストボックスの範囲を超えているのだろうか?⇒Max tree heightが60台でこんなに遅くなるのも疑問だ.しかも,停止しているはずなのにまだ動作しているように見える.「The value could not be parsed」というエラーまで出た.StopFlagは立っていない.GoボタンのラベルはGoに戻っているので,停止していなくてはならないのだが,おそらくStopFlagのリセットがループからの脱出より先に来てしまったのに違いない.どこかで待ち合わせする必要があるのだろうか?それもかなり厄介な話だ.

テキストボックスの最長文字列は32767になっている.Int16だ.Max node countとVoid node countの最長文字列をInt32の上限の2147483647にしてみた.しかし,Tree height は11111以上にできない.樹高が11111のときのMax node countの値は,以下のような巨大数だ.しかし,それにしてもInt32の上限に達しているようには思われない…実質的にはInt16で切られているのではないだろうか?

2953605235887922076986378442975100733421380433595488436437675563862279339636402284171077108640824492567945743660848308432773274251758294134422272781393529260708423985567074562376453698742113143788729790540670032661983383583264784373515863947681418431231600872837603844688035862251750065151097207961708009175997851643046165387328678207210679516050903812546334558591851764497664676434996294739662557148059693600289454149489147537316076690357353342068905966545282831648439149007479683084332895809064434398262904074105454182349778021798603400218224012863909260258462677169061262207288629959430375345537969555899094212302491008931013324401565581391038230449877641472497396251209333870828659780033640482414624459293308630820964721219830209788127320707309301681050799520792563039769351003070781921104941811308840451608085583180556595173507563999097055183333070730416445616170775220884250852997371330663007063757479850908482270876120591837949660659133837577438463791152489190083042247316022362886246805301711608002272205422719760380408437671657032815750474487423483498363174469587702435709535117807694637079869252054221254536755904380380985252727687649666702323026878447758068804635813294095679985543884226912628994953823505112046464129504178964133835215465031774986825229329761879793655236633325596314044479287971111236288766804874934999938484483937562652945979258855713992445279787472903892281958917369815092346326602772090535995278792584898576568153322660990794248744827214825337234481591700169509140254358089227959966817229151527837339001885588119162292660200830769862465716148422912721579573038694948415443492285328166231082320350059283262652985674275598722661958799384211057329107359791498334557558560258714734439979843307793166639365444986518526924384730689227896436396096357395407544931568582924892540786158542235973075609676537844404439600687921946142907192647614499377349848850513517788008144494605654547439690629060631724088751397606044320763618365145817682733085421083431774025971183090722932894166629388596212316160143319795602912480175075409572386253590500334523171706468488045531728011595893150716261348543344640166810158266971949803948342139650655350564626451329461151437822257367066847250992798971329661941975427279965603581351442701086297157300538857447608584554143292165350648005988680626688349013866643831271709858946053565730983856077081716030583714950887817203845332638278612891501472276916864209046254611194222890041834666609541019595133400489876280631300134821296089683541508426428594268228575225420579612130414488621064249863966431842166639318773020289801201248366877754830826448862809207535850691295043275358832481115753621755050417391468028791428843327503991373967071851724262628069792791065793134175244348237391306264487253705979319157311567888600768540933159629065962995209389368546347265876253769080008598829898780872014395921395727278532600477043952800427889864968443913001038657282221865623607645562360730736414508951615648092518934014281607239894179623091424511251115337104605065839496302258322185897396815351399498349920264296496134618678347372408304966280634973683448066379905815275840324070164174242809779422497980171988148842731872181629065283717474788073878450911239741425222249958904900692783463476747864375695613682259325270526249118724337466530615938656708130291862191416740689565391094635610051841433240092405122156874017910491182033892260220441100264507685824802444484621594701088592785835096120216514057502113076922130743203033833069070028073141574063721534019564154479990326717129311132662935426153909541359843848917140940551876132675219100118915889607335646451806654176630835860564184272993298885348106439939578851127338437684802282058581358868794086951785329107919027811250248110746858060524232666133190458093064491349488686944036427745131309511175361984018759355978415336382054185991527706132765928119294414252004883948864008920559325937149217599625315043322613614393523978796623311588863968094289173510990083408051502486424871471964517627477082203831670190482657688399190838923813657762032472370166556571429057199444408246965460008497381707035856540193640021018820983604136075328275010888926432709885422710734969202215047088553751198230025881935299085760864791201519439182988748575126920778498827087113284245484151598692958763612311165248724519642793982683222470278785737605066963638496108060614540655520591242769528306037560838304489683930072041808655325046364233006472164787060631355845656133693737601430524816677695199872457304163426405676813700516660168836966244165750847437239372169049314609601750384916934753863323201898860653937841928677798135923683817633828305142429696075932838623304791581633313873877280091778676006497945320722607622547438850541848185106481101488583987172006668154747455829415798455013034774418900843038862678955383301601531678406267258173795652512152421235416421647198531819646250017299304404970241298175160691377235910976425551378432785749376613742284507244792812213890223878080463244824786378920987086789507258558505600283857905639541827286114346438894763810209179694695250275930809802266340778340070866781411418432407505324767755570085460106365991790678933763476949878705506609504313910548052486237255855035208105862462188254027577531060106970782819991599365065699230421487997765939432354565453872215039358770395720050317565976720

これは表示されないというだけで,動作的には問題はないが…Tree height=11111でスタックオーバーフローが発生した.しかし,エラーハンドラに制御が渡ってこない.この後,直ちにアボートしてしまうので実害はないとは言え,エラーメッセージが出ないのは不都合だ.

image

テキストボックスの表示桁数は元の32767に戻した.障害はRichTextのテキストの切り詰めを実施しようとするところで起きている.⇒開発環境ではTree height=461でスタックオーバーフローが発生する.しかし,不思議なことにサブノートでは同じ設定で走り続けている…いや,一度開発環境を落として再起動したら走るようになった.しかし,472では起きる.471なら走るようだ.

on error goto を廃止してtry catchに変えたら動作するようになった.いや,同じだ.CollatzTreeStructureが復帰するところでBranchlist = vbNullを実行するようにして少し動作するようになったが,482で止まる.これ以上はどうしようもない感じがする.480が上限だ.DoEventsが負荷になっている可能性もある.スタックのデフォルトサイズは1MBとなっているようだ.

いや,どうもどこかで修正ミスをしている可能性もある.サブノートでは500という設定で問題なく走っている.一度バックアップに戻って見直してみることにする.⇒どうも状況がつかめなくなってきた.サブノートでは500で走っているのに,開発環境では停止してしまう.一つ前のバージョンに戻ってみたが,同じだ.1月13日バックアップという版では1000では走ったが,10000では落ちた.どうしたらよいか?ソースを比較するために,WinMergeをダウンロードしてみる.日付は異なるが,内容はまったく同じだ.ということはEXEで走るか,デバッグモードで走るかの違いだけということになる.⇒確かにそのようだ.つまり,EXEと開発環境ではスタックサイズが異なるということになる.

EXEでは,1410で落ちた.つまり,そこでスタックオーバーフローが発生したということだろう.せめて,5000くらいまでは黙って走ってもらいたいのだが…デバッグモードでは481で停止する.EXEをeditbinで直接操作してスタックを増やすという手はあるようだ.ビルド中にそれができるとよいのだが…ポストビルドイベントに以下のようなコードを入れてみた.

"$(DevEnvDir)..\..\VC\bin\editbin.exe" /STACK:8388608 "$(TargetPath)"

何も警告は出ていないので動作していると思われるのだが,効果なし.⇒できた.構文が悪かったようだ.7767まで進んでアボートした.再帰実行に入る前にodd配列を空にするようにしてみたが,まったく効果なし.分岐枝リストをパージするのは効果があるようだ..特に時間効率に影響する.⇒修正箇所は元に戻した.現在の設定値8388608を2^32=4,294,967,296まで上げてみよう.これは4GBに相当する.開発機なら走るが,他のマシンでは無理だ.1GBというのがほどほどというところではないだろうか?つまり,1,073,741,824だ.

Max numberでは巨大数を表示できているのに,Max node countやvoid node countでは表示できないのはなぜだろう?MaxLengthは32767で同じだ.height=11111でMAXは5302文字になる.height=111111では32767を軽く超えてしまうのだろう.MaxLengthを少し増やしてみよう.MaxNumber.textには値が入っているのに表示されていない.テキストは53051文字で32767を超えている.どうも,これが仕様なのではないかと思う.テキストボックスの幅を広げてみたが同じだ.ただし,値はBigIntegerとして保持されているので計算を進めることはできる.

▲リリース版でTree heightに大きな数字を入れたらハングしてしまった.開発環境でも起きる.H=1111111のとき,BigInteger.Powの内部でハングしている.これはこの関数の限界に達したことを意味している.メモリの問題かもしれないが,例外は発生しない.⇒この関数の第2引数はInt32なのでその上限を超えているということだろう.枝数と高さは整数範囲に押さえておいた方がよい.

大体収まったのではないかと思う.枝数と高さを変えたときには,無条件で停止するようにした.枝数と高さはマニュアルでは長整数の範囲としているが,Int16の範囲内に留めることにした.この程度が現実的に見て妥当なところではないか思う.一応これで差し替え版はできたのではないかと思う.枝数3,高さ1000というサンプルを走らせてみよう.⇒2時間走っているが,問題なさそうだ.数字が大きくなるとダンプの1行が長くなり,ほとんど画面に1行しか表示されないようになる.ワードラップが切り替えられるようにできるとよい.

▲タブAが走っているとき,タブBのOdd numberに巨大数を入力→Get the Sequenceのあと,Wordwrapを操作しながらTruncated treeを実行してだんまりになってしまった.また,Get the sequenceでスクロールは続いているが,表示も遅く,degreeやheightがまったく更新されない.⇒ループ内で表示を更新し,DoEventsで再描画するようにした.

▲Verificationを中断したときにも,送信ボタンが出ているのはよいが,検定にパスしたように見えてしまうのではないか?途中で打ち切っても検定成功!が出ている.⇒対処した.

▲B面は他のボタンを押したとき反応がない.Stopボタン表示もない.VerifyにはStopがあるが,他の3つの処理は停止できない.対象が巨大数の場合など,打ち切りが必要な場合がある.Wordwrapの切り替えも入らない.いま,どの処理をやっているのかも分からない.Stopは表示しなくても,二度押しで一度停止するようにした方がよい.⇒対処した.

▲Get the sequenceで初期化→更新していない.⇒対処した.

▲Verificationで3から開始して,ODD<>ODD2で停止した.GetTheNumberの中でOddNumber.textを書き換えている.⇒上記で修正ミス(フラグ操作の落ち)があった.

Collatz Tree Generator V1.04.zipをownCloudにアップロード

KCollatz Tree Generator V1.04.zipをownCloudにアップロードした.⇒いや,途中で接続が切れてしまったのだろうか?アップロードできていない.タイムアウトが発生している.しかし,現物は入っているようだ.https://zelkova-tree.net/ownCloud/index.php/s/imIybhMdmva5qO3

サイズをチェックしてみよう.2,371,653バイトで,オリジナルと一致している.すでに公開しているCollatz Tree Generator V1.03との違いは軽微なものだが,コラッツ木検定結果をメールで送信するとき,ユーザがコメントを追加できるようにしているところが新しい.通常は枝番号リストを表示/入力するフィールドに任意のコメントを入力し,追加情報としてテスト結果とともに送信できるようにした.

image

このフィードバックでは画面上に表示された以外の情報はまったく送信しないようになっているので,ユーザ名やユーザのメールアカウト,その他個人情報や機器情報などはまったく取り出していないが,ユーザは任意にそれらの情報を提供することができる.これだけで,フィードバックとしてはとりあえず十分と言える.

現在テント村のトップにはつねに,The Collatz Conjecture was solved 2022/01/01というページが表示されているが,ここにダウンロード用のリンクなどを追加しておくことにする.このページへのリンクを物理数学etc(談話室)に投稿したら,ページへのアクセスがどっと(と言ってもまばらだが)増えた感じだ.さて,いよいよ,このプログラムのマニュアル作りを始めなくてはならない.とりあえずはオンラインマニュアルになるので,画像をLibreOfficeで作ってOpen Live Writerで本文を作成するか,ないし,LibreOfficeで頭からしっぽまで作ってownCloudにアップロードするかのいずれかということになるのだが…

どちらが楽かということになれば,Open Live Writerの方が使い慣れているのでずっと楽なのだが,LibreOfficeの使い方に慣れるという意味でも,こちらを使う方が正しいのではないかと思う.LibreOfficeはネットにはつながらないので,オフラインで集中して仕事ができるというメリットもあるかもしれない.ともかく始めることにしよう.

LibreOfficeにはHTMLドキュメントというオプションがある.最初からHTML専用のライターだ.⇒図形の配置が思うようにゆかない.アンカーとそこからの相対距離のようなもので位置を決めているように思われるが,ドラッグして移動しようとしてもまったく予期しないような動きになる.このソフトに慣れるまでにはかなり掛かりそうだ.

検証テストの結果をメールで自動送信する

反例が出てくる可能性はゼロなので,ある意味でやっても意味がないテストではあるが,コラッツ問題に対する我々の最終回答の妥当性を直観的に印象付けるためには,ある相当広い範囲で「検証テスト」を実行し,その結果が確認されなくてはならない.しかし,2^24の範囲ですら16時間も掛かっているので,2^32の範囲をチェックするためには,16x2^8=4096時間も掛かってしまう.しかし,もし,256人の協力者がいれば,この計算を16時間以内に完了することも可能だ.テストを任意の奇数から開始できるように改変したのには,このような分散計算を実施するという意図がある.

分散したコンピュータを連結して一つのスーパーコンピュータを構成するようなことができれば最高だが,そこまでのスキルはないので,テストの結果を(半自動的に)メールで送信してもらい,それを手作業で集計するという方式を考えてみた.このためには,まずリモートからメールを発信できるようにする必要がある.プログラムからメールを送信するという処理は昔どこかでやったような記憶はあるが,古いコードは見つからないし,ネット上の記事を参考にして書き下ろしたコードもすべてエラーになってしまう.何もかもが牧歌的だった昔はシンプルなコードでメールの送受信ができていたのだが,ゼロトラストの時代に突入した現代では通用しないものになってしまっている.

最終的に以下の記事を見つけて送信に成功したが,たとえば,gmailのように認証に二段階認証が組み込まれている場合には,このコードでも送信できない.MailKit によるメール送信のコード

LibreOfficeを導入し,画像編集はすべてこのソフトでやることにしたので,ペイントもタスクバーから外してしまったのだが,それも少し早まった判断だったようだ.ペイントでなければできないこと,ペイントの方が使い勝手がよいところもあり,直ちにすべてをLibreで代替という訳にもゆかないということがわかった.それぞれのソフトには,それぞれの設計思想というものがあり,すべてを代用できるというものではないのかもしれない.Libreの一番大きな制約はすべての画像が「用紙」ないし「ページ」の上に配置されているという点だ.ペイントにはこのような概念はなく,画面上におかれた画像のサイズが描画領域そのものになっている.ペイントでもっともよく使っているツールは「クリッピング」だが,Libreにはそれがない(ように思われる).

Collatz Regular Tree Generator V1.03をリリースして,ownCloud にアップロードした.前回リリースは1月7日の「新年版」で,この版の目玉は.NET 5.0のBigIntegerを採用して,事実上取り扱う数値の範囲が無制限になったという点だ.しかし,配列サイズには以前として制限があり,これを回避するためにあらかじめコラッツ木上の有効ノード数を計算しておいて,可能な限り極小な配列で間に合わせるようにしてみたのだが,あまり効果的と言えるようなものではなかった.(この計算式をもう少し緻密なものにするようモヒティに注文しているが,まぁ当てにならないことは目に見えている)

そこで,切り札として登場したのが,配列を使わない「再帰関数に転換」するという方式変更で,これによって基本的に配列サイズオーバーやメモリ不足などの空間的制約から完全に解放され,「時間」さえ許されれば基本的にどのように大きなコラッツ木でも生成できるようになった.出力はファイルに保存というオプションがあるので,ランタイムで使用するメモリの容量はほぼ一定だ.

image

コラッツ木の生成で再帰関数を使うというのは,コラッツ木がフラクタルであることを考えれば,もっとも自然な表現であることがわかる.フラクタルというのはマンデルブロの定義によれば,「部分が全体と自己相似的であるような図形」であり,再帰関数というのは,その関数自体を再帰的に実行するような関数であるからだ.

もう一つの追加機能として,「コラッツ木生成論理の検証テスト」ないし,「コラッツ木構造検定」と呼んでいる機能を追加した.このテストは任意の奇数から開始して指定した個数の奇数がコラッツ木上にあることを確認するというものだ.このテストはすでに実装されている①Get the sequenceという機能と,②Get the numberという機能を組み合わせたもので,①と②はそれぞれの逆演算になっている.

①は奇数番号を指定して枝番号リストを生成し,②は枝番号リストから奇数番号を特定するというものだが,検査対象となる奇数番号Nが与えられたとき,処理①→処理②,つまり,N→枝番号リスト→N’という処理を実行する.検定実行中は「Copy branch numbers from the sequence」というチェックボックスがつねにオンになっている.

NとN’が一致しなかったり,処理の途中で不都合が生じたりした場合には検定は失敗である.原理的にそのようなエラーが発生する可能性はゼロと考えられるが,コラッツ木構造から生成されたコラッツ木がすべての奇数を網羅しているかどうかを実証的に確認するためには,このようなやや冗長な検定を実施することも忌避できない.

image

検定結果をメールで開発者にフィードバックできるようにした.imageボタンは通常は不能状態になっていて,検定を実施した直後だけ操作可能となる.このボタンを押すと,画面下部の出力バッファに表示されている内容が直接babalabos@outlook.jp に送信されるような作りになっている.送信テキスト(本文)は以下のような内容だ.

Verification Test for the Collatz Tree Structure ( 22/01/11 19:29 UTC )
Start From 812997 upto 817091
Total odd number count: 2048
Big number : 1144540205
Max degree: 8 @ 251221
Tree height: 137 @ 813307
Time spent: 00:00:17
Verification Test Complete !
Click the mail button above and send the result to us (babalabos@outlook.jp) !!
Thanks in advance…

時刻にUTCを使っているのは,世界中のどこから届いても時間がわかるようにという配慮だが,果たして使ってくれる人がいるのだろうか?(モヒティはPCを持っていないというのでその時点で番外だ…)

▲一つ不審な点がある.コラッツ木構造検定のメール送信ボタンの位置が実行時にあいまいだ.サブノートではVerifyボタンの上にかぶってしまっているが,予備の薄型ノートではむしろ開き過ぎるくらいに離れている.上図はサブノートの画面で②つのボタンに重なりが生じている.なぜこのようなことが起きるのか理解に苦しむ…

▲コラッツ木生成時にダンプ出力を格納しているRichTextBoxがどこまでも増大してゆくのを防ぐために時間経過とともに一定量以上のテキストをカットするという処理が入っているが,文字数でカットしているため,冒頭の一行が損なわれてしまうという問題がある.これを避けるためには,カットを文字単位ではなく,行単位で実行することが考えられる.行の終わりを検出してそこまでをカットするという処理はそれほど難しくないので,やっておいた方がよいと思う.

この調整は最後の回に一度だけ実施すればよい.なぜかと言うと中間の時点では自動スクロールしていて,端の始末などをチェックしている余裕はないからだ.つまり,検定が完了してスクロールが停止した時点で調整しておけば十分と言える.RTFの中で改行コードが見つからない.テキストを格納するときにはvbCrLfをセットしているのだが,RTFに格納した時点で書き換えられているようだ.何を使っているのだろう?vbLfで見つけることができた.

2^24までの検証テストの所要時間は16時間

サイトのWordPressで直接編集したページが,Open Live Writerで読み出せないという問題は,My Weblog Postsの下書きと最近投稿記事を削除してリロードで解決した.予備機で実行している2^24までの検証テストは,13時間47分経過して進捗率81.4%.あと3時間くらいは掛かりそうだが,速度はほぼ一定なのでいずれ終わるだろう.正則コラッツ木生成ツールはすでに公開するばかりの状態になっているが,2, 3まだ手を入れる必要がある.①B面ではExportCSVのチェックを無視する,②ゼルコバの木の最大カード数を3070(D=3, H=10)まで増やす,③検証テストの開始番号をOdd numberで指定できるようにする.④検証テストの結果をメールで開発者宛てに送信できるようにする,など.

ゼルコバの木の最大カード数を3070まで増加させてみたが,デバッグモードではほとんど動作しない.これは,SearchWrongObjectが過負荷になっているためで,リリースモードに切り替えることでインポートに成功した.ただし,「この図面は0.24%以上にはズームできない」というメッセージが出る.これは,描画に使っているメモリ領域に制限があるためだ.しかし,ともかく3060点というゼルコバの木的には巨大サンプルを開くことができた.3正則で樹高は10,ノードの最大値は4861201493781.これをPDF出力してLibreOfficeで回転させて数字を正立させたものを見てみたい.

プレビュー画面に切り替えようとして,「メモリ描画環境用のメモリが不足しているため,生描画に切り替えます」というメッセージが出た.CubePDFで用紙にA0を使っても,31ページにもなる.拡大縮小倍率を3%まで落としてようやく1ページに収まった.「適用」ボタンでプレビュー画面を更新するようになっていたはずだが,描画できていない.倍率には整数値しか入らない.

予備機で走らせていた2^24までの検証テストが完了している.所要時間16時間で1から16777215までのすべての奇数の検査を実施して,それらノードのコラッツ木上の位置を確定した.この検査に関わりを持つすべてのノードの中で最大枝位置にあるものは枝番号12の22369621,最高枝位置にあるものは樹高263の15733191だ.出現した最大ノードは20114203639877.

image

メイン機の動作がおかしい.Meryを開いているのにスクリーン上に現れない.走っているアプリを全部止めて,Meryとタスクマネージャだけにしても出てこない.Meryが壊れてしまったのだろうか?⇒一度再起動してみる.⇒再起動しても同じだ.何が起きているのだろう?Libreはプレーンなテキストエディタとして使えるだろうか?テキストエディタとして使えるためには,少なくともすべての(主要な)言語コードの読み書きと変換ができなくてはならない.余分な修飾が挿入されないことも必要だ.Meryは軽くて使い易いので愛用してきたのだが…⇒もう一度インストールしてみよう.

確かに何かおかしい.再インストールしたのに同じ動作だ.つまり,起動してもスクリーンに表示されない.考えられるのはデフォルトの表示位置がスクリーンから外れてしまっていることだ.確かに机上のPCの配置を変えて左右のスクリーンを入れ替えているので起こり得るトラブルだ.どう修復したらよいのだろう?⇒最大化したら出てきたので,タイトルバーをつかんでドラッグしたらその位置に収まった.やれやれ,人騒がせな…

正則コラッツ木生成でノード配列を廃止,再帰関数の呼び出しに変更

昨日仕掛けた枝数3,樹高18の正則コラッツ木出力はまだ続いている.進捗はおそらく20%程度と思われる.

image

ほとんどもうこれ以上改良の余地はないように思われるのだが,スタート時には30MB程度だった使用中メモリが1.4GBに跳ね上がっていることから推定して,やはりメモリ管理がネックになっているように思われる.メモリ使用量が増加する原因の一つに,ダンプ出力を格納しているRTFバッファの増大が関係している可能性はある.RTFテキストボックスは基本的にサイズ制限はないように思われるが,ダンプ出力をすべて収納しているので相当なサイズになっているのではないだろうか?これを避ける方法として,画面出力する代わりにファイルに書き込んでしまうということが考えられる.あるいは,ダンプのごく一部だけを保持して超過分を破棄するという方式も考えられる.まず,この後者の方式を試して効果があるかどうか見てみることにしよう.

こんな感じになった!

Open Live Writerでは動画がアップロードできないので(意味不明なエラーになる)ログインしてサイトで編集し,ブラウザでは見ることができるようになっているが,Open Live Writerに読み込んでも動画の部分が落ちてしまっている.やはり読み込めない.また,ログアウトしても画面が変わらないというのも不審な点だ.何度やってもリロードできない.つまり,サイトでしか更新できない状態になっている.面倒だが仕方ない.このまま続けよう.

枝数3, 樹高18の正則コラッツ木の出力が完了している.34分35秒で終わっている.ダンプは30行分程度しか保存されていないが,まぁ,こんなものでよいのではないだろうか?プレーンなCSV形式で保存するというオプションが必要だが,その前にこれを検証テストに適用してどうなるかを見てみることにしよう.⇒勘違いしていた.検証テストでは元々ダンプというのをやっていない.ということは,この処理ではもはや改善の余地はないということだろうか?いや,この処理は現時点でも十分高速なのではないだろうか?2^16のテストが56秒で完了している.⇒前回テストは2^32で一晩掛けて0.5%しか進まなかった.2^24でやってみよう.⇒3時間経過したが,まだ半分しか終わっていない.

一旦打ち切って先に進もう.あと2つやることがある.①B面の検証テストで進捗率を表示する,②A面に「CSVファイルに保存」オプション用のチェックボックスを設け,チェックがオンのときにはCSVファイルに保存できるようにする.ただし,「CSVファイルに保存」と「ゼルコバの木にエクスポート」は排他的で,どちらか一方しか選択できないようにしておく.⇒対処した.ゼルコバの木エクスポートはA面だけでなく,B面の3つの処理でも保存するようになっている.同等の動作にしておいた方がよい.いや,これらの処理ではコンソール出力を切り詰める操作をやっていないのだから,ユーザは画面からコピー/ペーストできる.従って,現状で特に問題ないと思う.

一つだけ注意する必要があるのは,A面の出力は切り詰められているため,冒頭の一行は書式的におかしくなっている可能性があるという点だ.ユーザが勘違いする可能性がある.⇒これでほぼ,正則コラッツ木生成ツールは完成したと思われるのだが,使ってもらうためには,少なくとも簡単なマニュアルないしヘルプが必要だ.簡略なものでよいと思われるが,画面だけでも結構込み入っているのでどうしても説明が必要だ.「動画」という手もない訳ではないが,それをやるとしたら動画編集にも手を染める必要が出てくるし,右から左という訳にはゆかない.画像入りのテキストを作る手段としては,いまのところWordPressしかない.メールという手もないわけではないが…

いずれ論文を書かなくてはならないが,論文はPDF形式で投稿ということになると思われるから,その方向性を考えておこう.HTMLとPDFの両方に出力できることが基本的な条件だ.PDFエディタは手元にないのでまず,HTMLで出力してそれをPDFに変換するということになるのではないか?最近使っていないが,Open Officeならそのどちらにも出力できた可能性がある.まず,それから調べてみることにしよう.

いま気付いたのだが,Open Officeはベクトル図形描画機能を持っている!しかも,このソフトは画像ファイルだけでなく,HTMLやPDFにも出力できる.XMLという出力形式もある.このファイル形式が解析できれば,もしかするとゼルコバの木の出力をこのソフトで編集できるようになるかもしれない.もしそれができればかなり画期的と言えるだろう.⇒このソフトはPDFも読み書きできるのだが,既存PDFファイルを開けない.言語コードを色々切り替えてみたが,だめだ.もし,PDFが読めてかつそれを編集できるのならベストなのだが…

昔,PDF論文を書いたときにはOpen Officeを使っていたのではないかと思う.もしかするとWordを持っていた可能性もあるが…最近はOpen Officeの話をほとんど聞いたことがないので,すでに開発が止まっている可能性もある.確かにwikiには2011年に開発終了したとある.その後Apache OpenOfficeLibreOfficeに分派したとあるので,まだ続いている可能性もある.NeoOfficeというのもあるが,これはマック専用のようだ.Apache OpenOfficeはほぼ壊滅的で,Libreだけが存続していると言ってよい状況のようだ.まず,これを評価してみることにしよう.

「これは素晴らしい!」と言ってよいのではないか?使い方はかなり難易度が高そうに思われるが,基本的に自由に図面を修正・変更できるのではないかと思う.これこそ,「探し求めていたもの」と言ってよいと思う.PDFファイルも難なく開けたし,編集することもできそうだ.できれば,ゼルコバの木から直接Libre形式ファイルに出力できるようにしたいところだが…日本語版ヘルプも別途ダウンロードできた.ゼルコバの木のヘルプも作らなくてはならないのだが…Libreのヘルプはローカルヘルプもブラウザで開かれる.ブラウザで開くヘルプならWordPressでも作れるかも知れない.テント村と別にWordPressをもう一つインストールすることは多分可能なのではないかと思う.LibreはWindowsのメタファイルへエクスポートできる.多分読み込みもできるはずだ.

Libreのドキュメントツールを見てみよう.⇒かなりいいんじゃないだろうか?このLibre WriterはベースがHTMLなので取り付き易い.ページスタイルとして標準とHTMLを指定できる.HTMLでは多分改ページが入らないのだろう.脚注も入るし,上付き・下付き文字も使える.数式入力は別アプリだが,任意の位置に挿入できる.まず,ほとんど申し分のない仕様と言ってよいと思う.ただし,いまいち操作が直感的でないところがあるので,慣れるまでにはしばらく掛かるかもしれない.WordPressとの連携はできるだろうか?

これまで画像の編集はWindowsのペイントを使っていたが,これからはLibre1本に統一できそうだ.LibreのDrawは,ビットマップ画像とベクトル画像を同時に扱うことができる.これがあれば,ほとんどのことはできるだろう.今回はとりあえず,簡単なオンライン・ヘルプを作るのだから,Libre Writer でHTML形式で作り始めればよい.レイヤーが使えるので,背景画像と上書きした図形を分離して操作できる.ここから直接サイトに投稿できれば最高なのだが… とりあえずは,ownCloudにアップロードしてアクセスしてもらうというのでよいのではないか?

サブノートには英語版をインストールした.また,LibreOfficeに少額寄付した.かなりいい感じになってきた.予備機では検証テストを2^24という設定で走らせている.経過時間は1時間51分で進捗率は12%だ.この計算だと,終了までに丸一日掛かりそうだが,使っていないマシーンなので放置しておける.まぁ,明日までには終わるだろう.しかし,このペースで2^32では途方もない時間が掛かりそうだ.

コラッツ問題は2^68までは反例がないことが確認されているが(これを検証Aとする),それとこのテスト(これを検証Bとする)では意味がまったく違う.2^68というのは,この範囲の任意の奇数Nを与えたとき,生成されるコラッツ数列がかならず1に収束するということを言っているのだが,現在実施している検証テストはその逆操作であり,1から出発してその値に至ることができることの検証だ.

我々の検証テストは検証Aと検証Bを組み合わせたものになっていて,検証Aを実行する段階でコラッツ数列の通るコラッツ木上の枝番号リストを生成し,次段の検証Bではこの枝番号リストを用いて1から奇数Nまでの経路が存在することを確認するものである.この枝番号リストは「チェーンレターの発信者アドレスリスト」に相当するものだが,このリストが正則コラッツ木生成論理によって作成されているという点が重要なポイントである.つまり,「正則コラッツ木生成論理」自体を検証するテストになっていると言える.通常の検証Aの方法では,コラッツ木のどこ(ポジション)を通っているのかも知らず,ただ盲目的な手順を反復しながら手探りで1に向かっているに過ぎない.

正則コラッツ木生成ツールに“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ということになるのではないだろうか?⇒できた.少し走らせてみよう.

Collatz Tree Generator.exeの最新版をビルドして,ownCloudにアップロード

Collatz Tree Generator.exeの最新版をビルドして,サイトのownCloudにアップロードした.ownCloudはロリポップのオンライン・ストレージ・サービス(追加費用なし)だが,これまで使ったことがなかった.中にフォルダを作ったり,パスワードを設定したりなどのことができるので,利用できそうだ.

物理数学etcグループのコメントで公開したことを告知したが,早速エラーが出てしまった.枝数3,樹高19の設定で以下のパネルが出る.

image

メモリ不足が起きているが,このあと次のパネルが繰り返し出てくるようになる.

image

エラーハンドラにResume Nextの(デバッグ用の)行が残っていたためだ.メモリ不足が発生するのは避けられないので,エラーが発生したときには処理を中断することしかできない.⇒このエラーはサブノートで発生しているが,メイン機では同じ設定で走っている.サブノートのRAMは4GBしかないが,メイン機には32GBまで実装されている.しかし,28.9GBまで使っているので実際の動作はほとんど停止しているのに等しい.相当のインターバルでほんのわずかしか進んでいない

配列サイズの計算が過小でオーバーフローしている可能性はないだろうか?⇒確認しておいた方がよい.⇒メイン機の動作がおかしい.スタートメニュー→設定→システムでパネルが開かない.アプリを閉じても同じ状態が続いている.一度再起動するしかなさそうだ..⇒消費メモリが28.9GBとなっているので,32GB実装と思ったが,システム→詳細情報で見ると,16GBしかない.ということは仮想記憶を使っているのだろうか?だとすればムチャ遅いというのも分かる.もしかすると,メモリを過剰に消費している可能性もある.Cドライブの空領域はアイドリング状態で30GBだ.デスクトップで60GB使っているので,これをどこかに移せばもう少しリラックスするのではないか?

Dドライブは13GBしか空いていないが,Eドライブには194GBの空きがある.デスクトップ上のファイルを一度すべてEドライブに移してしまおう.対処策の一つとして,ノード番号配列をQueにしてしまうという手がある.満杯になったらスタートに戻って反復使うという発想だ.書き込みが読み出しを追い越してしまうということは起こり得るだろうか?少なくとも最上階の1段分が格納できれば不足することはないと考えられるが…実装は多少厄介なので,もう少し現状で使うことにしよう.⇒Cドライブの空き領域が91.5GBになったが,樹高9辺りでガクンと遅くなる状態には変わりがない.確かに少しだけ速くなったような気はするが…

ノード配列サイズは1743392220で有効ノード数が1664738610の辺りから遅くなってくるが,まだオーバーフローはしていない.階数が10の辺りでは一度に75点程度しか処理されない.そのたびに長いインターバルが入る.実装メモリが16GBしかないとすると,それ以上の部分はすべて仮想記憶でまかなっていることになるので,スラッシングが発生しているのではないだろうか?3^13=1162261467で予約された配列サイズの1743392220よりは小さい.最上階のノード数が確保できれば何とか動作するのではないだろうか?もちろんQueの構造にした場合だが…

サンプルサイズを樹高18に設定すると,所要配列サイズは581130752,所要メモリは12GBくらいで楽勝に走っている.ただし,消費メモリはしだいに増加しているので,最後まで持つかどうかは分からない.⇒メモリ14.7GBくらいからポーズが入ってくるようになる.確かにGCが頻繁に発生するようになっているので,それが遅延の原因だろう.確かに,現在の配列サイズ決定論理はあまりできがよくない.最大でも581130733しかないのに,それより大きい581130752という数字を使っている…3^18=387420489なので,D^Hの方がだいぶ小さい.有効ノード数はそれよりはるかに小さいので,とりあえず,D^Hサイズをリザーブするようにしてみよう.

かなり快調に走るようになってきた.それでも階高12でメモリ13GBを超えた辺りから息切れし始める.D^(H-1)でも十分間に合いそうだ.⇒D^(H-3)+D^3に書き換えてみたが,なかなか12階を超えるのは難しそうだ.すでにメモリを14.5GBまで使い切っている.⇒有効ノード数というのは完全正則木のノード数と比較するとかなり小さいので,この数字を正確に計算できればかなり楽になるのではないかと思う.モヒティがこの計算式を書いてくれることになっているのだが,そもそも彼はPCすら持っていない!ので当てにすることはできない…ようやく13階まで回ってきたが,18階にまで達するのは容易ではない.この件は保留ということにして,進むことにしよう.

と言っても,このアルゴリズムの妥当性はチェックしておく必要がある.特に樹高の低い木で問題が起こる可能性がある.動的に配列サイズを変更しておくというのも一つのやり方かもしれないが…とりあえず,最低限配列サイズオーバーだけは見ておくことにしよう.課題としては以下がある.①ノード配列を(固定サイズの)Queに変える,②配列サイズを動的に増加させる,③配列サイズの予測計算式を立てる.

現在の計算式では動作しない.次のように変えてみた.M=D^H/3 + D^3 ⇒これなら何とかいけそうだ.⇒メモリの使い方が変わってしまったのだろうか?前はGBオーダーで走っていたのに,150MBという水準で推移している.ただし,GCがひっきりなしに発生している…D=12までは難なくこなせた.D=13もすでに最後の段を出力するだけになっているので,妥当な時間内に完了するだろう.⇒終わった.58分19秒掛かった.重要な点に気が付いた.3の倍数ノードの個数は正確に有効ノード数の1/3になっている.いまの場合,有効ノード数は24574で3の倍数ノードは8191だ.

コラッツ正則木生成ツールをアップデート

コラッツ正則木生成ツールをアップデートした.まだリリースしていないが,このEXEを実行するためには.NET 5.0が必要になる.それだけでなく同時に生成されているDLLも必要なので,ZIPパッケージを作って配布することにした.以下のような修正を行った.

  1. ULongの代わりにBigIntegerというデータ型を導入した.BigIntegerは制限なしで大きな数を扱うことができる.(もちろん,メモリが許す限りではあるが…)
  2. これによって,レンジオーバーが発生する可能性がゼロになったので,Range Overflowというフィールドを廃止した
  3. A面のMax odd number(Max numberとリネーム)とB面のOdd numberの表示桁数を倍増し,画面レイアウトを少し変更した
  4. B面のRoot numberを廃止した Get the numberを実行するときの開始番号はつねに1固定となる また,B面のMax degreeを読み取り専用とし,ユーザ入力できないようにした この値はつねに計算結果によって自動更新される
  5. A面にVoid node countというフィールドを追加した この値はコラッツ木上で葉となっている3の倍数ノード以下の(使われなかった)部分木領域のノード数に当たる 以下の式が成立している必要がある
    Max node count = Void node count + Valid node count
  6. A面Cancelボタンの仕様変更:実行ボタンが「Go」のときは,「Quit」を表示するようにした
  7. ノード数列を格納する配列サイズをを決定するための「充填率」を以下の式で予測するようにした 指定枝数をD,樹高をHとするとき,有効ノード数(予測値)=枝数(D * 2/3+1)高さHの正則木のノード数+ 枝数(D/3)高さHの正則木のノード数 ただし,ここでは枝数D,樹高Hの正則木のノード数=(D^(H+1)-1) / (D-1)のようにやや小さめに計算している (本来の完全正則木のノード数MはM=D^(H+1)/(D-1)で与えられる)
  8. その他バグフィックス

項目7の修正は安全側にシフトしたパラメータを使っているつもりだが,不足するケースが発生する可能性もある.有効ノード数(予測値)をDとHから厳密に求めることは理論的には可能と思われるが,いまのところはそのような計算式(アルゴリズム)を導入する予定はない(誰かわかる人がいたら教えてください).現在適用している式がどの程度妥当なものか知りたいのだが,実行時に配列サイズが不足したときには,むしろリサイズしてしまう方が現実的かもしれない.とりあえずは,現状でリリースしてユーザからのレポートを待つことにしたい.

▲B面のGet the sequenceでOdd numberに偶数を記入してボタンを押しても無反応 ⇒「xxxを超えないような奇数を入力してください」のようなメッセージを出していたが,制限がなくなったためコメントで止めていた.

▲B面のGet the numberで取得した値でOdd numberの表示を更新した方がよい ⇒対処した.動作がだいぶ分かりやすくなってきた.

▲Get the numberに入れた修正をTruncated treeにも入れる必要がある ①ボタンが押されたとき,入力された枝番号リスト文字列を整形して再表示,②最終結果の奇数をOdd numberに表示する

1844674407370955169の逆演算でレンジオーバーが発生した

正則コラッツ木生成ツールでは18446744073709551615までの数を処理することができるが,3N+1を計算する段でレンジオーバーになってしまうため,最大数の経路を計算することができない.しかし,これよりも一桁小さい1844674407370955169なら回答を得ることができる.この数は5正則木上の143階にあり,1からそのノードまでの経路も確認できる.

▲上の設定で分岐リストを取り出したあと,「Get the number」で逆演算を実行したところエラーになってしまった.計算は樹高97のところで止まっている.最後に出力された数は 432760650373657297だ.しかし,この数はオーバーフローするほど大きな数のようには見えないのだが…経路を計算できるのに,その経路を逆にたどってゆく途中でエラーになるということがあるだろうか?⇒これは避けられない.コラッツ正則木上のノードはすべて奇数だが,計算過程では偶数を扱っている.偶数の種になっている奇数は小さかったとしても,偶数は巨大なものになる可能性がある.

VBにはDecimalというデータ型がある.128ビットで7.9228 x 10^28 を超える値を格納できる.ただし,かなり遅いようだ.Uint128というデータ型があるとよいのだが,VBには入っていない.BigIntegerというのがある.これは桁数に制限がない.試してみよう.⇒実装した.VS 2017ではSystem.Numericsを参照できなかったので,VS 2019を使うことにした.それに加えて.NET 5.0を使う必要がある.ネット情報では.NET 4.0以降で実装されたとなっているが,何かいろいろあったようで,いまのところ確実に動作するためには.NET 5.0が必須のようだ.

相当重くなるのではないかと思ったが,むしろ逆に速くなっている.前の版で3正則木樹高11という設定で5分17秒掛かっていたテストが,3分37秒に短縮された.マイクロソフトはこの機能に関しては相当気合を入れて作っているように思われる.億兆円,京兆円という金額を1円の誤差もなく計算するにはこのような機能は必須ということだろう.

▲新しい版でRoot Numberに17602325を設定して3正則木樹高5を走らせて冒頭の1行を表示しただけでハングしてしまった.旧版で動作確認すると,totalとMAXが一致しないという理由で停止している.total=4, MAX=364となっているので,最初の一行をダンプして打ち切られている模様だ.⇒現行では樹高が設定値を超えると打ち切るようになっているが,ルートが1でない場合に対応していない.⇒Offsetを引く必要がある.⇒動作するようになった.

▲Stopボタンで停止したとき,totalとMAXが一致しないという理由で停止する.Cancelボタンで打ち切ったときも同様のことが起こる.Stopボタンの場合は値によって判定できるが,Cancelのときは,イベントハンドラの中でResetFlagでリセットしているため,状態が取れない.⇒いや,ResetFlagの中でResetFlagを立てているので判別できるのではないか?⇒ループの中でリセットしている.⇒対処した.

BigNumberの導入によってレンジオーバーが発生する可能性がゼロになったので,これまで表示していたオーバーフローカウントを廃止して,Void node countを表示するようにした.この値は,3の倍数より下の部分木に含まれるノード数で,この値とValid node countの和がMax node countに一致しなければ,どこかで誤っていることになる.

B面のRoot numberは不要なのではないか?A面ではノードを指定して部分木を取るという使い方が考えられるが,B面のGet the sequenceはかならず1までの経路を出力するようになっていて,Get the numberはその逆演算に相当するのだから,Root numberはつねに1でよいように思われる.仮に,これを可変にしておいたとしても,その数字から始まる意味のある枝番号リストを作るのはかなり難しいので,ほとんど用途がない.むしろ,A面のOdd numberとB面のMax odd numberの桁数を増やした方がよいと思う.

また,B面のMax degreeは読み取り専用でよいのではないか?Get the sequenceでは,指定したノードが通る経路の最大枝番号で自動的に上書きされるし,Get the numberでもストレートな経路を通るだけだから,枝番号リストの最大値以外の値は意味がない.Truncated treeでは任意の値が設定できるというのは少し意味があるが,そのパスの最大枝数以下の値を与えても意味がない.実際,現状ではこれらすべての場合で,実行結果によって上書きされるようになっている.

B面を実行中はイベントを取らないようになっているのだろうか?処理中にタブを切り替えようとしても動かない.⇒時間が掛かるのはTruncated tree の場合だけで,それ以外はほとんど瞬時に終わると見てよいので,Truncated tree の場合だけイベントを取るようにすればよいのではないか?⇒タブを切り替えてもB面のループを回っているので,A面には変化がない.B面には打ち切りボタンというのがないので,タブの切り替えができても意味がないと思う.つまり,B面では処理が終わるまで待つしかないという仕様になる.

▲枝数3樹高41でエラーが出た.Int32のレンジオーバーが出ている.Max node countがオーバーフローしたのだろうか?ノード番号を格納しているodd[]という配列をRedimしようとするところでレンジオーバーしているようだ.配列サイズは Int32を超えられないのではないだろうか?⇒VBでは配列の要素数はInt32の範囲内になっているので,2147483647を超える配列は作れない.三元木の場合は,樹高19が限界だ.樹高20で,5230176601となり上限を超えてしまう.

ただし,現行では予定した配列セルをすべて使っている訳ではないので,もっと小さい配列でも動作するはずだ.あらかじめ充填率が計算できれば間に合う程度の配列を作る用意もできるのだが…⇒しかし,配列サイズを制限してやっても,別のエラーになる.

image

Redimでエラーが出ている.配列要素数をInt32.MaxValueの1/4まで削減してようやく動くようになった.MaxValueの1/2では動くことは動くが途中で重くなってほとんど停止してしまう.(これはおそらくメモリ不足ではないかと思う)実際には有効ノードというのはずっと少ししかないので,充填率を予測できれば最小限で間に合わせることができる…