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     var _z: Transformation
  26     var _x: Transformation
  27     var _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     fun 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     fun 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     fun digit: Int
  62         do
  63             return _z.extract(3)
  64         end
  65
  66     fun is_safe(digit: Int): Bool
  67         do
  68             return digit == _z.extract(4)
  69         end
  70
  71     fun produce(i: Int): Transformation
  72         do
  73             return _inverse.qrst(10,-10*i,0,1).compose(_z)
  74         end
  75
  76     fun consume(a: Transformation): Transformation
  77         do
  78             return _z.compose(a)
  79         end
  80 end
  81
  82
  83 class Transformation
  84     var _q: Int
  85     var _r: Int
  86     var _s: Int
  87     var _t: Int
  88     var _k: Int
  89
  90     init(q: Int, r: Int, s: Int, t: Int)
  91         do
  92             set(q, r, s, t)
  93         end
  94
  95     fun set(q: Int, r: Int, s: Int, t: Int)
  96         do
  97             _q = q
  98             _r = r
  99             _s = s
 100             _t = t
 101             _k = 0
 102         end
 103
 104
 105     fun next: Transformation
 106         do
 107             _k = _k + 1
 108             _q = _k
 109             _r = 4 * _k + 2
 110             _s = 0
 111             _t = 2 * _k + 1
 112             return self
 113         end
 114
 115     fun extract(j: Int): Int
 116         do
 117             return (_q * j + _r) / (_s * j + _t)
 118         end
 119
 120     fun compose(a: Transformation): Transformation
 121         do
 122             return new Transformation(
 123                 _q * a._q,
 124                 _q * a._r + _r * a._t,
 125                 _s * a._q + _t * a._s,
 126                 _s * a._r + _t * a._t
 127                 )
 128         end
 129
 130     fun qrst(q: Int, r: Int, s: Int, t: Int): Transformation
 131         do
 132             set(q, r, s, t)
 133             return self
 134         end
 135 end
 136
 137
 138 var witdh = 10
 139 var n = args.first.to_i
 140 var j = 0
 141
 142 var digits = new PiDigitSpigot
 143
 144 while n > 0 do
 145     if n >= witdh then
 146         for i in [0..witdh[ do
 147             printn(digits.next)
 148         end
 149         j = j + witdh
 150     else
 151         for i in [0..n[ do
 152             printn(digits.next)
 153         end
 154         for i in [n..witdh[ do
 155             printn(" ")
 156         end
 157         j = j + n
 158     end
 159     print("\t:{j}")
 160     n = n - witdh
 161 end