The old Google Groups will be going away soon, but your browser is incompatible with the new version.
Pure functional (or monadic?) solution to Euler#10..?
 There are currently too many topics in this group that display first. To make this topic appear first, remove this option from another topic. There was an error processing your request. Please try again. Standard view   View as tree
 5 messages

From:
To:
Cc:
Followup To:
Subject:
 Validation: For verification purposes please type the characters you see in the picture below or the numbers you hear by clicking the accessibility icon.

More options Aug 9 2012, 8:37 am
From: jang <j...@ioctl.org>
Date: Thu, 9 Aug 2012 05:37:01 -0700 (PDT)
Local: Thurs, Aug 9 2012 8:37 am
Subject: Pure functional (or monadic?) solution to Euler#10..?

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.

Cheers,
jan

To post a message you must first join this group.
You do not have the permission required to post.
More options Aug 9 2012, 8:55 am
From: jang <j...@ioctl.org>
Date: Thu, 9 Aug 2012 05:55:32 -0700 (PDT)
Local: Thurs, Aug 9 2012 8:55 am
Subject: Re: Pure functional (or monadic?) solution to Euler#10..?

Yikes!

To answer my own question, the paper pointed at here:

me sufficiently by the nose to be useful.

I'd still be curious to see alternative approaches.

To post a message you must first join this group.
You do not have the permission required to post.
More options Aug 20 2012, 8:41 am
Date: Mon, 20 Aug 2012 05:41:48 -0700 (PDT)
Local: Mon, Aug 20 2012 8:41 am
Subject: Re: Pure functional (or monadic?) solution to Euler#10..?

You might also find http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf of
interest.

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.

To post a message you must first join this group.
You do not have the permission required to post.
More options Aug 23 2012, 4:58 am
From: Arwyn <arwyn.robe...@gmail.com>
Date: Thu, 23 Aug 2012 01:58:50 -0700 (PDT)
Local: Thurs, Aug 23 2012 4:58 am
Subject: Re: Pure functional (or monadic?) solution to Euler#10..?

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

To post a message you must first join this group.
You do not have the permission required to post.
More options Aug 23 2012, 3:26 pm
From: Shiyaz Rasheed <shi...@gmail.com>
Date: Thu, 23 Aug 2012 20:26:29 +0100
Local: Thurs, Aug 23 2012 3:26 pm
Subject: Re: Pure functional (or monadic?) solution to Euler#10..?
Hi Jan/Arwyn,

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?

Cheers,

Shiyaz