Daniel Fischer <daniel.is.fischer <at> web.de> writes:
>
>
> 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).
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
