Generic Programming(Ruby)
- 作者: Alexander A. Stepanov,Daniel E. Rose,株式会社クイープ
- 出版社/メーカー: 翔泳社
- 発売日: 2015/05/19
- メディア: 単行本(ソフトカバー)
- この商品を含むブログ (9件) を見る
第二章
掛け算
# ----- 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