Namaran

Code daily. Without assist.

2026-09-03

ArgMin.hs

argmin :: (Double -> Double) -> Double -> Double -> Double
argmin f = go
  where
    go lo hi
      | hi - lo < 1e-9 = lo
      | f m1 < f m2 = go lo m2
      | otherwise = go m1 hi
      where
        m1 = lo + (hi - lo) / 3
        m2 = hi - (hi - lo) / 3

main :: IO ()
main = do
  print (round (argmin (\x -> (x - 3) * (x - 3)) 0 10) :: Integer)
  print (round (argmin (\x -> (x - 4e8) * (x - 4e8)) 0 1e9) :: Integer)

argmin f lo hi は、区間 [lo, hi] で下ってから上る関数 f の最小点を、三分探索で求めるつもりの関数です。引数も標準入力も使わず、main が2つの関数の最小点を四捨五入して出力します。本来は 3 と 400000000 の2行が出力されるはずですが、いまは1つ目の呼び出しが 3 を返したあと、2つ目の呼び出しがいつまでも終わりません。

Answer

Wrong

go lo hi
  | hi - lo < 1e-9 = lo
  | f m1 < f m2 = go lo m2
  | otherwise = go m1 hi

Double が表せる値の間隔は、値が大きくなるほど広がります。3 の近くでは隣り合う値の差が約 4e-16 なので、1つ目の呼び出しは幅が 1e-9 を切って止まります。4e8 の近くでは差が約 6e-8 あり、hi - lo は 0 でない限り 1e-9 より小さくなれません。

区間が隣り合う2つの値まで縮むと、lo に (hi - lo) / 3 を足した m1 は丸められて lo に戻り、m2 も hi に戻ります。go lo m2 も go m1 hi も go lo hi と同じ呼び出しになり、go は同じ区間で自分を呼び続けます。

Right

argmin f = go (200 :: Int)
  where
    go 0 lo _ = lo
    go k lo hi
      | f m1 < f m2 = go (k - 1) lo m2
      | otherwise = go (k - 1) m1 hi

幅ではなく回数で止めます。1回で区間は 2/3 に縮むので、200回で幅は最初の 1e-35 倍より小さくなります。どちらの呼び出しでも、区間は Double の間隔まで縮んだうえで必ず止まります。間隔に届いたあとの残りの回数は、同じ区間を回るだけです1。

  1. 回数で止める代わりに、1e-9 * max 1 (abs lo) のように値の大きさに合わせた幅で止める書き方もあります。