RE: Adding an hex type in lua

["Grellier, Thierry" <t-grellier@...>]

Well actually original code avoids performing division or modulo because they are costly operation (note a*0.5 instead of a/2), and limits multiplication (adding twice is cheaper than multiplying by 2). 

I was just showing that naïve translation with bitwise enable lua was more efficient than more carefully designed one with lua without bitwise.

So if I compare the original code with a modified version of it benefiting from the bitwise operators I got:

% time src/lua test/nsieve-bits-original-nohex.lua 9
Primes up to  5120000   356244
Primes up to  2560000   187134
Primes up to  1280000    98610
23.360u 0.010s 0:23.62 98.9%    0+0k 0+0io 225pf+0w

% time src/lua nsieve-bits-opt-original-withhex.lua 9
Primes up to  5120000   356244
Primes up to  2560000   187134
Primes up to  1280000    98610
13.350u 0.010s 0:13.83 96.6%    0+0k 0+0io 225pf+0w

And well as a reference, the version published in previous mail
% time src/lua test/nsieve-bits-naive.lua 9
Primes up to  5120000   356244
Primes up to  2560000   187134
Primes up to  1280000    98610
16.370u 0.020s 0:16.58 98.8%    0+0k 0+0io 221pf+0w

With 
% cat nsieve-bits-opt-original-withhex.lua
-- The Great Computer Language Shootout
-- http://shootout.alioth.debian.org/
-- contributed by Mike Pall
local floor, ceil = math.floor, math.ceil

local precision = 64
local onebits = 0xFFFFFFFFFFFFFFFF

local function nsieve(p, m)
  local cm = (m+precision) \ precision
  do local onebits = onebits; for i=0,cm do p[i] = onebits end end
  local count, idx, bit = 0, 2, 0x1
  for i=2,m do
    if p[idx] & bit == bit then -- Bit set?
      local kidx, kbit = idx, bit
      for k=i+i,m,i do
        kidx = kidx + i
        while kidx >= cm do kidx = kidx - cm; kbit = kbit + kbit end
        local x = p[kidx]
        if x & kbit == kbit then p[kidx] = x ^^ kbit end -- Clear bit.
      end
      count = count + 1
    end
    idx = idx + 1
    if idx >= cm then idx = 0; bit = bit + bit end
  end
  return count
end

local N = tonumber(arg and arg[1]) or 1
if N < 2 then N = 2 end
local primes = {}

for i=0,2 do
  local m = (2^(N-i))*10000
  io.write(string.format("Primes up to %8d %8d\n", m, nsieve(primes, m)))
end

-----Original Message-----
From: lua-bounces@bazar2.conectiva.com.br [mailto:lua-bounces@bazar2.conectiva.com.br] On Behalf Of Roberto Ierusalimschy
Sent: Thursday, November 23, 2006 4:37 PM
To: Lua list
Subject: Re: Adding an hex type in lua

> Well part of speed improvement comes from less function calls notably
> thanks to the integer division.

Can't the original code benefit from the new '%' operator?

-- Roberto