Route 477

■ [ruby] 円周率を頭から順に計算するやつをRuby 2.0に移植してみた

• Island Life - Unbounded spigot algorithm

Ruby 2.0に入る予定のEnumerable#lazyを使って移植してみた。*1

def stream(nxt, safe, prod, cons, seed, strm)
  Enumerator.new{|yielder|
    loop do
      y = nxt[seed]
      if safe[seed, y]
        seed = prod[seed, y]
        yielder << y
      else
        seed = cons[seed, strm.next]
      end
    end
  }
end

def extr(a, x)
  q, r, s, t = *a
  return (Rational(q) * x + Rational(r)) / (Rational(s) * x + Rational(t))
end

UNIT = [1, 0, 0, 1]

def comp(a, b)
  q, r, s, t = *a
  u, v, w, x = *b
  return [q*u+r*w, q*v+r*x, s*u+t*w, s*v+t*x]
end

def pi
  init = UNIT
  lfts = (1..Float::INFINITY).lazy.map{|k| [k, 4*k+2, 0, 2*k+1]}
  nxt = ->(z){ extr(z, 3).floor }  # Integer -> Integer
  safe = ->(z, n){ n == extr(z, 4).floor }  # Integer, Integer -> bool
  prod = ->(z, n){ comp([10, -10*n, 0, 1], z) }
  cons = ->(z, zz){ comp(z, zz)}
  return stream(nxt, safe, prod, cons, init, lfts)
end

p pi.take(100)

• https://gist.github.com/3162627

ほぼHaskell版の素移植。最初、「%」をmodだと勘違いしていてちょっと手間取った。

 lfts = (1..Float::INFINITY).lazy.map{|k| [k, 4*k+2, 0, 2*k+1]}

という行がlazyの使用例で、1..∞という無限Rangeをmapして無限列を作っている。

で、streamというメソッドがこの無限列を円周率の各桁を表す無限列([3,1,4,1,5,...])に変換するのだけど、 こっちはなんかうまく書けなくてEnumerator.newを使った。最初はlazy.mapで書けるのかと思ったのだが、 1桁求めるのに元の列を複数個消費するので、mapではだめそうだった。