Spigot Algorithm

ネイピア数ってそういえばどうやって計算しているのかと思って調べてみたら、面白い記事を見つけた。
こつこつアルゴリズム(Spigot Algorithm)

無限級数 $S_n$ が以下のように定義されているとする。
$\displaystyle S_n = a_0 + \sum^n_{k=1} \prod^k_{j=1} c_j a_k = a_0 + c_1 a_1 + c_1 c_2 a_2 + c_1 c_2 c_3 a_3 + \cdots \\ \displaystyle \quad = a_0 + c_1 \left( a_1 + c_2 \left( a_2 + c_3 \left( \cdots \right) \right) \right)$

この時、 $a_k = ( a_k {\rm div} b_k ) + ( a_k {\rm mod} b_k ) \equiv ( a_k {\rm div} b_k ) + \bar{a}_k$ と書けるので、
$\displaystyle a_k + c_{k+1} ( a_{k+1} + c_{k+2}( \cdots ) ) = a_k + c_{k+1} ( ( a_{k+1} {\rm div} b_{k+1} ) + \bar{a}_{k+1} + c_{k+2}( \cdots ) ) \\ \displaystyle \quad = ( a_k + c_{k+1} ( a_{k+1} {\rm div} b_{k+1} ) ) + c_{k+1} ( \bar{a}_{k+1} + c_{k+2}( \cdots ) ) \\ \displaystyle \quad \equiv a_k' + c_{k+1} ( \bar{a}_{k+1} + c_{k+2}( \cdots ) )$

ここで、
$\displaystyle a_{n-1}' = a_{n-1} + c_{n} ( a_{n} {\rm div} b_{n} ) \\ \displaystyle a_k' = a_k + c_{k+1} ( a_{k+1}' {\rm div} b_{k+1} )$

したがって、これを次々繰り返せば、
$\displaystyle S_n = a_0 + c_1 \left( a_1 + c_2 \left( ( a_2 {\rm div} b_2 ) + \bar{a}'_2 + c_3 \left( \cdots \right) \right) \right) \\ \displaystyle \quad = a_0 + c_1 \left( a_1' + c_2 \left( \bar{a}_2 + c_3 \left( \cdots \right) \right) \right) \\ \displaystyle \quad = a_0 + c_1 \left( ( a_1' {\rm div} b_1 ) + \bar{a}'_1 + c_2 \left( \bar{a}_2 + c_3 \left( \cdots \right) \right) \right) \\ \displaystyle \quad = a_0' + c_1 \left( \bar{a}'_1 + c_2 \left( \bar{a}_2 + c_3 \left( \cdots \right) \right) \right) \\ \displaystyle \quad \equiv \bar{S}_n$

$\bar{S}_n$ に対しても同様の操作が可能であるため、これを任意回繰り返した後に第一項で近似することが出来る。

nano_exit

基礎的なことこそ、簡単な例が必要だと思うのです。