lib/ruby-1.9.1-rc1/benchmark/bm_so_pidigits.rb

   1 # The Great Computer Language Shootout
   2 # http://shootout.alioth.debian.org/
   3 #
   4 # contributed by Gabriele Renzi
   5
   6 class PiDigitSpigot
   7
   8     def initialize()
   9         @z = Transformation.new 1,0,0,1
  10         @x = Transformation.new 0,0,0,0
  11         @inverse = Transformation.new 0,0,0,0
  12     end
  13
  14     def next!
  15         @y = @z.extract(3)
  16         if safe? @y
  17             @z = produce(@y)
  18             @y
  19         else
  20             @z = consume @x.next!()
  21             next!()
  22         end
  23     end
  24
  25     def safe?(digit)
  26         digit == @z.extract(4)
  27     end
  28
  29     def produce(i)
  30         @inverse.qrst(10,-10*i,0,1).compose(@z)
  31     end
  32
  33     def consume(a)
  34         @z.compose(a)
  35     end
  36 end
  37
  38
  39 class Transformation
  40     attr_reader :q, :r, :s, :t
  41     def initialize (q, r, s, t)
  42         @q,@r,@s,@t,@k = q,r,s,t,0
  43     end
  44
  45     def next!()
  46         @q = @k = @k + 1
  47         @r = 4 * @k + 2
  48         @s = 0
  49         @t = 2 * @k + 1
  50         self
  51     end
  52
  53     def extract(j)
  54         (@q * j + @r) / (@s * j + @t)
  55     end
  56
  57     def compose(a)
  58         self.class.new( @q * a.q,
  59                         @q * a.r + r * a.t,
  60                         @s * a.q + t * a.s,
  61                         @s * a.r + t * a.t
  62                     )
  63     end
  64
  65     def qrst *args
  66         initialize *args
  67         self
  68     end
  69
  70
  71 end
  72
  73
  74 WIDTH = 10
  75 n = 2_500 # Integer(ARGV[0])
  76 j = 0
  77
  78 digits = PiDigitSpigot.new
  79
  80 while n > 0
  81     if n >= WIDTH
  82         WIDTH.times {print digits.next!}
  83         j += WIDTH
  84     else
  85         n.times {print digits.next!}
  86         (WIDTH-n).times {print " "}
  87         j += n
  88     end
  89     puts "\t:"+j.to_s
  90     n -= WIDTH
  91 end
  92