[Date Prev][Date Next][Thread Prev][Thread Next]
[Date Index]
[Thread Index]
**Subject**: **Re: [ANN] LuaJIT-2.0.0-beta4**
**From**: Mike Pall <mikelu-1004@...>
**Date**: Tue, 6 Apr 2010 03:24:07 +0200

Linus Sjögren wrote:
> Nice! I noticed a speed improvement in my prime finder:
>
> beta2:
> >189.43 seconds spent - 15485863 is the 1000000th prime.
> beta4:
> >143.27 seconds spent - 15485863 is the 1000000th prime.
Ah, interesting. But whatever algorithm you use is a tad slow.
Even the naive Sieve of Eratosthenes finds all primes in less
than a second (and there are other, much better algorithms).
See the attached program for a variant using bit operations. It
counts the primes up to a maximum, not the other way round. Run it
with 15485863 as the argument to get a comparable timing.
--Mike

-- This is the (naive) Sieve of Eratosthenes. Public domain.
local bit = require("bit")
local band, bxor, rshift, rol = bit.band, bit.bxor, bit.rshift, bit.rol
local function nsieve(m)
local p, count = {}, 0
for i=0,rshift(m, 5) do p[i] = -1 end
for i=2,m do
if band(rshift(p[rshift(i, 5)], i), 1) ~= 0 then
count = count + 1
for j=i+i,m,i do
local jx = rshift(j, 5)
p[jx] = band(p[jx], rol(-2, j))
end
end
end
return count
end
local N = tonumber(arg and arg[1]) or 1000
io.write(string.format("Primes up to %d: %d\n", N, nsieve(N)))