べき剰余数列と循環小数節の統合

べき乗剰余数列の周期を求める計算と循環小数の循環節長を求める計算ではどちらも剰余演算になるのでアルゴリズム的にはかなり類似したものになっている.これを統合することは可能か?というのが目下の課題だ.すでにかなりのところまで煮詰まってはいるのだが,まだ完全に解決したとは言い難い.強い類似性はあるが,相違する点も大きい.実際,真逆の計算なのだから違って当然なのだが,それを一つの計算で間に合わせようというところにかなりの無理がある.ただし,もしそれができれば,この2つの計算の「関係」がかかりクリアに見えてくるのではないかという期待がある.

PowerResidueFuncというnの逆数の循環周期を求める関数をべき剰余列にも適用するというのが目標だ.逆数1/nの循環周期では基数Bのべきを法nで除した剰余RにBを乗ずるという計算,つまりR_i=R_(i-1)*B mod H を反復することで周期を決定しているが,除算の対象を剰余Rではなく,R_i=B^i mod K のように切り替えることでほぼ同等の計算が実現できるという考え方だ.問題はRが反復していることの判定に微妙な差異があるという点だ.その前に一つよくわからない例外が発生した.

SeedTestClickで例外が発生する.K=7でi=24のとき,num0.valueにi値を書き込むところでオーバーフロー例外が発生する.しかし,書き込もうとしている値は24という小さな数であり,整数範囲を超えているなどのことは考えられない.何が起きているのか訳が分からないというのが実情だ.num0の上限値はInt64の最大値を指定しているので,9223372036854775807という十二分に大きな数字だ.⇒障害の真因は不明だが,最終的にこのパーツを作り直すことで問題解消した.

大体動くようになったが,nがKの倍数の場合に従来論理と一致しない現象が残っている.剰余数列は{0, 0}のようになるが,現行ではこれを固定部0,循環部1と解釈している.しかし,これは少しおかしいような気もする.循環小数としてみると,1/7を7進表記した場合には0.1となり,固定部1,循環部0となる.つまり,小数ではゼロが発生した時点で打ち切っている.剰余数列もそのような解釈でよいとすれば,固定部1:循環部0というのが正解になるような気がする.

たとえば,N=6,K=8の場合,剰余周期は{6*,4*,0,0}で固定部2,循環部1となっているが,これは固定部2,循環部0でよいのではないだろうか?だとすれば,剰余周期の表示も{6*,4*}のようになるはずだ.これは言い換えれば,統合版の論理の方が正しいということになる.もし,これでよいとすれば差し替えて終わりということになるのだが,従来論理を見直して一応修正しておこう.従来論理はResidueFuncから切り離して,FindOutCycleという独立の関数になっている.

FindOutCycleでは最初に剰余数列をストレートに生成し,末尾項から遡って末項の出現位置を探索,そこまでのステップを「周期」として確定した後,今度は初項から末項までドロップ項を探してカウントしているが,いくつかの点において問題がある.今の場合は,剰余数列には0項しか入っていないので,それを周期カウントに含めるのは問題がある.逆にドロップ項の検査では0項は対象に含まれていない(これは正当かもしれないが…)末項が0の場合は循環しないと断定してよいのだろうか?それは,当然だろう.従って,末項が0の場合は非ゼロ項が末項になり,そこから初項までが固定部ということになる.今の事例のようにすべてゼロ項の場合は固定部1ということになる.⇒対処した.

K=8 N=2のとき,新旧で固定部の不一致が起きた.現行では2,改訂版では3になっている.剰余数列は{2*,4*,0,}で末尾の0は循環には入らないから,固定部2桁というのが正しい.従って,改訂版の論理が間違っていることになる.しかし,これは末尾の0を固定部に入れてしまうという考え方もあるのではないか?というのは,完全に割り切れる場合には{0*}という固定部が生じるのは避けられないと考えられるからだ.言い換えると,末項の{0}は明示的に固定部に含めるという考え方でよいのではないか?もし,それが通用するのであれば,改訂版が正しいので,現行版を修正する必要があるということになる.FindOutCycleを修正してこの件は解決したが,まだ不一致が残っている.

K=12,N=2のとき固定部の不一致が生じる.改訂版では2,現行版では1になっている.循環部はどちらも2だ.剰余数列は{2*,4,8,4,}のようになるので,固定部は1というのが正しい.従って,現行版の方が正しく,改訂版は修正が必要ということになる.⇒一応動くようになったが,確信は持てない.もう少し整理する必要があるような気もする.ともかく,少し動かしてみよう.

どうも大体仕上がってしまったようだ.パラメータを一定範囲で変化させる包括検定を実施しても停止しないようになった.もう少し整理できそうな気もするが,先に進むことにしよう.試してみたいことが2つある.①小数循環節を整数化してその性質を調べる,②小数循環節に関連するレピュニット数を生成してその性質を調べる,の2点だ.まず,①から取り掛かることにしよう.⇒Recursion Unit U は10進数として表記する.(B進数として表記すると1/Nの循環節とダブってしまう).

レピュニット数の議論ではoriginatorという用語が出てくる.

コメントを残す

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

CAPTCHA