【Elixirで学ぶCS】Elixirで加算器を実装するまで

なにこれ(既視感

前回の記事の続編です

www.okb-shelf.work

まだ挫折してないです

www.oreilly.co.jp

この本を勉強しているつもりなのですが、普通に難しい
僕のレベルが低いのもあるが、説明があるようでなかったりと結局ググらないと分からない部分が多い
まぁ、そこは自分で実装して理解しろやってコンセプトなんだと思いますがね

加算器について

数日前は唸りに唸って考えていたが、今思えば何も難しくなくてやっていることはシンプルだった
「ただの足し算マシーン」ということでした

一応の専門用語として

carry(桁上がり)
sum(下の例では1桁目の値)

というものがある以下の例を見て頂きたい。aとbはそれぞれ入力値を指している

a	b	carry	sum
1	0	0	1
0	0	0	0
1	1	1	0

ただの2進数の足し算でしかない
a+bが2になった時に桁上がりが発生するため、条件a = b = 1のときにcarryの値が1になっており
sumの値が0になっている
普段使っている10進数の計算となんら変わらないということが伝われば幸いです

今行ったこの演算をするための演算器を半加算器というそうです

しかしながら半加算器のみではcarry(桁上がり)の値を次の加算に用いることが出来ない
どういうことかというと

a0 = 1
b0 = 1
carry0 = 1
sum0 = 0

#carry(桁上がりなので10)を用いて半加算器でもう一度、加算を行う
a1(先ほどのcarry値) = 1
b1 = 1
carry1 = 1
sum = 0

せっかくの桁上がりが消滅して、また同じ桁で加算を行ってしまっている
これだと役に立たないので桁上がりを考慮した加算器が必要になる
それが全加算器とよばれるもので桁上がりを考慮した加算器というわけになる

全加算器では入力がa, bに合わせてz(桁上がり値)の3つを受け取る
イメージしやすいように先に論理表をお見せする

a	b	z	carry	sum
1	0	0	0	1
1	1	0	1	0
1	0	1	1	0
1	1	1	1	1

見てお判りかと思うが、単にa+bの加算を行った後にzを加算しているだけ
zを桁上がり値と見なせば全加算器と半加算器を組み合わせれば
上手く桁上がりを考慮した加算器が作れそうだと思う

#半加算器の加算
a0 = 1
b0 = 1
carry0 = 1 = z
sum0 = 0 

#全加算器の加算
a1 = 1
b1 = 1
z = 1
carry = 1
sum = 1

全加算器を複数個用意すれば、複数桁の加算を行うことが可能となる

elixirでの実装

まずはcarryとsumを求める関数を作成する
このcarryとsumはそれぞれ

carry = andゲート
sum = xorゲート

の出力に等しい
carryは入力が(1, 1)の時に1を返す
sumは入力が(1, 0)もしくは(0, 1)の時に1を返すため上記が当てはまる

前回に実装した論理ゲートを用いてそれぞれを無名関数で実装するとこんな感じに

sum_ = fn x, y -> RogicalGate.xor_(x,y) end
carry_ = fn x, y -> RogicalGate.and_(x,y) end

で、あとはこいつらを組み合わせて半加算器を作成する
(回路図はググってね)

half_adder = fn x, y -> {carry_.(x,y), sum_.(x,y)} end

タプルで返していることに深い意味はない(戻り値の要素が4以下だったのでタプルを採用)
簡単なテストを実行してみる

half_adder_test = [
  half_adder.(0, 0) == {0, 0},
  half_adder.(0, 1) == {0, 1},
  half_adder.(1, 0) == {0, 1},
  half_adder.(1, 1) == {1, 0}
]

IO.inspect(half_adder_test)
[true, true, true, true]

いいね
続いて全加算器を実装する
回路上では2つの半加算器を用意して、それぞれの出力をorに通すことで作成可能
(回路図はググってね)

all_adder = fn x, y, z ->
  {res1_x, res1_y} = half_adder.(x, y)
  {res2_x, res2_y} = half_adder.(res1_y, z)
  {RogicalGate.or_(res1_x, res2_x), res2_y}
end

同様に簡単なテストを実行する

all_adder_test = [
  all_adder.(0,0,0) == {0,0},
  all_adder.(0,1,0) == {0,1},
  all_adder.(1,0,0) == {0,1},
  all_adder.(1,1,0) == {1,0},
  all_adder.(0,0,1) == {0,1},
  all_adder.(0,1,1) == {1,0},
  all_adder.(1,0,1) == {1,0},
  all_adder.(1,1,1) == {1,1},
]

IO.inspect(all_adder_test)
[true, true, true, true, true, true, true, true]

いいね
先ほども述べたように後は全加算器を追加していくだけで演算の桁を増やすことが可能であり
試しに4bitの加算器を作成してみた(4桁目はcarry用(桁上がり))

bit_adder_4 = fn [a0, b0], [a1, b1], [a2, b2] ->
  {c0, s0} = half_adder.(a0, b0)
  {c1, s1} = all_adder.(a1, b1, c0)
  {c2, s2} = all_adder.(a2, b2, c1)
  [c2, s2, s1, s0]
end

IO.inspect(bit_adder_4.([1,1], [1,1], [1,1]))
[1, 1, 1, 0]

引数は以下のように捉えて頂きたい

  1 1 1  
+ 1 1 1  
--------  
 1 1 1 0

4bitにもなるとテストパターンが多すぎるので割愛
せっかくなのでnbitに対応する加算器も作ってみた

今まで作成したcarryやらhalf_adderを全てモジュール内関数に置き換えている
すっきりしたね
nbit対応には再帰関数を使用しているが、Enum.reduceとかで書ける気がする

defmodule NbitAdder do
  def sum_(x, y), do: RogicalGate.xor_(x,y)
  def carry_(x, y), do: RogicalGate.and_(x,y)
  def half_adder(x, y), do: {carry_(x,y), sum_(x,y)}
  def full_adder(x, y, z) do
    {res1_x, res1_y} = half_adder(x, y)
    {res2_x, res2_y} = half_adder(res1_y, z)
    {RogicalGate.or_(res1_x, res2_x), res2_y}
  end
  #例外処理: 引数が不正な場合に:errorを返す
  def nbit_adder([]), do: :error
  def nbit_adder([[]]), do: :error
  def nbit_adder([[a0, b0] | tail]) do
    {c0, s0} = half_adder(a0, b0)
    _nbit_adder(tail, c0, [s0])
  end
  
  #再帰関数: リストが空になったら終了
  defp _nbit_adder([], carry, accum), do: [carry] ++ accum
  defp _nbit_adder([[a1, b1] | tail], carry, accum) do
    {c0, s0} = full_adder(a1, b1, carry)
    _nbit_adder(tail, c0, [s0] ++ accum)
  end
end

基本的に難しいことは特にやってなくて、算出した結果をaccumlatorに随時、追加しているだけである
再帰関数が終了した際に、carryの値を加えるのを忘れたぐらいで割とスラスラ書けた
とりあえず、何か実行してみる

res1 = NbitAdder.nbit_adder([[1,1], [1, 1], [1,1], [1,1]])
IO.inspect(res)

#[1, 1, 1, 1, 0]

res2 = NbitAdder.nbit_adder([[1,0], [0, 1], [1,1], [1,0]])
IO.inspect(res)

#[1, 0, 0, 0, 1]