From Mathematics to Generic Programming

pr0201.rb

# coding: utf-8
# See Book "http://ptgmedia.pearsoncmg.com/images/9780321942043/samplepages/9780321942043.pdf"
#          "From Mathematics to Generic Programming"

def odd?(n)
  (n & 1) == 1
end
def half(n)
  n >> 1
end

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

def mult_acc0(r, n, a)
  return r + a if n == 1
  r2 = odd?(n)? r + a : r
  mult_acc0(r2, half(n), a + a)
end

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

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

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

def mult_acc4(r, n, a)
  while true
    if (odd?(n))
      r = r + a
      return r if n == 1
    end
    n = half(n)
    a += a
  end
  a
end

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

def multiply3(n, a)
  while(!odd?(n))
    a += a
    n = half(n)
  end
  return a if n == 1
  mult_acc4(a, n - 1, a)
end

def multiply4(n, a)
  while(!odd?(n))
    a += a
    n = half(n)
  end
  return a if n == 1
  mult_acc4(a, half(n - 1), a + a)
end


TESTS = [
  [1, 2, 1 * 2],
  [3, 2, 3 * 2],
  [3, 3, 3 * 3],
  [3, 4, 3 * 4],
  [3, 5, 3 * 5],
]

TESTS.each do |t|
  result1 = multiply1(t[0], t[1])
  result2 = multiply2(t[0], t[1])
  result3 = multiply3(t[0], t[1])
  result4 = multiply4(t[0], t[1])
  resulta0 = mult_acc0(0, t[0], t[1])
  resulta1 = mult_acc1(0, t[0], t[1])
  resulta2 = mult_acc2(0, t[0], t[1])
  resulta3 = mult_acc3(0, t[0], t[1])
  resulta4 = mult_acc4(0, t[0], t[1])

  puts "# fail 1  #{t[0]} * #{t[1]} = #{result1} (!= #{t[2]})"  if result1 != t[2]
  puts "# fail 2  #{t[0]} * #{t[1]} = #{result2} (!= #{t[2]})"  if result2 != t[2]
  puts "# fail 3  #{t[0]} * #{t[1]} = #{result3} (!= #{t[2]})"  if result3 != t[2]
  puts "# fail 4  #{t[0]} * #{t[1]} = #{result4} (!= #{t[2]})"  if result4 != t[2]
  puts "# fail a0 #{t[0]} * #{t[1]} = #{resulta0} (!= #{t[2]})" if resulta0 != t[2]
  puts "# fail a1 #{t[0]} * #{t[1]} = #{resulta1} (!= #{t[2]})" if resulta1 != t[2]
  puts "# fail a2 #{t[0]} * #{t[1]} = #{resulta2} (!= #{t[2]})" if resulta2 != t[2]
  puts "# fail a3 #{t[0]} * #{t[1]} = #{resulta3} (!= #{t[2]})" if resulta3 != t[2]
  puts "# fail a4 #{t[0]} * #{t[1]} = #{resulta4} (!= #{t[2]})" if resulta4 != t[2]
end

pr0301.rb

# coding: utf-8
# See Book "http://ptgmedia.pearsoncmg.com/images/9780321942043/samplepages/9780321942043.pdf"
#          "From Mathematics to Generic Programming"

require 'prime'

class Sieve
  # 奇数 (first * 2 + 3 .. last + 2 + 3) に対応する配列をつくる。
  def initialize(first, last)
    @first = first
    @last  = last
    @set = Array.new(last - first, '')
  end

  # idx 番目の要素の値を val に設定する。
  def set_sieve(idx, val)
    @set[idx - @first] = val
  end

  # 配列の値を表示する。
  def show
    num = 2 * @first + 1
    @set.each_with_index do |val, idx|
      puts "#{2 * (idx + @first) + 3} #{val}"
    end
  end

  # 素数を表示する。
  def show_prime
    str = ''
    num = 2 * @first + 1
    @set.each_with_index do |val, idx|
      num += 2
      str += "#{num} " if val == ''
      if str.length > 70
        puts str
        str = ''
      end
    end
  end

  # palindromic な素数の値を表示する。
  def show_palindrom(base = 10)
    @set.each_with_index do |s, idx|
      if s == ''
        str = (2 * (idx + @first) + 3).to_s(base)
        puts str if str.reverse == str
      end
    end
  end

  def to_a
    a = []
    @set.each_with_index do |s, idx|
      a << 2 * (idx + @first) + 3 if s == ''
    end
    a
  end

  # first + factor * n (n = 0, ,..) 版目の要素の値を false にする。
  def mark_sieve(first, last, factor)
    puts "--- mark_sieve #{first}, #{last}, #{factor}"
    set_sieve(first, false)
    while(last - first > factor)
      first += factor
      set_sieve(first, false)
    end
  end

  def sift0(first, last)
    i = 0
    index_square = 3
    factor = 3
    while index_square < last
      if @set[i] == ''
        mark_sieve(first + index_square, last, factor)
      end
      i += 1
      index_square += factor
      factor += 2            # i + i + 3
      index_square += factor # 2 * i * (i + 3) + 3
    end
  end

  # ruby の prime クラスでの素数列挙の結果と比較
  # =============================================
  def check_ruby_prime
    a = self.to_a
    ps =  Prime.each(@last * 2 + 1).to_a
    # puts "a.size = #{a.size}"
    # puts "ps[1..-1].size = #{ps[1..-1].size}"

    #ps[1..-1].each_with_index do |p, idx|
    #  puts "ps [#{p}],  [#{a[idx]}]" if p != a[idx]
    #end
    #a.each_with_index do |p, idx|
    #  puts "a  [#{p}],  [#{ps[idx + 1]}]" if p != ps[idx + 1]
    #end
    puts "check_ruby_prime: #{ps[1..-1] == a}"
  end
end

first, last = 0, 1000
sieve = Sieve.new(first, last)
sieve.sift0(first, last)
# sieve.show
sieve.show_prime
# sieve.show_palindrom
# sieve.show_palindrom(16)
sieve.check_ruby_prime