[Date Prev][Date Next][Thread Prev][Thread Next]
[Date Index]
[Thread Index]
- Subject: https://www.lua.org/cgi-bin/demo?sieve: Eratosthenes' sieve?
- From: Thorkil Naur <naur@...>
- Date: Sun, 9 May 2021 23:05:49 +0200
Dear List,
The demonstration program https://www.lua.org/cgi-bin/demo?sieve is:
-- sieve.lua
-- the sieve of Eratosthenes programmed with coroutines
-- typical usage: lua -e N=500 sieve.lua | column
-- generate all the numbers from 2 to n
function gen (n)
return coroutine.wrap(function ()
for i=2,n do coroutine.yield(i) end
end)
end
-- filter the numbers generated by `g', removing multiples of `p'
function filter (p, g)
return coroutine.wrap(function ()
for n in g do
if n%p ~= 0 then coroutine.yield(n) end
end
end)
end
N=N or 500 -- from command line
x = gen(N) -- generate primes up to N
while 1 do
local n = x() -- pick a number until done
if n == nil then break end
print(n) -- must be a prime number
x = filter(n, x) -- now remove its multiples
end
This is a wonderful program in many ways and I fully agree with its use
as a demonstration. However, the method used is simple trial division,
not the sieve of Eratosthenes. So I suggest that the comment is adjusted
acordingly, for example to say "prime filtering by trial division
programmed with coroutines" or similarly.
To support this view, instrument sieve.lua slightly:
$ diff -u sieve.lua sieve2.lua
--- sieve.lua 2021-04-14 19:59:22.000000000 +0200
+++ sieve2.lua 2021-05-09 19:58:26.000000000 +0200
@@ -16,6 +16,7 @@
function filter (p, g)
return coroutine.wrap(function ()
for n in g do
+ print( n .. "%" .. p .. " = " .. n%p )
if n%p ~= 0 then coroutine.yield(n) end
end
end)
$
Running the instrumented version shows what happens:
$ lua-5.4.3 -e'N=15' sieve2.lua
2
3%2 = 1
3
4%2 = 0
5%2 = 1
5%3 = 2
5
6%2 = 0
7%2 = 1
7%3 = 1
7%5 = 2
7
8%2 = 0
9%2 = 1
9%3 = 0
10%2 = 0
11%2 = 1
11%3 = 2
11%5 = 1
11%7 = 4
11
12%2 = 0
13%2 = 1
13%3 = 1
13%5 = 3
13%7 = 6
13%11 = 2
13
14%2 = 0
15%2 = 1
15%3 = 0
$
So: Each candidate is divided by the primes less than the candidate. And
if all remainders are non-zero, the number is printed as prime.
This is in contrast to the sieve of Eratosthenes
(https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes): Initially, the
desired candidates are listed:
2 3 4 5 6 7 8 9 10 11 12 13 14 15
Then numbers divisible by the first number in the list, 2, except 2
itself, are marked as composite (enclosed in ()s):
2 3 (4) 5 (6) 7 (8) 9 (10) 11 (12) 13 (14) 15
Then numbers divisible by 3, the next unmarked number, are marked:
2 3 (4) 5 (6) 7 (8) (9) (10) 11 ((12)) 13 (14) (15)
(Marking starts at 3*3 = 9, because 6 = 2*3 has already been marked
as divisible by 2.)
And then we are done, since the next number to be marked, 5*5 = 25, is
beyond the list. The primes less than 15 are the unmarked numbers left:
2 3 5 7 11 13
Clearly, this process is quite different from what happens in sieve.lua.
The view that the sieve.lua program is not really an implementation of
Eratosthenes' sieve is inspired by a similar view, expressed by Melissa
E. O’Neill in "The Genuine Sieve of Eratosthenes"
(https://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf), concerning the
following "much beloved and widely used example" Haskell program for
generating primes:
primes = sieve [2..]
sieve (p : xs) = p : sieve [x | x <− xs, x ‘mod‘ p > 0]
I will spare the reader a discussion of this Haskell program, except for
noting that the code is actually prominently displayed on the
haskell.org web site (2021-May-09), with "sieve" renamed to
"filterPrime". Reading O'Neill's paper may provide further support to
the view that sieve.lua is not an implementation of Eratosthenes' sieve.
Best regards
Thorkil Naur