# A try on a is_prime function

8 messages
Open this post in threaded view
|

## A try on a is_prime function

 Hi! For a presentation of lua for mathematicians I tried to come up with a is_prime function. This is what I got: local function is_prime()   local primes = { [2] = true, [3] = true }   local max_prime = 3   local floor = math.floor   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     end     max_prime = table.maxn( t )   end   return function( n )     while n > max_prime do       add_primes()     end     return primes[ n ] == true   end end is_prime = is_prime() Now, if you like to tiker around with such things for recreational purposes (like me), please comment. The result should be * easy to understand * concise * performant Regards, Matthias
Open this post in threaded view
|

## Re: A try on a is_prime function

 * I'd declare "function add_primes()" as "local function add_primes()" * "for x, _ in" can be written as just "for x in" if you're not using the "_" variable * "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]" * "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" On Mon, Apr 27, 2009 at 5:10 PM, Matthias Kluwe <[hidden email]> wrote: > Hi! > > For a presentation of lua for mathematicians I tried to come up with a > is_prime function. > > This is what I got: > > local function is_prime() >  local primes = { [2] = true, [3] = true } >  local max_prime = 3 >  local floor = math.floor >  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 >    end >    max_prime = table.maxn( t ) >  end >  return function( n ) >    while n > max_prime do >      add_primes() >    end >    return primes[ n ] == true >  end > end > is_prime = is_prime() > > Now, if you like to tiker around with such things for recreational > purposes (like me), please comment. The result should be > > * easy to understand > * concise > * performant > > Regards, > Matthias >
Open this post in threaded view
|

## Re: A try on a is_prime function

 Hi! Thanks for the quick reaction. 2009/4/27 Peter Cawley <[hidden email]>: > * 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
Open this post in threaded view
|

## RE: A try on a is_prime function

 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.htmGMP is here: http://gmplib.org/-----Original Message----- From: [hidden email] 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 <[hidden email]>: > * 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 (5K) Download Attachment
Open this post in threaded view
|

## Re: A try on a is_prime function

 In reply to this post by Matthias Kluwe Since most mathematicians couldn't care less about programming languages you should be prepared for questions about primality tests. A good starting point is   http://en.wikipedia.org/wiki/Primality_testBye, Wim
Open this post in threaded view
|

## Re: A try on a is_prime function

 In reply to this post by Hines, Johnicholas Hi! Hines, Johnicholas schrieb: > 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. Using some existant C code could be more performant, of course. But this is about showing some »fine features«, not about showing the extensibility... Currently, this could be an example showing sparse tables (?!), local functions, upvalues (closures) and some memoize technique. Lua may be not the best utility for number theory, but this is just some kind of playground thing (like it would being asked on a PostScript list...). Regards, Matthias