Am Montag, 28. Juli 2008 18:15 schrieb Niels Aan de Brugh:
Steve Klabnik wrote:
I think you're onto something with the Int/Integer thing....when using a type signature of "Integer", "f 1 113383" gives "248" immediately. Compiling and running the code with "Integer" types on my home machine yields "525".... which Euler says isn't the right answer?
Because you're not providing the right number. :-)
Also, on the strictness annotations: Do you put them in the type declaration? Or in the pattern match on the lhs of the declaration?
I've tested your code with strictness annotations and it appears to not make a difference. GHC employs several optimization techniques, one of those being strictness analysis, so maybe it is already using a strict, unboxed integer.
Using -O2, GHC produces the same core with or without strictness annotations, the 'acc' parameter of f is an unboxed Int, so the optimiser indeed sees it is needed. The Integer parameter unfortunately can't be unboxed. A native 64-bit integer type might gain something.
The real speed-up (a non-linear one) here is not to re-calculate every sequence over and over again, but keep it in a map/array (as suggested by Rafael and me).
Using a Map, though easier to code, doesn't buy you much here, indeed less than a few easy considerations where the maximal length cannot occur. The problem is that you have to update the Map often, which is rather costly, also the Map takes a lot of memory. Using an array is more convoluted, but much faster (if done right).
I've found some Euler puzzles are impossible to solve without this technique.
At least, it would take far longer to get the solution.
Niels
P.S.: If you're really going for speed, compile (not interpret) the code (using -O -fvia-C, and there's some more stuff in the manual) using the latest greatest version of GHC.
Nowadays, the native code generator is not necessarily slower than -fvia-C, often faster. So the best should be to test both, -O2 and -O2 -fvia-C -optc-On, for some medium sized inputs and see which actually is faster. Cheers, Daniel