二進数コードで弾き語り

情報系大学生の徒然技術ブログ。

λ式と再帰を使って連分数を計算するRubyワンライナーでπを近似する

お久しぶりです。もう定番ネタと化しているπの近似値ですが(諦)、今回は第3弾となります。

πの近似値を連分数で求める

公式

今回参考にした公式が、Wikipediaに載ってます。
wikipedia:連分数#様々な数の連分数展開

引用させていただくと、



\displaystyle \frac{4}{\pi} = 1+
\displaystyle  \frac{1^2}{3+
\displaystyle  \frac{2^2}{5+
\displaystyle  \frac{3^2}{7+
\displaystyle  \frac{4^2}{9+
\displaystyle  \frac{5^2}{11+
\displaystyle  \frac{6^2}{\ddots
}
}
}
}
}
}

あ、ちなみに↑の連分数なのですが、はてな記法で書くにはコツがありまして、
私はこんな感じで書いています。

<div style="text-align: center;">
[tex:
\displaystyle \frac{4}{\pi} = 1+
\displaystyle \frac{1^2}{3+
\displaystyle \frac{2^2}{5+
\displaystyle \frac{3^2}{7+
\displaystyle \frac{4^2}{9+
\displaystyle \frac{5^2}{11+
\displaystyle \frac{6^2}{\ddots
}
}
}
}
}
}
]
</div>

余談でした。

さて、問題は連分数をどうやって実装するのかですね

再帰を使う

やはり最初に思い浮かんだのは再帰でした。
イメージとしては



\displaystyle a_n = n_1 + \frac{n_2}{a_{n-1}}

これがテンプレートになって、これをイテレートしていくと



\begin{align}

\displaystyle a_n &= n_1 + \frac{n_2}{a_{n-1}} \\ \\

\displaystyle &=
n_1 + \frac{n_2}{n_3 +
\displaystyle \frac{n_4}{a_{n-2}}} \\ \\

\displaystyle &=
n_1 + \frac{n_2}{n_3 +
\displaystyle \frac{n_4}{n_5 +
\displaystyle \frac{n_6}{a_{n-3}
}
}
}
\end{align}

という具合に求まっていきます。再帰的ですね。

さて問題の上のπの公式をRubyに落とし込むと、こんな感じに

def pi_continued_fraction(num1, num2, loopcount)
  return 1 if loopcount <= 0

  num1 + (num2**2 / pi_continued_fraction(num1 + 2, num2 + 1, loopcount - 1))
end

puts 4 / pi_continued_fraction(1.0, 1.0, 25)

三項演算子の呪い

私「n?このコードもう少し短くできるよね?」

可読性「えっ?(困惑)」

私「三項演算子をすこれよ」

def pi_continued_fraction(num1, num2, loopcount)
  loopcount <= 0 ? 1 : num1 + (num2**2 / pi_continued_fraction(num1 + 2, num2 + 1, loopcount - 1))
end

puts 4 / pi_continued_fraction(1.0, 1.0, 25)

λ式の呪い

私「関数定義はやっぱ一行だよね」

可読性「やめとk」

ラムダ騎士団「いいぞ(食い気味)」

私「ラムダ式すこ」

pi_continued_fraction = ->(num1, num2, loopcount) { loopcount <= 0 ? 1 : num1 + (num2**2 / pi_continued_fraction.call(num1 + 2, num2 + 1, loopcount - 1)) }
puts 4 / pi_continued_fraction.call(1.0, 1.0, 25)

ワンライナーの呪い

私「2行...」

可読性「日本では古来から、奇数は縁起が良いと言われてきたらしい」

私「あぁ、三重塔とか五稜郭とか三十一文字とかそうだね」

「「一行にするか」」

puts 4/(pi_continued_fraction = ->(num1, num2, loopcount) { loopcount <= 0 ? 1 : num1 + (num2**2 / pi_continued_fraction.call(num1 + 2, num2 + 1, loopcount - 1)) }).call(1.0,1.0,25)

できればπの近似値をはじき出す関数

pi()

の定義がしたいので、
最終的には

puts pi = -> { 4 / (pi_continued_fraction = ->(num1, num2, loopcount) { loopcount <= 0 ? 1 : num1 + (num2**2 / pi_continued_fraction.call(num1 + 2, num2 + 1, loopcount - 1)) }).call(1.0, 1.0, 25) }.call

となりました。
ターミナルには

> 3.141592653589793

と表示されました。だいたい25項目よりも前には小数点以下15桁は求まるみたいです。

最後に

最後まで読んでいただき、ありがとうございました。

誰か可読性ちゃんを擬人化してくれると嬉しいです。