[Top] [All Lists]

 ```Will Ness yahoo.com> writes: > > Daniel Fischer web.de> writes: > > > Am Dienstag 05 Januar 2010 14:49:58 schrieb Will Ness: > > > > > > euler [email protected](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 [email protected](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 [email protected](Roll (x:_) by) p > = Roll (takeWhile (< (x+p*by)) \$ rollFrom r) (by*p) > > primes = euler \$ Roll [2] 1 > euler [email protected](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 [email protected](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. _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe ```