-- TestQuickSort
local array={}
local function QuickSort(arr,left,right)
  local  i=left
  local  j=right
  local  center=arr[math.floor((i+j)/2)]
    while i<=j do
        while(arr[i]<center and i<right) do   i=i+1  end
        while(arr[j]>center and j>left) do  j=j-1   end
        if i<=j then  local   x=arr[i]   arr[i]=arr[j]    arr[j]=x     i=i+1    j=j-1  end
    end
    if left<j then  QuickSort(arr,left,j)  end
    if right>i then  QuickSort(arr,i,right)  end
end

local function Start1()
    for i=0,MAX_SIZE-1 do  array[i]=i%100 end
    start=os.clock()
    QuickSort(array,0,MAX_SIZE-1)
    res=(os.clock()-start)*1000
    print("TestQuickSort SIZE="..MAX_SIZE..", time=" .. res .. " ms")
    for i=1,MAX_SIZE-1 do
        if array[i]<array[i-1] then  print("Array not sorted"); break;
        end
    end
end

local str=""
local a={}
local function PiCalculate(digits)
local   d = 0
local   c = (math.floor(digits/4)+1)*14
local   f = 10000
   for i=0,c do a[i]=20000000   end
   c=c-14
   b=c
   while b>0 do
      e=d%f
      d=e
      while b-1>0 do
         b=b-1
         d = d * b + a[b]
         g = (b * 2) - 1
         a[b]=(d%g)*f
            d=math.floor(d/g)
        end
        r=e+math.floor(d/f)
      if r<1000 then
         if(r>99) then
            str=str .. "0"
         else
            if(r > 9) then
               str=str .. "00"
            else
               str=str .. "000"
            end
         end
      end
      str=str .. string.format("%d",r)
      c=c-14
      b=c
   end
end

function Start2()
   start=os.clock()
   PiCalculate(MAX_SIZE)
   res=(os.clock()-start)*1000
   print("TestPiCalculated SIZE="..MAX_SIZE..", time=" .. res .." ms  Pi="..string.sub(str,1,16))
end

-- TestFibo

local fib={}
local function TestFibo(n)
   if n<2 then return 1 else return TestFibo(n-2)+TestFibo(n-1) end
end

local function Start3()
   start=os.clock()
   for i=0,MAX_SIZE-1 do    fib[i]=TestFibo(i) end
   res=(os.clock()-start)*1000
   print("TestFibo SIZE="..MAX_SIZE..", time="..res.." ms Fibo[39]="..fib[39])
end

-- TestArrays
local function Start4()
   local  x={}    local y={}
    local start=os.clock()
    for i=1,MAX_SIZE,1 do   x[i]=i  y[i]=0   end
    y[MAX_SIZE]=0
    for k=1,MAX_SIZE,1 do
        for i=MAX_SIZE, 1,-1 do  y[i]=y[i]+x[i] end
    end
    local res=(os.clock()-start)*1000
    local check=0
    for k=1,MAX_SIZE,1 do check=check+y[k]  end
    print("Test Arrays SIZE="..MAX_SIZE..", Time = "..res.." ms check=".. check)
end

local function Ackermann(m,n)
        if(m==0) then return(n+1) end
        if(n==0) then return(Ackermann(m-1,1)) end
        return(Ackermann(m-1,Ackermann(m,(n-1))))
end

-- TestAckermann
local function Start5()
    local check=0
    local start=os.clock()
        for i=1,MAX_SIZE do  check=check+Ackermann(1+i%3,1+i%5); end
    local finish=os.clock()
    local res=(finish-start)*1000
    print("TestAckermann SIZE="..MAX_SIZE..",time=".. string.format("%.0f",res).." ms check="..check)
end


-- TestFloat
local f0=0.0
local f1=123.456789
local f2=98765.12345678998765432
local f3=12345678943.98

function TestFloat(MAX_SIZE)
   MAX_SIZE=MAX_SIZE-1
   for i=0, MAX_SIZE do
        for j=0, MAX_SIZE do
            f0=f0+(f1/(i+1))-f2+(f3*i);
        end
    end
end

function Start6()
   local t=os.clock()
   TestFloat(MAX_SIZE)
   local res=(os.clock()-t)*1000
 local  check=f0
   print("TestFloat SIZE="..MAX_SIZE..", time=" ..res.." ms  check="..tostring(check));
end


MAX_SIZE=35000; Start6()
MAX_SIZE=120000; Start5()
MAX_SIZE=32000; Start4()
MAX_SIZE=40; Start3()
MAX_SIZE=22000; Start2()
MAX_SIZE=16000000; Start1()