Generic Programming(Ruby)

その数式、プログラムできますか?

その数式、プログラムできますか?

 

第二章

掛け算

# ----- 2.1
# na
def multiply0(n, a)
  return a if n == 1
  multiply0(n - 1, a) + a
end

# na
def multiply1(n, a)
  return a if n == 1
  result = multiply1(half(n), a + a)
  result += a if odd(n)
  result
end

# 奇数か
def odd(n)
  (n & 0x1) != 0
end

# 2で割る
def half(n)
  n >> 1
end


# ----- 2.2
# r + na
def mult_acc0(r, n, a)
  return r + a if n == 1
  if odd(n)
    mult_acc0(r + a, half(n), a + a)
  else
    mult_acc0(r, half(n), a + a)
  end
end

# r + na
def mult_acc1(r, n, a)
  return r + a if n == 1
  r += a if odd(n)
  mult_acc1(r, half(n), a + a)
end

# r + na
def mult_acc2(r, n, a)
  if odd(n)
    r += a
    return r if n == 1
  end
  mult_acc2(r, half(n), a + a)
end

# r + na
def mult_acc3(r, n, a)
  if odd(n)
    r += a
    return r if n == 1
  end
  n = half(n)
  a += a
  mult_acc3(r, n, a)
end

# r + na(最終形)
def mult_acc4(r, n, a)
  loop do
    if odd(n)
      r += a
      return r if n == 1
    end
    n = half(n)
    a += a
  end
end

# na
def multiply2(n, a)
  return a if n == 1
  mult_acc4(a, n - 1, a)
end

# na
def multiply3(n, a)
  while not odd(n)
    a += a
    n = half(n)
  end
  return a if n == 1
  mult_acc4(a, n - 1, a)
end

# na(最終形)
def multiply4(n, a)
  while not odd(n)
    a += a
    n = half(n)
  end
  return a if n == 1
  mult_acc4(a, half(n - 1), a + a)
end

 

第三章

エラトステネスの篩

# ----- 3.3
def mark_sieve(first, last, factor)
  @bool[first] = false
  while last - first > factor
    first += factor
    @bool[first] = false
  end
end

def shift0(first, n)
  @bool.fill(true, first..(first + n))
  i = 0
  index_square = 3
  while index_square < n
    mark_sieve(first + index_square, first + n, i + i + 3) if @bool[i]
    i += 1
    index_square = 2 * i * (i + 3) + 3
  end
end

def shift1(first, n)
  last = first + n
  @bool.fill(true, first..last)
  i = 0
  index_square = 3
  factor = 3
  while index_square < n
    mark_sieve(first + index_square, last, factor) if @bool[i]
    i += 1
    factor = i + i + 3
    index_square = 2 * i * (i + 3) + 3
  end
end

# 最終形
def shift(first, n)
  last = first + n
  @bool.fill(true, first..last)
  i = 0
  index_square = 3
  factor = 3
  while index_square < n
    mark_sieve(first + index_square, last, factor) if @bool[i]
    i += 1
    index_square += factor
    factor += 2
    index_square += factor
  end
end

@bool = Array.new(100)
shift(0, 100 - 1)

prime = []
@bool.each_with_index {|bl, i| prime << i * 2 + 3 if bl}
p prime