[Haskell-cafe] NumberTheory library

[ajb at spamcop.net]

G'day all.

Quoting Daniel Fischer <daniel.is.fischer at web.de>:

> 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