| -- The Great Computer Language Shootout |
| -- http://shootout.alioth.debian.org/ |
| -- |
| -- contributed by Isaac Gouy |
| |
| -- requires BigNum library |
| -- http://oss.digirati.com.br/luabignum/ |
| |
| |
| require( "BigNum.lua" ) ; |
| |
| -- Transformation |
| |
| local T = {} |
| |
| function T.bigzero() return BigNum.new(0) end |
| function T.bigone() return BigNum.new(1) end |
| function T.bigten() return BigNum.new(10) end |
| |
| function T.new(q,r,s,t) |
| return { |
| q = BigNum.new(q) |
| ,r = BigNum.new(r) |
| ,s = BigNum.new(s) |
| ,t = BigNum.new(t) |
| ,k = 0 |
| } |
| end |
| |
| function T.unity() return T.new(1,0,0,1) end |
| function T.zero() return T.new(0,0,0,0) end |
| |
| function T.compose(a,b) |
| local qq = T.bigzero() |
| local qr = T.bigzero() |
| local rt = T.bigzero() |
| local qrrt = T.bigzero() |
| local sq = T.bigzero() |
| local ts = T.bigzero() |
| local sqts = T.bigzero() |
| local sr = T.bigzero() |
| local tt = T.bigzero() |
| local srtt = T.bigzero() |
| |
| BigNum.mul(a.q,b.q,qq) |
| |
| BigNum.mul(a.q,b.r,qr) |
| BigNum.mul(a.r,b.t,rt) |
| BigNum.add(qr,rt,qrrt) |
| |
| BigNum.mul(a.s,b.q,sq) |
| BigNum.mul(a.t,b.s,ts) |
| BigNum.add(sq,ts,sqts) |
| |
| BigNum.mul(a.s,b.r,sr) |
| BigNum.mul(a.t,b.t,tt) |
| BigNum.add(sr,tt,srtt) |
| |
| return T.new(qq, qrrt, sqts, srtt) |
| end |
| |
| |
| function T.extract(a,j) |
| local bigj = BigNum.new(j) |
| local qj = T.bigzero() |
| local qjr = T.bigzero() |
| local sj = T.bigzero() |
| local sjt = T.bigzero() |
| local n = T.bigzero() |
| local sjt = T.bigzero() |
| |
| BigNum.mul(a.q,bigj,qj) |
| BigNum.add(qj,a.r,qjr) |
| |
| BigNum.mul(a.s,bigj,sj) |
| BigNum.add(sj,a.t,sjt) |
| |
| local d = T.bigzero() |
| local r = T.bigzero() |
| BigNum.div(qjr,sjt,d,r) |
| |
| return math.floor( tonumber( BigNum.mt.tostring(d) )) |
| end |
| |
| function T.next(a) |
| a.k = a.k + 1 |
| a.q = BigNum.new(a.k) |
| a.r = BigNum.new(4*a.k + 2) |
| a.s = T.bigzero() |
| a.t = BigNum.new(2*a.k + 1) |
| return a |
| end |
| |
| |
| -- Pi Digit Stream |
| |
| local P = {} |
| |
| function P.new() |
| return { |
| z = T.unity() |
| ,x = T.zero() |
| ,inverse = T.zero() |
| } |
| end |
| |
| function P.produce(a,j) |
| local i = a.inverse |
| i.q = T.bigten() |
| i.r = BigNum.new(-10*j) |
| i.s = T.bigzero() |
| i.t = T.bigone() |
| return T.compose(i,a.z) |
| end |
| |
| function P.consume(a,b) |
| return T.compose(a.z,b) |
| end |
| |
| function P.digit(a) |
| return T.extract(a.z,3) |
| end |
| |
| function P.isSafe(a,j) |
| return j == T.extract(a.z,4) |
| end |
| |
| function P.next(a) |
| local y |
| y = P.digit(a) |
| if P.isSafe(a,y) then |
| a.z = P.produce(a,y) |
| return y |
| else |
| a.z = P.consume(a,T.next(a.x)) |
| return P.next(a) |
| end |
| end |
| |
| |
| -- Main |
| |
| n = tonumber(arg and arg[1]) or 27 |
| i = 0 |
| length = 10 |
| pidigit = P.new() |
| |
| while n > 0 do |
| if n < length then |
| for _ = 1,n do io.write( P.next(pidigit) ) end |
| for _ = n,length do io.write( ' ' ) end |
| i = i + n |
| else |
| for _ = 1,length do io.write( P.next(pidigit) ) end |
| i = i + length |
| end |
| io.write('\t:', i, '\n') |
| n = n - length |
| end |