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).
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
