User talk:Retroburrowers: Difference between revisions
m
→reply2: typos...
GordonBGood (talk | contribs) (→reply2: response...) |
GordonBGood (talk | contribs) m (→reply2: typos...) |
||
Line 133:
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
<lang python>import math
Line 173:
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''
: 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.
|