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:

: 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).