Anonymous user
User talk:Retroburrowers: Difference between revisions
→reply2: reply3
GordonBGood (talk | contribs) (reply to reply) |
(→reply2: reply3) |
||
| (7 intermediate revisions by 2 users not shown) | |||
Line 108:
In your recent contribution to the Sieve of Eratosthenes Task for QLSuperBasic/Sundaram Sieve:
http://rosettacode.org/wiki/Sieve_of_Eratosthenes#Sieve_of_Sundaram, with respect, your statement - "Thus, Sundaram's is what Eratosthenes' Sieve becomes upon applying all optimisations incorporated into the other entries for QL SuperBASIC." is incorrect. Sundaram uses **all odd numbers** as the basis for culling composite numbers whereas the SoE optimized to odds-only uses only **odd primes** for this purpose; this changes the computational complexity to O(n^(
: Sorry, forgot to sign - [[User:GordonBGood|GordonBGood]] ([[User talk:GordonBGood|talk]]) 20:30, 22 May 2021 (UTC)
Line 122:
well as the title to an optimised sieve of Sundaram, rather than by removing line 50 & not generating 2.
: RE "So we're more inclined to change the reference in the statement as well as the title to an optimised sieve of Sundaram, rather than by..." - but the title of the whole Task page is The Sieve of Eratosthenes not Sundaram so why clutter it up and make it confusing by bringing up the subject of other less efficient sieves? I would recommend just removing any and all sieves that are not SoE's. Regards [[User:GordonBGood|GordonBGood]] ([[User talk:GordonBGood|talk]]) 06:22, 24 May 2021 (UTC)
====reply2====
b/c most optimisations employed in other languages go beyond the
given task's specification. Many of them are similar to the Sieve of
Sundaram in their 2:1 compression. Others are similar to the modestly
optimised version. Thus, the task should be reclarified to allow such
'extras'. In this specific case, it's more of an academic exercise to
show how one optimised Sieve is a modest transformation away from
another. Thusly optimised, they should be identical in terms of speed.
: You seem to be under the impression that the Sieve of Sundaram (SoS) is an "optimisation"; '''It is not'''. The only optimization that it enjoys is that it is just slightly easier to implement that the SoE and that, like the odds-only SoE, it reduces the sieving memory requirement to half. You are correct that the SoE can be just a modest transformation away from the properly implemented SoS. Perhaps it will take an example to convince you; Following is a properly implemented version of the Python code from [https://en.wikipedia.org/wiki/Sieve_of_Sundaram#Correctness the Wikipedia article on SoS]; I say improved because it removes the redundancies of over-looping past constraints that never do any culling operations, it properly manages zero based array indices, and the determination of `j` is based on what it actually does and is formulated so that no multiplications are required inside the culling loop:
<lang python>import math
def sieve_of_Sundaram(n):
"""The sieve of Sundaram is a simple deterministic algorithm for finding all the prime numbers up to a specified integer."""
if n < 3:
if n < 2: return 0
else: return 1
k = (n - 3) // 2 + 1; integers_list = [True] * k; ops = 0
for i in range(0, (int(math.sqrt(n)) - 3) // 2 + 1):
# if integers_list[i]: # adding this condition turns it into a SoE!
p = 2 * i + 3; s = (p * p - 3) // 2 # compute cull start
for j in range(s, k, p): integers_list[j] = False; ops += 1
print("Total operations: ", ops, ";", sep='')
count = 1
for i in range(0, k):
if integers_list[i]: count += 1
print("Found ", count, " primes to ", n, ".", sep='')
"""
if n > 2:
print(2, end=' ')
for i in range(0, k):
if integers_list[i]:
print(2 * i + 3, end=' ')
"""
sieve_of_Sundaram(1000000)</lang>
{{out}}
<pre>Total operations: 1419797;
Found 78498 primes to 1000000.</pre>
: Now, uncommenting the prime test condition as noted turns this into a SoE, but changes the output as to the total number of operations:
{{out}}
<pre>Total operations: 811068;
Found 78498 primes to 1000000.</pre>
: This difference in the amount of operations as in the amount of work done gets even larger as the range goes up; if you want to play with it, the code is posted on [https://wandbox.org/permlink/I5PmD0YsAW0ndm6q an on-line IDE here]. The reason for this difference is that the SoE has about O(n log log n) asymptotic complexity which increases quite slowly with range, where as the SoS has about O(n log n) complexity, which increases more quickly with range. This can be seen from the above implementation as ''i'' ranges up to (half of) the square root of the range, where the ''j'' variable ranges from a little above ''i'' to something approaching (half of) the range, so the product is O(n^(3/2)) but the span of the culling increases with increased base number so as to reduce the term to about ''log n'', with the extra constant factor of about a quarter meaningless for showing complexity with increasing range (Big-O).
: That is the reason that the SoS should not be on the SoE Task Page: it doesn't have the same asymptotic complexity, it isn't that much simpler, and it is confusing for those that can't tell the difference.
: Regards, [[User:GordonBGood|GordonBGood]] ([[User talk:GordonBGood|talk]]) 06:16, 25 May 2021 (UTC)
:: I had another look at your "Sieve of Sundaram" code and it's not wrong other than for the title: as it does have the condition that the base value must have already been determined to be prime, it is not the SoS but rather a full implementation of the Odds-Only Sieve of Eratosthenes. Therefore, my recommendation is just that you change the title and comments. Regards [[User:GordonBGood|GordonBGood]] ([[User talk:GordonBGood|talk]]) 02:04, 26 May 2021 (UTC)
====reply3====
We were dissuaded from keeping line 50 by your subsequent argument, even w/o the example in Python, but still appreciate its inclusion. We accordingly changed the comments to stress that a minimally changed SoS is being emulated, and so allow keeping the title.
| |||