xのn乗を計算する2進分解法をElixirで実装する

授業で教えている2進分解法という，$x$と正の整数$n$に対する$x^n$を計算するアルゴリズムをElixirで実装してみましたので，報告します．

解答例

fn x, n ->
  Stream.unfold(n, fn
      0 -> nil
      n -> {Bitwise.band(n, 1), Bitwise.bsr(n, 1)}
  end)
  |> Enum.reduce({1, x}, fn
    0, {r, x} -> {r, x * x}
    1, {r, x} -> {r * x, x * x}
  end)
  |> elem(0)
end

解説

Stream.unfold/2を使って，下記のようにすることで，nを下位ビットから順番にビットを取り出したリストのStreamを生成し，上位ビットが全て0になったら終了します．

Stream.unfold(n, fn
    0 -> nil
    n -> {Bitwise.band(n, 1), Bitwise.bsr(n, 1)}
end)

このリストに対し，初期値{r, x} = {1, x}として，Enum.reduce/3によって，次のロジックで繰り返します．

• ビットが0の時には，{r, x} = {r, x * x}とする
• ビットが1の時には，{r, x} = {r * x, x * x}とする

最後に，elem/2を使って，rのみを取り出します．

余談

Stream.unfold/2のドキュメントの例題がわかりやすくなったと思いませんか？ 実はこれは私 @zacky1972 の提案によるものです！