In an attempt to become less rusty, I was looking at some of the Euler challenge problems. #10 has me scratching my head. The problem statement is pretty simple: sum the primes < 2,000,000. A trivial (imperative, array-based) sieve in (your (other) language of choice) calculates this in no time flat.
The reason I _know_ that the imperative sieve runs so quickly is because I had plenty of time to write one whilst I was waiting for the Haskell one to run to conclusion; which, incidentally, it never did. Admittedly I used the "my first Haskell program" approach for sieving out primes, which runs candidate integers through an ever-increasing cascade of filters, one per prime:
> primes [] = [] > primes (n:ns) = n : primes [ n' | n' <- ns, n' `mod` n /= 0 ]
It's a neat expression of primality and showcases Haskell's lazy approach; but I'm hunting around for better (by which I mean, faster) ways to do this: ideally with derivations that are amenable to study. The Haskell wiki has some pointers (see? I _do_ google first) but if anyone with more Haskell chops fancies spending five minutes running through alternatives (especially in this case, where the upper bound is known well in advance, so a fixed array is a plausible approach) at the next meeting I'd be really appreciative.
Otherwise, if you want to see how not to do it ;) , you can see my very messy (probably non-idiomatic) version of an iterative sieve (without a wheel) near the top of https://github.com/status203/euler-clj/blob/master/src/euler/numbers.clj . I was exploring the idea of filtering/transforming down from an initial lazy sequence that contained every step of the sieve.
-- euler problem #10 e10 = sum (takeWhile (< 2000000) primes) where primes = 2 : [x | x <- [3..], prime x] prime y = testFactors y $ takeWhile (<= intSqrt y) primes testFactors z = all ((/=0).mod z) intSqrt = truncate.sqrt.fromIntegral
On Thursday, 9 August 2012 13:37:01 UTC+1, jang wrote:
> In an attempt to become less rusty, I was looking at some of the Euler > challenge problems. #10 has me scratching my head. The problem statement is > pretty simple: sum the primes < 2,000,000. A trivial (imperative, > array-based) sieve in (your (other) language of choice) calculates this in > no time flat.
> The reason I _know_ that the imperative sieve runs so quickly is because I > had plenty of time to write one whilst I was waiting for the Haskell one to > run to conclusion; which, incidentally, it never did. Admittedly I used the > "my first Haskell program" approach for sieving out primes, which runs > candidate integers through an ever-increasing cascade of filters, one per > prime:
> > primes [] = [] > > primes (n:ns) = n : primes [ n' | n' <- ns, n' `mod` n /= 0 ]
> It's a neat expression of primality and showcases Haskell's lazy approach; > but I'm hunting around for better (by which I mean, faster) ways to do > this: ideally with derivations that are amenable to study. The Haskell wiki > has some pointers (see? I _do_ google first) but if anyone with more > Haskell chops fancies spending five minutes running through alternatives > (especially in this case, where the upper bound is known well in advance, > so a fixed array is a plausible approach) at the next meeting I'd be really > appreciative.
I would suggest a filter with the Chinese primality test (which will
catch most of the composites) before doing the more expensive sieve. I
have no Haskell chops to speak of, so I won't do a demonstration of my
ignorance :|
The Chinese test is (2^n - 2) mod n == 0, then n is probably prime.
(2^2 - 2) mod 2 == 2 mod 2 == 0
(2^3 - 2) mod 3 == 6 mod 3 == 0
(2^4 - 2) mod 4 == 14 mod 4 == 2
(2^5 - 2) mod 5 == 30 mod 5 == 0
(2^6 - 2) mod 6 == 62 mod 6 == 2
.
.
.
I assume Haskell has a highly optimised exponentiation operator/function?
On Thu, Aug 23, 2012 at 9:58 AM, Arwyn <arwyn.robe...@gmail.com> wrote:
> Hi Jan,
> Here's my first attempt:
> -- euler problem #10
> e10 = sum (takeWhile (< 2000000) primes)
> where primes = 2 : [x | x <- [3..], prime x]
> prime y = testFactors y $ takeWhile (<= intSqrt y) primes
> testFactors z = all ((/=0).mod z)
> intSqrt = truncate.sqrt.fromIntegral
> Now I can go and read those papers...
> Cheers,
> Arwyn
> On Thursday, 9 August 2012 13:37:01 UTC+1, jang wrote:
>> In an attempt to become less rusty, I was looking at some of the Euler
>> challenge problems. #10 has me scratching my head. The problem statement is
>> pretty simple: sum the primes < 2,000,000. A trivial (imperative,
>> array-based) sieve in (your (other) language of choice) calculates this in
>> no time flat.
>> The reason I _know_ that the imperative sieve runs so quickly is because I
>> had plenty of time to write one whilst I was waiting for the Haskell one to
>> run to conclusion; which, incidentally, it never did. Admittedly I used the
>> "my first Haskell program" approach for sieving out primes, which runs
>> candidate integers through an ever-increasing cascade of filters, one per
>> prime:
>> > primes [] = []
>> > primes (n:ns) = n : primes [ n' | n' <- ns, n' `mod` n /= 0 ]
>> It's a neat expression of primality and showcases Haskell's lazy approach;
>> but I'm hunting around for better (by which I mean, faster) ways to do this:
>> ideally with derivations that are amenable to study. The Haskell wiki has
>> some pointers (see? I _do_ google first) but if anyone with more Haskell
>> chops fancies spending five minutes running through alternatives (especially
>> in this case, where the upper bound is known well in advance, so a fixed
>> array is a plausible approach) at the next meeting I'd be really
>> appreciative.
