Ocaml で二分法 - I am bad at math

最近、Ocaml と数値計算をセットで勉強することにしている。

さてこの二分法とは、解を含む区間の中点を求める操作を繰り返すことによって方程式を解く求根アルゴリズムだそうな・・・。詳しくはWikipediaの二分法を参照のこと。

で、円周率を二分法で求める例、全然たいしたことないコードなんだけど Ocaml で書くのに一時間以上もかかってしまった。でも再帰関数が身に染み込んだ気がするので良し。
アルゴリズムとしては $\cos \frac{\pi}{2}$ が円周率になることを利用し、その近似値を二分法で求めるというもの。なので $\sin \pi$ でも同様だと思う。

type sign = Positive | Negative ;;

let f x = cos ( x /. 2.0 );;

let g x =
  if x >= 0.0 then
    Positive
  else
    Negative
;;

let rec bis ( x1, x2, x3, x4 ) =
  if x3 >= x4 then
    (x1, x2, x3, x4)
  else
    let xm = ( x1 +. x2 ) /. 2.0 in
    if g ( f xm ) = g ( f x1 ) then
      bis ( xm, x2, x3 + 1, x4 )
    else
      bis ( x1, xm, x3 + 1, x4 )
;;

実行してみる。

# bis (0.0, 6.0, 0, 50);;
- : float * float * int * int =
(3.14159265358978956, 3.14159265358979489, 50, 50)

収束するのに50回ちょっとかかるみたい。

文系であればこの二分法、意味は全く違う「二分法の罠」というほうが有名かもしれない。例えば
・クリスマスのプレゼントを子供に買ってあげなければいけない
・プレゼント代は自分の少ない小遣いから出さなければいけない
・なるべく出費を抑えたい
という場合において子供はPS3が欲しいものとしよう。

PS3は約3万円、でもできれば1万円以上節約したい。ここで親が繰り出すのが「二分法の罠」なのだ。親がクリスマス前あたりに子供に向かって
「Nintendo DSi と PSP Go だったらどっちをサンタさんに頼みたい？」
とあらかじめ聞いてしまう。
周りの子供達における DS の普及率が高ければ子供が DS を選ぶという期待値は予め高いものと予想できる。かつ DSi LL でも 18,000 円程度で１万円以上の節約になる。
ということでめでたくクリスマスに子供は DSi をゲットできて、親も PS3 を買わずに済んで見かけ上は win-win となる。

ここではセコい親の例をあげたけど、交渉が仕事のような人であれば知らず知らずのうちにもこの「二分法の罠」を使っていると思われる。キモは相手が許容できるギリギリのところにターゲットを合わせて「（こちら側に都合の良い）正解」となる選択肢を用意し、他の捨て駒となる選択肢もいくつか用意しておくこと。
ただし、将来的な展望を考えた上で使わないと仕事の依頼自体がなくなることもあるのは自明なので、できれば使わない方が良いのは当然である。