[Date Prev][Date Next][Thread Prev][Thread Next]
[Date Index]
[Thread Index]
- Subject: RE: Adding an hex type in lua
- From: "Grellier, Thierry" <t-grellier@...>
- Date: Thu, 23 Nov 2006 18:42:46 +0100
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