Will Ness
Daniel Fischer
writes: Am Dienstag 05 Januar 2010 14:49:58 schrieb Will Ness:
euler ks@(p:rs) = p : euler (rs `minus` map (*p) ks) primes = 2:euler [3,5..]
Re-write:
primes = euler $ rollFrom [2] 1 = 2:euler ( rollFrom [3] 1 `minus` map(2*) (rollFrom [2] 1)) ) rollFrom [3,4] 2 `minus` rollFrom [4] 2 -- rollFrom [3] 2 -- = 2:3:euler (rollFrom [5] 2 `minus` map(3*) (rollFrom [3] 2)) rollFrom [5,7,9] 6 `minus` rollFrom [9] 6 -- rollFrom [5,7] 6 -- = 2:3:5:euler (rollFrom [7,11] 6 `minus` rollFrom [25,35] 30) [7,11, 13,17, 19,23, 25,29, 31,35] 30 -- rollFrom [7,11,13,17,19,23,29,31] 30 -- = .....
correction: where rollOnce (x:xs) by = (x, xs ++ [x+by]) rollFrom xs by = concat $ iterate (map (+ by)) (xs) multRoll xs@(x:_) by p = takeWhile (< (x+p*by)) $ rollFrom xs by
so, reifying, we get
data Roll a = Roll [a] a
rollOnce (Roll (x:xs) by) = (x,Roll (xs ++ [x+by]) by) rollFrom (Roll xs by) = concat $ iterate (map (+ by)) (xs) multRoll r@(Roll (x:_) by) p = Roll (takeWhile (< (x+p*by)) $ rollFrom r) (by*p)
primes = euler $ Roll [2] 1 euler r@(Roll xs _) = x:euler (Roll (mxs `minus` map (x*) xs) mby) where (x,r') = rollOnce r (Roll mxs mby) = multRoll r' x
There's much extra primes pre-calculated inside the Roll, of course. For any (Roll xs@(x:_) _), (takeWhile (< x*x) xs) are all primes too. When these are used, the code's complexity is around O(n^1.5), and it runs about 1.8x slower than Postponed Filters. The "faithful sieve"'s empirical complexity is above 2.10..2.25 and rising. So it might not be exponential, bbut is worse than power it seems anyway.