Personal tools

Talk:Prime numbers

From HaskellWiki

Revision as of 14:47, 25 December 2009 by WillNess (Talk | contribs)

Jump to: navigation, search
Here's an interesting question: will the program go faster if we replace all those
(n >)
expressions with
(\x -> floor (sqrt n) > x)

On one hand, a composite integer cannot possess a factor greater than its square root.

On the other hand, since the list we're looking through contains all possible prime numbers, we are guaranteed to find a factor or an exact match eventually, so do we need the
at all?

Throwing this over to somebody with a bigger brain than me...

MathematicalOrchid 16:41, 5 February 2007 (UTC)

a composite can indeed have factors greater than its square root, and indeed most do. what you mean is that a composite will definitely have at least one factor smaller-equal than its square root.

why not use
(\x -> n > x*x)
--Johannes Ahlmann 21:18, 5 February 2007 (UTC)

LOL! That is indeed what I meant.

It turns out my comment above is correct - the
filtering in
is in fact unecessary. The function works just fine without it. (Notice I have made some edits to correct the multiple bugs in the
function. Oops!) Now the only use of
is in the
function, which could be changed to 'give up' the search a lot faster and hence confirm large primes with much less CPU time and RAM usage. Maybe I'll wrap my brain around that later.

MathematicalOrchid 10:17, 6 February 2007 (UTC)

The section Simple Prime Sieve II is not a sieve in the same sense that the first one is. It really implements a primality test as a filter.

A more "sieve-like" version of the simple sieve which exploits the fact that we need not check for primes larger than the square root would be

  primes :: [Integer]
  primes = sieve [2..]
    where sieve (p:xs) = p : sieve [x | x<-xs, (x< p*p) || (x `mod` p /= 0)]

However, this runs even slower than the original!

Kapil Hari Paranjape 06:51, 4 February 2009 (UTC)

I want to thank Leon P. Smith for showing me the idea of producing the spans of odds directly, for version IV. I had a combination of span and infinite odds list, as in span (< p*p) [3,5..] etc. That sped it up some 20% more, when GHC-compiled.

The mark-and-comb version that I put under Simple Sieve of Eratosthenes seems to me very "faithful" to the original (IYKWIM). Strangely it shows exactly same asymptotic behavior when GHC-compiled (tested inside GHCi) as IV. Does this prove that priority queue-based code is better than the original? :)

BTW "unzip" is somehow screwed up inside "haskell" block, I don't know how to fix that.

I've also added the postponed-filters version to the first sieve code to show that the squares optimization does matter and gives huge efficiency advantage just by itself. The odds only trick gives it a dozen or two percent improvement, but it's nothing compared to this 20x massive speedup!

Written in list-comprehension style, it's

  primes :: [Integer]
  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

Which BTW is faster than the IV version itself, when interpreted in GHCi. So what are we comparing here, code versions or Haskell implementations??

WillNess 10:46, 15 November 2009 (UTC)

I've added the code for Euler's sieve which is just the postponed filters with minimal modification, substituting (t `minus` multiples p) for (filter (nodivs p) t).

Now it is obvious that (...(((s - a) - b) - c) - ...) is the same as (s - (a + b + c + ...)) and this is the next code, the "merged multiples" variation of Euler's sieve.

It is very much like the streamlined and further optimized famous Richard Bird's code (appearing also in Melissa O'Neill's JFP article), which copyright status is unknown to me, so I couldn't reference it in the main article body. The code as written in the article has the wrong clause order in merge, and uses minus instead of more efficient gaps.

I've also changed the span pattern-binding to the more correct lazy pattern, (h,~(_:t)).

WillNess 17:10, 5 December 2009 (UTC)

New treefolding merge is inspired by apfelmus's VIP code from Implicit Heap; but it uses a different structure, better at primes multiples generation: instead of his 1+(2+(4+(8+...))) it's (2+4)+( (4+8) + ( (8+16) + ...)).

I estimated the total cost of producing primes multiples as Sum (1/p)*d, where d is the leaf's depth, i.e. the amount of merge nodes its produced prime must pass on its way up to the top. The values for cost function correspond very well with the actual time performance of the respective algorithms: it's better by 10%-12% and the performance boost is 10%-12% too.

I will also add this code further improved with the Wheel optimization here. That one beats the PQ-based code from Melissa ONeill's ZIP file by a constant margin of around 20%, its asympotic behaviour *exactly* the same.

I measure local asymptotics by taking a logBase of run time ratio in base of a problem size ratio. I've settled testing code performance as interpreted, inside GHCi. Running a compiled code feels more lke testing a compiler itself. Too many times I saw two operationally equivalent expressions running in wildly different times. It can't be anything else other tha the compiler's quirks, and we're not interested in those, here. :)

Apparently, arrays are very fast. :) WillNess 14:47, 25 December 2009 (UTC)