User talk:Retroburrowers: Difference between revisions

Line 110:

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^(1/2)) from O(n log log n), a considerable difference. While one can use some recursion to cull by previously sieved primes, that result becomes a full SoE and can no longer be called the Sieve of Sundaram, as "all odd numbers" is it's exact characteristic. One can recompose your Sundaram code to make this more obvious.

: Sorry, forgot to sign - [[User:GordonBGood|GordonBGood]] ([[User talk:GordonBGood|talk]]) 20:30, 22 May 2021 (UTC)

====reply====

Recomposing to get back to Sundaram's original sieve would be to reverse the "modest transformation" from it into the optimised SoE

Therefore, the quoted statement is meant in the sense that transforming Sundaram's Sieve will produce the same effect as the

original when reducing his 2D array down to 1D, as well as skipping odd non-primes via line 50. Thus, we increased the degree of

the transformation from "slight" to "modest." Likewise in the last FOR loop where it becomes necessary to include zero as a member

of the compressed elements in order to be equivalent to the SoE, since Sundaram's matrix excludes 0 - but only explicitly, since

one can include it on the ground that "the empty set is a subset of any set of items" such that 0 is thereby an implicit way of

generating 2 as the 1st prime by uncompressing via 0^I+1+I*2. 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 removing line 50 & not generating 2.