[email protected]
[Top] [All Lists]

[Haskell-cafe] Re: FASTER primes

Subject: [Haskell-cafe] Re: FASTER primes
From: Will Ness
Date: Wed, 6 Jan 2010 14:24:51 +0000 UTC
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 [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

<Prev in Thread] Current Thread [Next in Thread>