function isInCircle(x, y)
    return x*x + y*y < 1
end

function monteCarlo(N)
    local inCircle = 0
    for i=0,N do
        if isInCircle(math.random(), math.random()) then
            inCircle = inCircle + 1
        end
    end
    return inCircle/N*4
end

function deterministicCircle(N)
    local inCircle = 0
    for j=0,N do
        local m = 0
        for i=0,N do
            local x,y = i/N, j/N
            if isInCircle(x,y) then
                inCircle = inCircle + 1
                m = i
            end
        end
    end
    return inCircle/(N*N)*4
end

function dichoFind(a, b, f)
    local m = math.floor((a+b)/2)
    if a == m then return m end
    if f(m) then
        return dichoFind(m,b,f)
    else
        return dichoFind(a,m,f)
    end
end

function dichoCircle(N)
    local isIntCircle = function(j)
        return function(i)
            local x,y = i/N, j/N
            return isInCircle(x,y)
        end
    end

    local inCircle = 0
    for j=0,N do
        local i = dichoFind(0,N,isIntCircle(j))
        inCircle = inCircle + i + 1
    end
    return inCircle/(N*N)*4
end

t1 = os.clock()
r = monteCarlo(1000*1000*1000)
t2 = os.clock()
print(string.format("monte carlo   : %.10f\t%.2fs", r, t2-t1))

t1 = os.clock()
r = deterministicCircle(1000*100*2)
t2 = os.clock()
print(string.format("deterministic : %.10f\t%.2fs", r, t2-t1))

t1 = os.clock()
r = dichoCircle(1000*100*2)
t2 = os.clock()
print(string.format("dichotomique  : %.10f\t%.2fs", r, t2-t1))