Problem 64 - のてすきあ　− 完全独習非プログラマー −

無理数の連分数展開

　Project Euler を解き続けて60問。今回初めて諦めようかと思ってしまった。難しい。
　無理数の連分数展開はそんなに難しくない。しかしそれを数値計算でやろうとすると、誤差の問題でうまく行かないのである。引き算を回避したり割り算を回避したりしても、やっぱりうまく行かない。
　ここで考える。数値計算は可能な限り整数の世界で完結するべきではないか。誤差や桁落ちを心配しなくて良い土俵に上がるべきではないか。…。ココから先は完全に数学の世界である。

$\displaystyle{ \alpha = \frac{P + \sqrt D}{Q}\\ = \alpha^{\prime} + \frac{(P - \alpha^{\prime} Q ) + \sqrt D}{Q}\\ = \alpha^{\prime} + \frac{((P - \alpha^{\prime} Q ) + \sqrt D)((P - \alpha^{\prime} Q ) - \sqrt D)}{Q((P - \alpha^{\prime} Q ) - \sqrt D)}\\ = \alpha^{\prime} + \frac{(P - \alpha^{\prime} Q )^2 - D}{Q((P - \alpha^{\prime} Q ) - \sqrt D)}\\ = \alpha^{\prime} + \frac{1}{\frac{Q((P - \alpha^{\prime} Q ) - \sqrt D)}{(P - \alpha^{\prime} Q )^2 - D}}\\ = \alpha^{\prime} + \frac{1}{\frac{Q((\alpha^{\prime} Q - P) + \sqrt D)}{D - (P - \alpha^{\prime} Q )^2}}\\ = \alpha^{\prime} + \frac{1}{\frac{(\alpha^{\prime} Q - P) + \sqrt D}{\frac{D - (P - \alpha^{\prime} Q )^2}{Q}}}\\ }$