Daniel Fischer
Am Dienstag 29 Dezember 2009 20:16:59 schrieb Daniel Fischer:
especially the claim that going by primes squares is "a pleasing but minor optimization",
Which it is not. It is a major optimisation. It reduces the algorithmic complexity *and* reduces the constant factors significantly.
D'oh! Thinko while computing sum (takeWhile (<= n) primes) without paper. It doesn't change the complexity, and the constant factors are reduced far less than I thought.
I do not understand. Turner's sieve is primes = sieve [2..] where sieve (p:xs) = p : sieve [x | x<-xs, x `mod` p /= 0] and the Postponed Filters is primes = 2: 3: sieve (tail primes) [5,7..] where sieve (p:ps) xs = h ++ sieve ps [x | x<-t, x `rem` p /= 0] where (h,~(_:t)) = span (< p*p) xs Are you saying they both exhibit same complexity? I was under impression that the first shows O(n^2) approx., and the second one O(n^1.5) (for n primes produced).