アルゴリズムが間違っている可能性

超冪剰余の計算機能を久留島喜内の道具箱に組み込もうとしているところだが,どうも使っているアルゴリズムが間違っている可能性が出てきた.いや,もちろん,実装でやり損なっている可能性はあるが… 2^^3%47=16という簡単な計算で失敗している.

UltraPower: 超冪=基底^^階数 mod 除数=2^^3 mod 47=4 有効階数=3

この計算は尖頂の2^2=4 ⇒ 2^4=16 となるのだから,答えは16にならなくてはならない.そもそも,2^^1%47=1というところで間違えている.ここから始めるしかない.いや,これは正しい.2^^1=2^0=1だ.2^^2を見てみよう.

UltraPower: 超冪=基底^^階数 mod 除数=2^^2 mod 47=2 有効階数=2

これも間違っていない.超冪記法の読み違いだろうか?ということはむしろ,超冪原木の値の方が間違っていることになる.確かにそのようだ.階高と言っている値から2を引いた数が実際のべきの回数だ.つまり,a^^nはa^a^a^…でn個のaが並んでいることを意味するので,たとえば,a^^4の場合はa^a^a^aだが,CalcPowerTowerの中で^aを実行する回数は2である.つまり,a^(a^(a^a))の式に出てくる()の個数は2だ.しかし,階高1ならaを返さなくてはならないのではないか?1が帰るというのはおかしい.いや,やはり合っていないような気がする.a=2のとき,

a^^1=a
a^^2=a^a=2
a^^3=a^a^a=16

でなくてはならない.UltraPowerでべき回数を一つ少なく見ているように思われる.⇒n=1の場合について対処した.base Mod divisor を直接返すようにした.n=2ではまだ戻ってしまっている.⇒base Mod divisorで離脱するようにして動作するようになった.しかし,49^^2%47では不一致になってしまう.3^^2%47=27 では正しく動作しているので,α>γの場合の現象だろう.7^7%47=9は正しく動作している.15^^2 mod 47=0 という数字が出てくる.原木では30だ.4^^2 mod 47=12 までは正しい答えになっている.

15, 2, 47 はすべて互いに素であるはずなのだが… 17^^2 mod 47=37 では正しい答えが出ている.これは17が素数であることに関係しているのではないか?しかし,19は素数であるにも関わらずエラーになっている.13は通る.

超冪=基底^^階数 mod 除数=19^^2 mod 47=5 有効階数=2
超冪原木=1978419655660313589123979 超冪盆栽=33

15^^2 mod 47=0 というのを見てみることにしよう.

超冪=基底^^階数 mod 除数=15^^2 mod 47=0 有効階数=2
超冪盆栽=30 超冪原木=437893890380859375

43789389038085937547はもちろん47で割り切れない.割り切れたようになっているのは中間の計算に何か誤りがあるためだろう.配列Eに何も書き込まれていない.これはどういうことだろう.α=14のときはE(0)=12が入っている.B={14, 14},C={47, 23},E={12, 0}だ.α=15の場合,depth=0 で exponentが0になっている.B={15, 15},C={47, 46}だ.C[1]=46というのが何かありそうだ.⇒どうもこれは数値がオーバーフローしているためではないかと思われる.

baseもpowerも15という小さい整数だが,15^15はすでに437,893,890,380,859,375という巨大数だ.⇒CalcPowerのローカル変数をすべてBigIntegerに変更した.これで動作するようになった.まだ通っていない.49^^2%47=2<>8で超冪盆栽と一致しない.

▲47^^2%47でゼロ除算が発生した.PowerResiduePeriodの引数 baseが0になっている.⇒LambdaFunctionで例外が発生している.GCMが0を返している.これをγ = BigInteger.Divide(γ, gcd)で使っているためだ.⇒回避するようにした.LambdaFunctionでもα=0で復帰するようにした.CalcPowerではModPow(base, power, divisor)を計算しているので,power=0のときは1が帰るようになっている.しかし,割り切れるときには0を返すべきだろう.⇒base Mod divisorの冒頭でbase Mod divisorを実行し,割り切れる場合は0復帰するようにした.

αが49を超えると不一致が発生するようになる.49^^2 mod 47=4<>8だ.ともかく一度バックアップしておこう.どうも,どこかいじって壊してしまったようだ.49^^5%47=4になってしまう.いままでは25という正しい答えが出ていたのだが…

コメントを残す

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

CAPTCHA