Adder and Multiplier

adder-and-multiplier.vim

"
" Wikipedia - 加算器
" https://ja.wikipedia.org/wiki/%E5%8A%A0%E7%AE%97%E5%99%A8
"
" Wikipedia - 乗算機
" https://ja.wikipedia.org/wiki/%E4%B9%97%E7%AE%97%E5%99%A8
"

function! s:run() abort
  for [anum, bnum] in [
  \  [3, 7],
  \  [255, 1]
  \]
    echo '-------------- '.anum.' + '.bnum.' --------------'
    call s:do_add(anum, bnum, 1)
  endfor

  for [anum, bnum] in [
  \  [3, 3],
  \  [255, 2]
  \]
    echo '-------------- '.anum.' * '.bnum.' --------------'
    call s:do_multiply(anum, bnum, 1)
  endfor
endfunction

function! s:do_add(anum, bnum, verbose) abort
  let a = s:nr2bits(a:anum, 8)
  let b = s:nr2bits(a:bnum, 8)
  if a:verbose
    echo 'a =' string(a)
    echo 'b =' string(b)
  endif
  let r = s:add(a, b, a:verbose)
  if a:verbose
    echo 'r =' r
  endif
  echo 'r = a('.a:anum.') + b('.a:bnum.') =' s:bits2num(r)
endfunction

function! s:do_multiply(anum, bnum, verbose) abort
  let a = s:nr2bits(a:anum, 8)
  let b = s:nr2bits(a:bnum, 8)
  if a:verbose
    echo 'a =' string(a)
    echo 'b =' string(b)
  endif
  let r = s:multiply(a, b, a:verbose)
  if a:verbose
    echo 'r =' r
  endif
  echo 'r = a('.a:anum.') * b('.a:bnum.') =' s:bits2num(r)
endfunction

function! s:add(a, b, verbose) abort
  let [a, b] = [a:a, a:b]
  let r = repeat([0], 9)
  " 1 digit
  let result = s:half_adder(a[s:dig(1, a)], b[s:dig(1, b)])
  if a:verbose
    echo '[a[0], b[0], carry, result] =' string([a[s:dig(1, a)], b[s:dig(1, b)], 0, '->', result])
  endif
  let r[s:dig(1, r)] = result.sum
  let carry = result.carry
  " 2 digit later
  for i in range(1, 7)
    let result = s:full_adder(a[s:dig(i+1, a)], b[s:dig(i+1, b)], carry)
    if a:verbose
      echo '[a['.i.'], b['.i.'], carry, result] =' string([a[s:dig(i+1, a)], b[s:dig(i+1, b)], carry, '->', result])
    endif
    let r[s:dig(i+1, r)] = result.sum
    let carry = result.carry
  endfor
  let r[s:dig(9, r)] = carry
  return r
endfunction

function! s:half_adder(n, m) abort
  return {'sum': xor(a:n, a:m), 'carry': and(a:n, a:m)}
endfunction

function! s:full_adder(n, m, c) abort
  let ab = s:half_adder(a:n, a:m)
  let abc = s:half_adder(ab.sum, a:c)
  return {'sum': abc.sum, 'carry': or(ab.carry, abc.carry)}
endfunction

function! s:multiply(a, b, verbose) abort
  let [a, b] = [a:a, a:b]
  let p = [
  \ map(copy(b), 'and(a[7], v:val)'),
  \ map(copy(b), 'and(a[6], v:val)'),
  \ map(copy(b), 'and(a[5], v:val)'),
  \ map(copy(b), 'and(a[4], v:val)'),
  \ map(copy(b), 'and(a[3], v:val)'),
  \ map(copy(b), 'and(a[2], v:val)'),
  \ map(copy(b), 'and(a[1], v:val)'),
  \ map(copy(b), 'and(a[0], v:val)')
  \]
  if a:verbose
    for i in range(len(p))
      echo 'p['.i.'] =' string(p[i])
    endfor
  endif
  let r = repeat([0], 16)
  let carry = 0
  for ri in range(15)
    if ri >= 8
      let start = ri % 8 + 1
      let end = 7
    else
      let start = 0
      let end = ri
    endif
    " echo 'DEBUG [ri, start, end, carry] =' string([ri, start, end, carry])
    let r[s:dig(ri+1, r)] = carry
    let carry = 0
    for i in range(start, end)
      " echo 'p['.i.']['.(s:dig(ri-i+1, p[i])).'] =' string(p[i][s:dig(ri-i+1, p[i])])
      let r[s:dig(ri+1, r)] += p[i][s:dig(ri-i+1, p[i])]
      if r[s:dig(ri+1, r)] >= 2
        let r[s:dig(ri+1, r)] = 0
        let carry = 1
      endif
    endfor
  endfor
  let r[s:dig(15, r)] = carry
  return r
endfunction

" a:n digit of number(a:list)
function! s:dig(n, list) abort
  return len(a:list) - a:n
endfunction

function! s:nr2bits(n, least_digit) abort
  let bits = []
  let dig = 0
  let n = a:n
  while n > 0
    let d = float2nr(pow(2, dig))
    if and(n, d)
      let n -= d
      call insert(bits, 1)
    else
      call insert(bits, 0)
    endif
    let dig += 1
  endwhile
  return repeat([0], a:least_digit - len(bits)) + bits
endfunction

function! s:bits2num(bits) abort
  return str2nr(join(a:bits, ''), 2)
endfunction

call s:run()

output.txt

-------------- 3 + 7 --------------
a = [0, 0, 0, 0, 0, 0, 1, 1]
b = [0, 0, 0, 0, 0, 1, 1, 1]
[a[0], b[0], carry, result] = [1, 1, 0, '->', {'sum': 0, 'carry': 1}]
[a[1], b[1], carry, result] = [1, 1, 1, '->', {'sum': 1, 'carry': 1}]
[a[2], b[2], carry, result] = [0, 1, 1, '->', {'sum': 0, 'carry': 1}]
[a[3], b[3], carry, result] = [0, 0, 1, '->', {'sum': 1, 'carry': 0}]
[a[4], b[4], carry, result] = [0, 0, 0, '->', {'sum': 0, 'carry': 0}]
[a[5], b[5], carry, result] = [0, 0, 0, '->', {'sum': 0, 'carry': 0}]
[a[6], b[6], carry, result] = [0, 0, 0, '->', {'sum': 0, 'carry': 0}]
[a[7], b[7], carry, result] = [0, 0, 0, '->', {'sum': 0, 'carry': 0}]
r = [0, 0, 0, 0, 0, 1, 0, 1, 0]
r = a(3) + b(7) = 10
-------------- 255 + 1 --------------
a = [1, 1, 1, 1, 1, 1, 1, 1]
b = [0, 0, 0, 0, 0, 0, 0, 1]
[a[0], b[0], carry, result] = [1, 1, 0, '->', {'sum': 0, 'carry': 1}]
[a[1], b[1], carry, result] = [1, 0, 1, '->', {'sum': 0, 'carry': 1}]
[a[2], b[2], carry, result] = [1, 0, 1, '->', {'sum': 0, 'carry': 1}]
[a[3], b[3], carry, result] = [1, 0, 1, '->', {'sum': 0, 'carry': 1}]
[a[4], b[4], carry, result] = [1, 0, 1, '->', {'sum': 0, 'carry': 1}]
[a[5], b[5], carry, result] = [1, 0, 1, '->', {'sum': 0, 'carry': 1}]
[a[6], b[6], carry, result] = [1, 0, 1, '->', {'sum': 0, 'carry': 1}]
[a[7], b[7], carry, result] = [1, 0, 1, '->', {'sum': 0, 'carry': 1}]
r = [1, 0, 0, 0, 0, 0, 0, 0, 0]
r = a(255) + b(1) = 256
-------------- 3 * 3 --------------
a = [0, 0, 0, 0, 0, 0, 1, 1]
b = [0, 0, 0, 0, 0, 0, 1, 1]
p[0] = [0, 0, 0, 0, 0, 0, 1, 1]
p[1] = [0, 0, 0, 0, 0, 0, 1, 1]
p[2] = [0, 0, 0, 0, 0, 0, 0, 0]
p[3] = [0, 0, 0, 0, 0, 0, 0, 0]
p[4] = [0, 0, 0, 0, 0, 0, 0, 0]
p[5] = [0, 0, 0, 0, 0, 0, 0, 0]
p[6] = [0, 0, 0, 0, 0, 0, 0, 0]
p[7] = [0, 0, 0, 0, 0, 0, 0, 0]
r = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1]
r = a(3) * b(3) = 9
-------------- 255 * 2 --------------
a = [1, 1, 1, 1, 1, 1, 1, 1]
b = [0, 0, 0, 0, 0, 0, 1, 0]
p[0] = [0, 0, 0, 0, 0, 0, 1, 0]
p[1] = [0, 0, 0, 0, 0, 0, 1, 0]
p[2] = [0, 0, 0, 0, 0, 0, 1, 0]
p[3] = [0, 0, 0, 0, 0, 0, 1, 0]
p[4] = [0, 0, 0, 0, 0, 0, 1, 0]
p[5] = [0, 0, 0, 0, 0, 0, 1, 0]
p[6] = [0, 0, 0, 0, 0, 0, 1, 0]
p[7] = [0, 0, 0, 0, 0, 0, 1, 0]
r = [0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0]
r = a(255) * b(2) = 510