tests/shootout_pidigits.nit

   1 # This file is part of NIT ( http://www.nitlanguage.org ).
   2 #
   3 # Copyright 2005-2008 Jean Privat <jean@pryen.org>
   4 #
   5 # Licensed under the Apache License, Version 2.0 (the "License");
   6 # you may not use this file except in compliance with the License.
   7 # You may obtain a copy of the License at
   8 #
   9 #     http://www.apache.org/licenses/LICENSE-2.0
  10 #
  11 # Unless required by applicable law or agreed to in writing, software
  12 # distributed under the License is distributed on an "AS IS" BASIS,
  13 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14 # See the License for the specific language governing permissions and
  15 # limitations under the License.
  16
  17 # The Comptuer Language Shootout Benchmarks
  18 # http://shootout.alioth.debian.org
  19 #
  20 # contributed by Jean Privat
  21
  22 # Incorrect without bignums
  23
  24 class PiDigitSpigot
  25     attr _z: Transformation
  26     attr _x: Transformation
  27     attr _inverse: Transformation
  28
  29
  30     init
  31         do
  32             _z = new Transformation(1,0,0,1)
  33             _x = new Transformation(0,0,0,0)
  34             _inverse = new Transformation(0,0,0,0)
  35         end
  36
  37
  38     meth next: Int
  39         do
  40             var y = digit
  41             if is_safe(y) then
  42                 _z = produce(y)
  43                 return y
  44             else
  45                 _z = consume(_x.next)
  46                 return next
  47             end
  48         end
  49
  50     meth next_: Int
  51         do
  52             var y = digit
  53             while not is_safe(y) do
  54                 _z = consume(_x.next)
  55                 y = digit
  56             end
  57             _z = produce(y)
  58             return y
  59         end
  60
  61     meth digit: Int
  62         do
  63             return _z.extract(3)
  64         end
  65
  66     meth is_safe(digit: Int): Bool
  67         do
  68             return digit == _z.extract(4)
  69         end
  70
  71     meth produce(i: Int): Transformation
  72         do
  73             return _inverse.qrst(10,-10*i,0,1).compose(_z)
  74         end
  75
  76     meth consume(a: Transformation): Transformation
  77         do
  78             return _z.compose(a)
  79         end
  80 end
  81
  82
  83 class Transformation
  84     attr _q: Int
  85     attr _r: Int
  86     attr _s: Int
  87     attr _t: Int
  88     attr _k: Int
  89
  90
  91     init(q: Int, r: Int, s: Int, t: Int)
  92         do
  93             _q = q
  94             _r = r
  95             _s = s
  96             _t = t
  97             _k = 0
  98         end
  99
 100
 101     meth next: Transformation
 102         do
 103             _k = _k + 1
 104             _q = _k
 105             _r = 4 * _k + 2
 106             _s = 0
 107             _t = 2 * _k + 1
 108             return self
 109         end
 110
 111     meth extract(j: Int): Int
 112         do
 113             return (_q * j + _r) / (_s * j + _t)
 114         end
 115
 116     meth compose(a: Transformation): Transformation
 117         do
 118             return new Transformation(
 119                 _q * a._q,
 120                 _q * a._r + _r * a._t,
 121                 _s * a._q + _t * a._s,
 122                 _s * a._r + _t * a._t
 123                 )
 124         end
 125
 126     meth qrst(q: Int, r: Int, s: Int, t: Int): Transformation
 127         do
 128             init(q, r, s, t)
 129             return self
 130         end
 131 end
 132
 133
 134 var witdh = 10
 135 var n = args.first.to_i
 136 var j = 0
 137
 138 var digits = new PiDigitSpigot
 139
 140 while n > 0 do
 141     if n >= witdh then
 142         for i in [0..witdh[ do
 143             printn(digits.next)
 144         end
 145         j = j + witdh
 146     else
 147         for i in [0..n[ do
 148             printn(digits.next)
 149         end
 150         for i in [n..witdh[ do
 151             printn(" ")
 152         end
 153         j = j + n
 154     end
 155     print("\t:{j}")
 156     n = n - witdh
 157 end