[Haskell-cafe] Re: FASTER primes

[Will Ness]

Will Ness <will_n48 <at> yahoo.com> writes:

> 
> Daniel Fischer <daniel.is.fischer <at> web.de> 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.