[Haskell-cafe] A tale of Project Euler

[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. 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...)

> Another thing: you can stop sieving when p*p > size, another speedup
>   

Saves a few hundred milliseconds.

> Fifth thing: better use an STUArray, don't drag IO in if it's not necessary.
>   

I don't understand the ST monad.

>> 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.

> 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?)

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.