kdoo

>> るーと2

期間終了したらソース公開されるんかなあ、と思ってたらそうでもなさそうなんで貼っておく。

def pow2(x)
  bits = x.size*8
  if bits < 4000
    x*x
  else
    k = bits/2

    a = x>>k
    b = x-(a<<k)

    (pow2(a)<<(k*2)) + ((a*b)<<(k+1)) + pow2(b)
  end
end

a=1
b=1
18.times { |i|
  a, b = pow2(a)+(pow2(b)<<1), a*(b<<1)
  a, b = a+2*b, a+b if i == 3
}

n = 400_000
step = 1764
k5 = 5**step

th = ((208_000 - 100343)/step + 1)*step

print "1."
a = ((a-b)*k5)<<step
m=nil
1.step(n, step) {|i|
  m, a = a.divmod(b)

  print(m.to_s.rjust(step,'0'))

  if Process.times.utime > 19.7
    break 
  end

  if i<th
    a = (a*k5)<<step
  else
    b = (b>>step)/k5
  end
}

説明とゆーか、メモ。

pow2() は二乗。Ruby で書いた方が速かったので。

やってることは、

• るーと2の近似値 a/b （a,b は Integer）をニュートン法で求め、
• 表示。

ニュートン法は x = (x + 2/x)/2 の繰り返し。Float じゃ精度が足りないから a/b の分数で、

a, b = a*a+2*b*b, 2*a*b 

と。Rational は演算中に（コストの高い）正規化が入るので、ここでは自前で。

ニュートン法だと、一回のループで有効ケタ数がほぼ二倍になる。a,b=1,1 から始めて、17回ループで 10万、18回で 20万くらい。10万の壁とか20万の壁とかはそれのこと。「20万を越えるには19回目のループが必要で、a, b = a*a+2*b*b, 2*a*b の一行に数秒掛かるし、表示部の計算量も増えるから、どーんと遅くなるよ」という話。

んで、「階段を刻み込む方法を思いついた」ってのが、

a, b = a+2*b, a+b

という（有効ケタ数の増加がヌルい*1）式を挟むこと。ケタ数は挟む位置次第だけど、今回は（表示にかかる時間との兼ね合いで）1万桁くらい増やした。

んで、あとは十進表記に変換、と。

print a*(10**2_000_000)/b

と書ければいいんだけど、時間がかかりすぎて問題外（10万桁の Bignum を to_s するだけでタイムアウトする）。

んで、割り算の筆算を（step 桁まとめて）やる、と。step の数値は、てきとーに選んで速そうなあたりで。

10**step を掛けるより、5**step を掛けて step ビットシフトした方が速いとか。

出力に必要なケタ数は有限かつ既知なので、それ以上のケタまで a/b を正確に計算する必要はない。つーことは、筆算の

• (a*10)/b 　（a を 10**step 倍して、a を b で割る）

とゆー処理を、途中から

• a/(b/10) 　（b を 10**step で割って、a を b で割る）

に置き換えられる。 b のケタ数が減るから、計算量も減る、と。

どのタイミングで切り換えるかが th の値なんだけど、「何ケタ欲しい時にどこで切り換えていいか」なんてよくわからずてきとーにやってます「数値計算のエラい人ごめんなさい」。

やり残したこと。

a と b を、（Bignum の Array で）自前の十進*2多倍長整数にしたらどうなるのかなあ、と。割り算に時間がかかりそうだけど、表示の手間はほぼゼロになる。速くなるのか遅くなるのかわかんないや。

>> [チラシの裏] 今日のアイマスメモ

リミックスをメモ。

• アイドルマスター 青い鳥 Remix

春香様の「蒼い鳥」をリミックス。じゃなくて、レ・ミックス。

気持ち悪さが良い。

• とかち未来派(仮)

ゲリゲリ（【アイマス】　とかち猩々編　ゲリラのうた？ remix）とか、むっつりすけべ〜（【アイマス】　とかち天国系　Here we go!! remix）とかの中の人のブログ。

【アイマス】　とかち春秋編　relations remixも好きだお。

• 【IDOLM@STER】　千早Solo Relations (Minimal Idol Remix)

かっこよす。