多項式を計算するホーナー法をElixirで実装する

授業で教えているホーナー法という，多項式を効率よく計算するアルゴリズムをElixirで実装してみましたので，報告します．

解答例

$a_0 x^n + a_1 x^{n - 1} + a_2 x^{n - 2} \cdots + a_{n - 2} x^2 + a_{n - 1} x + a_n$ を計算するのですが，リストaとして $[a_0, a_1, a_2, \cdots, a_{n - 2}, a_{n - 1}, a_n ]$ を与えます．

fn [h | t], x ->
  Enum.reduce(t, h, fn a, y -> y * x + a end)
end

解説

ホーナー法は次のようなアルゴリズムです．

• $y_k = a_0 x^k + a_1 x^{k - 1} + \cdots + a_{k - 1} x + a_{k}$ と定義する．
• $y_k$は次の漸化式で表せる
  • $y_0 = a_0$
  • $y_k = y_{k - 1} x + a_k$

そこで，t すなわち リスト$[a_1, a_2, \cdots, a_{n - 1}, a_n]$に対して，初期値h すなわち $a_0$ を初期値として，漸化式 fn a, y -> y * x + a を累積するEnum.reduce/3 を計算します．

ホーナー法が，Elixirだとこんなにも単純に書けるのは，少し感動しますね．

応用

先ほどの式を変形して，次のように定義します．

fn [h | t] ->
  fn x ->
    Enum.reduce(t, h, fn a, y -> y * x + a end)
  end
end

この関数をfとすると，次のようにすると，$g(x) = x^2 + 2x + 1$ を計算する関数gを得ることができます．

g = f.([1, 2, 1])

iex> g.(1)
4
iex> g.(2)
9
iex> g.(3)
16

ちなみに，このような手法をカリー化と言います．