LLL in Python

I've been checking my LLL routine. It's already live on my
website to simplify the unison vectors. The previous
algorithm (naïve Tenney reduction) was failing to find
simple things like 100:99 for 13-limit magic. The
vectors/ratios you see now are the simplest ones within 3
lattice points of the LLL reduced set.

Now, there are various problems with LLL as a standard form
for generators or unison vectors. There's a free parameter
that controls the strictness of the results, and
implementations tend not to document what value they use.
Because of this, different definitions of it can disagree.
Even when they should agree, trivial implementation details
can affect the results because the output isn't strictly
defined.

What I've done is to follow the algorithm as defined in the
"Modern Computer Algebra" book I own. I've tested it with
the two examples in the book. I know that these examples
disagree with Pari/GP but I don't know what variant of the
algorithm they implemented. I know that Wikipedia is
describing a different variant and the example (which
happens to use exactly the same input as my book) is wrong,
but given that I don't really understand the example I
don't know how to correct it.

I also know that the 3x3 example in "Modern Computer
Algebra" doesn't follow the algorithm they described. It
comes down to whether halves should round up or down. They
strictly defined the rounding, and ½ should most definitely
round up. That's good, because halves rounding up is the
easiest thing to implement in Python. According to the
example, though, ½ rounds down. I don't know why. I've
fudged it so that halves always round down. They're
probably doing something cleverer, like the bankers'
rounding used by default in IEEE 754:

http://en.wikipedia.org/wiki/Bankers%27_rounding#Round_half_to_even

Maybe they didn't realize the floating point library they
were using was implemented differently to how they
described. It does matter in that you get different
results for different rounding rules. It probably doesn't
matter in that all the alternatives will fulfill the
promises the LLL algorithm gives you.

I would paste the code here, but my email client completely
screws up the line wrapping. You can find it in the file
regutils.py in the bundle
http://x31eq.com/temper/regular.zip

It works for inner products that correspond to different
weightings of the Euclidean axes. It doesn't work for
inner products that are more generalized than that, so it's
no good for minimizing Cangwu badness. If you're using a
library that doesn't allow you to specify the inner
product, you can still get Tenney-weighted LLL to work by
weighting the vectors before you feed them in and reversing
the process on any vectors that come out.

Graham