[ccan] Mathematics Module

[Timothy B. Terriberry]

Some of this stuff seems a little trivial to include, but if we're going
to do so...

The result of nCr is guaranteed to be an integer after each iteration,
and so there's a) no reason to keep a separate numerator and denominator
and b) no reason to do a minimum of nine (9!) divisions every iteration.
Only a single gcd() is needed, and even that can often be skipped,
requiring only 2-3 divisions per iteration. This is illustrated in
choose.c (attached). You can easily add the check for the smaller r (_m
in this implementation), upgrade the types to long, etc., as desired. If
one really cared about speed, the divisions could be entirely replaced
by multiplications and a small lookup table, since m and n are known to
have a very limited range (or the result will overflow).

Also included are a gcd() implementation without tail recursion and
egcd(), the "extended" gcd, as well as a nice illustration of the use of
egcd, a Chinese Remainder Theorem solver for systems of linear
congruences. I don't have time to format these into a nice module with
test cases right now, but feel free to take what you want and throw the
rest in "junk". The code is (C) 1998-2001, except crt.c, which is (C)
1999-2001, 2007. I'm releasing it here under the LGPLv2 license.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: nmbrthry.tar.bz2
Type: application/x-bzip
Size: 2978 bytes
Desc: not available
URL: <http://lists.ozlabs.org/pipermail/ccan/attachments/20090318/06e83a7c/attachment.bin>