Re: [ANN] LuaJIT-2.0.0-beta4

[Mike Pall <mikelu-1004@...>]

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)))