[Haskell-cafe] A tale of Project Euler

[Henning Thielemann]

On Fri, 30 Nov 2007, Daniel Fischer wrote:

> Am Freitag, 30. November 2007 14:39 schrieb Henning Thielemann:
>
> > Is this thread still about the prime sieve? As I mentioned, I think one
> > can avoid the mutable array, because if there is only a small number of
> > array updates with much changes per update, it should be efficient enough
> > to copy the array per update.
>
> I think in this case it's far less efficient than in-place update. Consider
> sieving primes up to 10^7, there are 446 primes with p^2 < 10^7, so you would
> have over 400 array updates. Even if you leave out the even numbers, an array
> going up to 10^7 would require some 800 KB memory (each odd number one bit),
> so overall, you'd allocate well over 300 MB (not at once, of course).

"not at once" - that's the point. With some luck there are only two pieces
of memory where the data is copied back and forth. It's obviously not the
most efficient solution, but a non-monadic solution.