Talk:Sieve of Eratosthenes: Difference between revisions
→Trial division sieves should be moved from here: new section
m (Updated to note resolution) |
(→Trial division sieves should be moved from here: new section) |
||
Line 144:
-----
== Trial division sieves should be moved from here ==
As the title says. The context for this is the discussion at [[User talk:Elibarzilay|Eli Barzilay's talk page]].
Here's my response to that discussion.
It is most definitely a sieve, just not the sieve of Eratosthenes as it is understood today, and at least as early as 1772 -- time of publication of the article by Horsley, referenced in the Wikipedia article, in which he much trashes Nicomachus (yes, trashes, it is beyond criticism), incidentally, for being unable to convey clearly the essence of Eratosthenes's method. Horsley in fact says that the impression as if it was about testing divisibility of each number in separation, is ''"preposterous"'' and that a brilliant mind such as Eratosthenes's couldn't possibly have chosen such lowly route when in fact the bright gem, a treasure of a true formulation was possible - IIRC. I'm paraphrasing.
It indeed is a ''trial division'' sieve - a sieve where the removal is done by trying out the divisions by primes, one prime after another, as opposed to the "true" sieve of Eratosthenes finding out the composites as primes' multiples, and getting the primes for free, in the gaps between the multiples, as "what's left" after all the numbers are let ''"through the sieve"''.
I.e. the sieve is ''constructed'' from primes, by ''counting'' (i.e. by repeated additions); no number needs be attempted to be divided by any other number. And that's the difference between the two.
The defining characteristic of an algorithm is its theoretical time complexity. The sieve of Eratosthenes' complexity is N log (log N) ~ n log n log (log n), for n primes below N; the (''optimal'') trial division sieve's - N^1.5/(log N)^2 ~ n^1.5/(log n)^0.5, as derived in M. O'Neill's paper. Granted, that paper is short on clear-cut explanations, but it has the needed math derivations nonetheless.
The real question we're left with here, is whether to open up a new page for "trial division sieves", or to add - both Scala and Scheme, and any other entry's there might be - to the [[Primality by trial division]] page. Which I did, incidentally, for the Haskell entry, long time ago, where we can find this unoptimized simple famous code both in its original, and optimized formulation.
'''''I propose all such entries are, indeed, moved to [[Primality by trial division]]''''', for now; and if the special page gets created for them later, they can be further moved there. Right now, having trial division sieves under the heading of "sieve of Eratosthenes", on the page which explicitly forbids anything other than the proper algorithm, seems to be a no-go proposition. -- [[User:WillNess|WillNess]] ([[User talk:WillNess|talk]]) 19:59, 10 September 2014 (UTC)
| |||