RE: A try on a is_prime function

["Hines, Johnicholas" <Johnicholas-Hines@...>]

I think this misrepresents lua. Lua has many fine features (tables, dynamic typing, local functions, and so on). However, the crucial selling point is embedding and extending. Something like LGMP's probab_prime (implemented by wrapping the GNU Multiple Precision library) would be more essentially lua-ish, and more performant as well. 

Johnicholas

LGMP is here:

http://members.chello.nl/~w.couwenberg/lgmp.htm

GMP is here:

http://gmplib.org/

-----Original Message-----
From: lua-bounces@bazar2.conectiva.com.br on behalf of Matthias Kluwe
Sent: Mon 4/27/2009 12:53 PM
To: Lua list
Subject: Re: A try on a is_prime function
 
Hi!

Thanks for the quick reaction.

2009/4/27 Peter Cawley <lua@corsix.org>:
> * I'd declare "function add_primes()" as "local function add_primes()"

Yes, that has been a typo.

> * "for x, _ in" can be written as just "for x in" if you're not using
> the "_" variable

Of course. You can see my low lua experience here...

> * "local primes = { [2] = true, [3] = true }" is less clear, but a
> tiny bit more memory efficient as "local primes = {nil, true, true}"
> * "floor( max_prime / x ) * x" is probably more efficient as
> "max_prime - (max_prime % x)"
> * "return primes[ n ] == true" may be more efficient as "return not
> not primes[n]"

I hope so.

> * "max_prime = table.maxn( t )" might be more efficient if rolled into
> the preceeding for loop; "if x > max_prime then max_prime = x end"

Ok, as table.maxn iterates over the table itself, that should be a good idea.

Including your suggestions, here's the revised version:

local function is_prime()
  local primes = { [2] = true, [3] = true }
  local max_prime = 3
  local floor = math.floor
  local function add_primes()
    local t = {} -- list of candidates
    local N = max_prime * 2 + 1
    for i = max_prime + 2, N, 2 do
      t[ i ] = true
    end
    -- sieve candidates
    for x  in pairs( primes ) do
      for i = floor( max_prime / x ) * x, N, x do
        t[ i ] = nil
      end
    end
    -- append primes
    for x  in pairs( t ) do
      primes[ x ] = true
      if x > max_prime then max_prime = x end
    end
  end
  return function( n )
    while n > max_prime do
      add_primes()
    end
    return primes[ n ] == true
  end
end
is_prime = is_prime()

Regards,
Matthias

<<winmail.dat>>