[email protected]
[Top] [All Lists]

Re: [Haskell-cafe] Re: FASTER primes

Subject: Re: [Haskell-cafe] Re: FASTER primes
From: Daniel Fischer
Date: Wed, 30 Dec 2009 11:42:53 +0100

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
[email protected]
<Prev in Thread] Current Thread [Next in Thread>