User talk:Retroburrowers: Difference between revisions

: You seem to be under the impression that the Sieve of Sundaram (SoS) is an "optimisation"; '''It is not'''. The only optimization that is 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(k)) + 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/IXqqq4DKriRNJApb an on-line IDE here]. The reason this is true is that the SoE has about O(n log log n) asymptotic complexity which increases quite slowly with range, where as the SoS has o(n^(3/2)) complexity, which increases quite quickly with range. This can be seen from the above implementation as ''i''` ranges up the the square root of (half of) the range, where the ''j'' variable ranges from a little above ''i'' for something approaching (half of) the range, so the product is O(n^(3/2)), with the constant extra 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)