[Haskell-cafe] NumberTheory library

[ajb at spamcop.net]

G'day all.

I've finally had a chance to implement some of these changes.

Quoting Yitzchak Gale <gale at sefer.org>:

> o I think you are testing w' * w' < n each time, even
>    when you are repeating factors of the same prime p.
>    You only need to do that when you move to the next p.

Actually, it turns out we only test that when we change wheels, which is
not very often.  There's still some lambda dropping which could be done,
but I'm not sure it's worth it.

> o You can use divMod (or quotRem) instead of using
>    div and then multiplying. (That's an ancient trick
>    from C. It may not make a difference on modern
>    CPUs.)

Fixed.

> o I personally would much prefer a function
>    that only returns prime numbers, not -1, 0,
>    or 1.

I'd like, if I can, to preserve the property that product is a retraction
for factor.  I've changed it so that factor 1 = [], but I'm unsure what to
do with 0 and negative numbers.  I think that factor 0 = [0] is the only
reasonable thing to return.  As for negative numbers, the two easiest
solutions are return -1 as a first factor, or negate the first prime
factor returned.  Even then, you'd have to return factor (-1) = [-1].

Maybe there should be two functions exposed?

Cheers,
Andrew Bromage