[Haskell-cafe] Re: FASTER primes

Daniel Fischer daniel.is.fischer at web.de
Wed Dec 30 05:42:53 EST 2009


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. The huge performance differences I had must have been due to cache misses (unless 
you use a segmented sieve, starting at the square reduces the number of cache misses 
significantly).
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20091230/4086c291/attachment.html


More information about the Haskell-Cafe mailing list