top page > computer > haskell > web_lecture > for_programmer > leibniz_formula.html
更新日:
文責: 重城良国

ライプニッツの公式(円周率を求める)

はじめに

ジレンマがある。初学者にわかりやすい例だと生の再帰を使うメリットがない。リストを使ったほうがきれいに書ける。とりあえずはリストを使ったほうが良い例にあえて生の再帰を使う。そのあとリストでは解決できない例を見る。

ライプニッツの公式とは

円周率を4で割った値は以下のようになる。

1 - 1 / 3 + 1 / 5 - 1 / 7 + 1 / 9 - ...

符号を反転させながら分母を[1, 3, 5, 7, 9 ...]とふやす。単純な級数だ。収束が遅いため実用的ではない。

再帰関数を使う

leibnizRec.hs

円周率の4分の1がわかれば

「...がすでに定義されていれば」という仮定になれることが再帰関数を理解するコツだ。練習してみよう。「円周率の4分の1の近似値を求める関数estPi4が定義されていれば」円周率の近似値を求める関数estPiは

estPi :: Int -> Double
estPi n = 4 * estPi4 (fromIntegral n)

となる。

級数の何個目まで計算するかを示す引数をとる。「何個」なので整数値だが計算の便宜を考えて関数estPi4では実数値Doubleとした。関数estPiでは整数でとってDouble型に変換している。仮引数nを消す。

estPi = (4 *) . estPi4 . fromIntegral

仮引数を使わない書きかたをポイントフリースタイルと呼ぶ。ポイントフリースタイルを使うと直接的な表現になる。「関数estPiは型変換してestPi4してから4倍する」。

関数estPi4

関数estPi4に0, 1, 2 ...と引数を与えた結果を見る。

estPi4 0 = 1
estPi4 1 = 1 - 1 / 3
estPi4 2 = 1 - 1 / 3 + 1 / 5
estPi4 3 = 1 - 1 / 3 + 1 / 5 - 1 / 7
estPi4 4 = 1 - 1 / 3 + 1 / 5 - 1 / 7 + 1 / 9
...

隣接する値同士を比較する。

estPi4 0 = 1
estPi4 1 = estPi4 0 - 1 / 3
estPi4 2 = estPi4 1 + 1 / 5
estPi4 3 = estPi4 2 - 1 / 7
estPi4 4 = estPi4 3 + 1 / 9
...

引数が奇数のときには引き算で偶数のときには足し算だ。引いたり足したりする数は引数をnとすると1 / (2 * n + 1)だ。

estPi4 0 = 1
estPi4 1 = estPi4 0 + (- 1) ** 1 / (2 * 1 + 1)
estPi4 2 = estPi4 1 + (- 1) ** 2 / (2 * 2 + 1)
estPi4 3 = estPi4 2 + (- 1) ** 3 / (2 * 3 + 1)
estPi4 4 = estPi4 3 + (- 1) ** 4 / (2 * 4 + 1)
...
estPi4 n = estPi4 (n - 1) + (- 1) ** n / (2 * n + 1)

(**)は第2引数が実数のべき乗演算子だ。第2引数が整数のべき乗演算子は(^)だ。これらは意味が異なるので別々の演算子となっている。estPi4 0以外はnを使った表現にまとめられる。estPi4 0とestPi4 nだけを抜き出すと実際のHaskellの関数定義となる。

estPi4 0 = 1
estPi4 n = estPi4 (n - 1) + (- 1) ** n / (2 * n + 1)

試してみる

% ghci leibnizRec.hs
*Main> estPi 10
3.232315809405594
*Main> estPi 100
3.1514934010709914
*Main> estPi 100000
3.1416026534897203
*Main> estPi 10000000
3.1415927535898396
*Main> pi
3.141592753589793

円周率に近づく。

リストを使う

leibnizList.hs

学習のために生の再帰を使ったがリストを利用したほうが「きれい」だ。0以上の実数のリストの要素すべてを以下の関数で置換する。

\k -> (- 1) ** k / (2 * k + 1)

結果としてできたリストからn個とりだし総和を求める。

estPi n = sum . take n $ map (\k -> (- 1) ** k / (2 * k + 1)) [0 ..]

ポイントフリースタイルにする。

estPi = sum . (`take` map (\k -> (- 1) ** k / (2 * k + 1)) [0 ..])

「生の再帰」版とくらべて文字数はふえているがこちらのほうが「きれい」だ。「生の再帰」よりも限定的で力の弱い「リストの操作」を使っている。

グラフ

波の振幅ははじめは急速に小さくなる。その後はなかなか小さくならない。収束が遅い。

ライプニッツの公式における円周率への収束のグラフ

まとめ

再帰関数の定義のしかたを学んだ。基底(今回は引数0が基底)と漸化式を定義する。引数が基底より「大きい」範囲のすべての値が求まる。単純な「くりかえし」であれば「生の再帰」よりリストを使う。

課題

  1. 再帰を利用して0からnまでの和を求める関数sumNを作成せよ

「再帰関数とは」へもどる 「二分樹を下へたどる」へ

正当なCSSです! HTML5 Powered with CSS3 / styling, and Semantics