| -- 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 |