アルゴリズムのチカラ

昨日の社内勉強会で詰まって悔しかったのでリベンジ。
x^3 + x^2 + x = 1 となるx を求めよ（近似値 = 0.000001とする）という三次方程式の解を求めるプログラム。

まず、ループを使ったベタな線形探索。
解答に至るまで543690ステップの計算を要しています。

EPSILON = 0.000001  # 近似値イプシロン
FUNC_EQUAL = 1      # 三次方程式func の値

# 三次方程式func
def func(x)
  return x**3 + x**2 + x
end

x = 0  # 仮定解x
i = 0  # 計算回数カウンタ

while func(x) <= FUNC_EQUAL do  # FUNC_EQUAL に到達するまでぶん回し
  x += EPSILON
  i += 1
end

puts "#{x}:[#{i}]" # 0.5436899999947967:[543690]

次に、昨日は書けなかった再帰による二分探索。
線形探索と同じ答えに至るのに20ステップの計算で済んでいます。
およそ27184.5倍の差。
これが適切なアルゴリズムを選択することの威力です。 ^*01気をつけて欲しいのですが、決して二分探索が線形探索に優れているという単純な話ではありません。用途にあったアルゴリズムを選びましょうという話なのです。

EPSILON = 0.000001  # 近似値イプシロン
FUNC_EQUAL = 1      # 三次方程式func の値

# 三次方程式func
def func(x)
  return x**3 + x**2 + x
end

def search_x(start, stop, i)
  i += 1  # 計算回数カウンタ
  
  # start:stop 間を二分する値を仮定解xとして設定
  x = (stop.to_f - start.to_f) / 2 + start.to_f
  
  # 再帰停止条件（仮定解xによるfunc(x)の値がFUNC_EQUAL に対して近似値内に到達）
  if FUNC_EQUAL < 0 || (func(x) - FUNC_EQUAL).abs < EPSILON then
    puts "#{x}:[#{i}]"  # 0.5436887741088867:[20]
    return x
  end
  
  # 再帰継続
  # 仮定解x によるfunc(x)の値がFUNC_EQUAL より大きい
  if func(x) > FUNC_EQUAL then
    # 探索範囲の終端（stop）を仮定解x まで引き下げて再帰
    return search_x(start, x, i)
  # 仮定解x によるfunc(x)の値がFUNC_EQUAL 以下
  else
    # 探索範囲の先頭（start）を仮定解x まで引き上げて再帰
    return search_x(x, stop, i)
  end
end

search_x(0, FUNC_EQUAL, 0)

恥ずかしながら、これまで再帰はちゃんと書けていなかったのですが、ようやく何とかなる様になってきました。
まだスタックオーバーフローの回避とか意識せねばならんことはありますが、目を背けずに身に付けて行こう。

余談

上の２つのコードですが、イプシロン値を小さくして行くと、まさに指数関数的に処理ステップの差が開いていきます。