A try on a is_prime function

classic Classic list List threaded Threaded
8 messages Options
Reply | Threaded
Open this post in threaded view
|

A try on a is_prime function

Matthias Kluwe
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
Reply | Threaded
Open this post in threaded view
|

Re: A try on a is_prime function

Peter Cawley
* 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
>
Reply | Threaded
Open this post in threaded view
|

Re: A try on a is_prime function

Matthias Kluwe
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
Reply | Threaded
Open this post in threaded view
|

RE: A try on a is_prime function

Hines, Johnicholas

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: [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
Reply | Threaded
Open this post in threaded view
|

Re: A try on a is_prime function

Wim Couwenberg
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_test

Bye,
Wim
Reply | Threaded
Open this post in threaded view
|

Re: A try on a is_prime function

Matthias Kluwe
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
Reply | Threaded
Open this post in threaded view
|

Re: A try on a is_prime function

Matthias Kluwe
In reply to this post by Wim Couwenberg
Hi!

2009/4/27 Wim Couwenberg <[hidden email]>:
> 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_test

Thanks for the advice, but being an mathematician myself an knowing my
audience, this should be no problem (I could leave further
consideration as an exercise :-) ). But I have to admit that my number
theory background is almost zero.

Luckily, my small function is not obliged to solve any real world
problems considering prime numers.

Regards,
Matthias
Reply | Threaded
Open this post in threaded view
|

Re: A try on a is_prime function

Niels Aan de Brugh
In reply to this post by Matthias Kluwe
Matthias Kluwe <mkluwe <at> gmail.com> writes:
>
> 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...).

Your example clearly shows some of the nice language features, but wouldn't
it make more sense to pick an application where Lua actually beats the
competition? This implementation is probably slower than something I can
whip up in an elegant (compiled) functional language that would also impress
an adience of mathematicians.

In Lua you can easily leverage the processing power of C (e.g. GMP) and beat
the pants off many other high-level languages while being dynamic. You could
not even mention that specifically and simply use LGMP and show some
benchmarks.

Just my two cents.

Niels