G'day all.
Quoting Daniel Fischer
The fibonacci numbers are really cool, for fib 100000 and fib 200000 I got the same performance as with William Lee Irwins 'fastest fibonacci numbers in the west' from a couple of months ago.
He reported that mine was a little slower, but it might have been for smaller n. By the way, I believe that my specific algorithm is a new invention. I certainly haven't seen it before, though there are no doubt algorithms that are very much like it out there.
The AKS primality testing is definitely not for Haskell, I'm afraid - or somebody would have to come up with a better way to model polynomials.
Unsurprising, for two reasons: 1. AKS is mostly of theoretical interest. 2. I didn't try very hard to optimise it. IMO, reason 1 dominates reason 2.
However, if you want fast factorization, I recommend Pollard's Rho-Method - it's not guaranteed to succeed, but usually it does and it's pretty fast:
A proper library would have both, and let users either pick which algorithm to use, or to use a combination of techniques depending on whatever criteria make sense to try. Oh, I've also got code for fast combinatorial calculations (e.g. factorial and binomial coefficients). I'll have a go at setting up a darcs repo this weekend. Cheers, Andrew Bromage