[Haskell-cafe] A tale of Project Euler

[Daniel Fischer]

Am Donnerstag, 29. November 2007 19:43 schrieb Andrew Coppin:
> Daniel Fischer wrote:
> > One thing: since You check the array bounds, the system needn't check
> > them again, use unsafeWrite and unsafeRead. And use Int for the index,
> > that would be MUCH faster.
>
> I can't find the functions you're talking about.

As Sebastian already said, they're in Data.Array.Base, sorry, should've 
mentioned that.

> I have however changed
> the index type. (Make little or no noticable speed difference. But then,
> it's already pretty damn fast in the first place...)
>

But it can be considerably faster. On my 5 yo 1200MHz thing, I can sieve up to 
10 million in less than half a second:
dafis at linux:~/Documents/haskell/move> time ./Sieve2 10000000
664579

real    0m0.419s
user    0m0.420s
sys     0m0.000s

And that's even faster than any sieve in C that I managed to write.
(Okay, I don't know how to use bitsets in C, that might beat Haskell)
> > Another thing: you can stop sieving when p*p > size, another speedup
>
> Saves a few hundred milliseconds.

Which is pretty much for a programme running below 1 second.
>
> > Fifth thing: better use an STUArray, don't drag IO in if it's not
> > necessary.
>
> I don't understand the ST monad.

Nor do I. Just use it (and be prepared to use scoped type variables).
>
> >> The obvious downside of course is that you must know how big
> >> to make the array at the start of your program, and you must compute the
> >> entire array before you can use any of it. Both limitations not precent
> >> in the lazy recursive list implementation...
> >
> > The size of the array can easily be estimated by the prime number
> > theorem,
>
> Probably. But it doesn't compare to the elegance and simplicity of being
> able to generate an arbitrary number of primes on an as-needed basis.

True. But when speed matters, you have to bite the bullet.
And if you don't know up to which bound you need the primes, but know it's a 
not too low bound, you can sieve the first part in an array and then go on 
using a list, that's what I do.
>
> > Keep enjoying Project Euler,
> > Daniel
>
> Well, I don't know about "enjoy" - generally I just find it quite
> frustrating. It's kind of addictive trying to increase your score
> though... (Anybody here reached 100% yet?)

int-e (Bertram Felgenhauer, I believe), well he has not yet solved last 
week's, so currently he's at 99%, and there were a couple of others but they 
didn't persevere.
>
> I find that a lot of the problems don't seem to involve much math.
> (E.g., "here is some data, process it into a list of integers, find the
> highest one". Where is the deep mathematics in that?) A few of them do,
> but a lot are simply to do with prime numbers, and as far as I'm away,
> it is impossible to know anything about prime numbers. In other words,
> you must compute them all the hard way.
>
Some of the problems require little math, but more programming techniques. 
Others require a good grip of maths to find an efficient algorithm. Really 
deep maths can't be required, the site is not meant for professional 
mathematicians but for laypeople with mathematical interest.
The aim is to make brute force unattractive (brute forcing times from 5 hours 
upwards), while a mathematical insight will often give the solution in a few 
nanoseconds.
Many problems require both, some maths to find a good algorithm, and some 
programming techniques to make it run really fast.

Cheers,
Daniel