Q: Feature Wish: "%" Extension

[Tim Peters]

[Paul Rubin]
> I did notice that Algorithm X from Knuth vol. 2 for extended GCD
> gives negative answers in Python if you code it straight from the book.
> It was easy to correct so I didn't analyze it carefully but I think
> floor-mod may have had something to do with it.

Note that Knuth's description of X begins with "Given nonnegative integers u
and v, ...".  So if you pass any negative ints, all bets are off.  Algorithm
A has the same restriction.

This is as literal a translation as I can dream up:

def X(u, v):
    """Return (u1, u2, u3) s.t. u*u1 + v*u2 == u3 == gcd(u, v).

    Assumes u and v are non-negative.
    """

    u1, u2, u3 = 1, 0, u
    v1, v2, v3 = 0, 1, v
    while v3:
        q = u3 / v3  # or u3//v3 under __future__ division
        t = u1-v1*q, u2-v2*q, u3-v3*q
        u1, u2, u3 = v1, v2, v3
        v1, v2, v3 = t
    assert u*u1 + v*u2 == u3
    return u1, u2, u3

If v > 0, then u3 > 0 upon return; if v < 0, then u3 < 0.  Those aren't hard
to show, relying on flooring division.  I expect the easiest way to extend
it to all ints is just to add

    if u3 < 0:
        u1, u2, u3 = -u1, -u2, -u3

before the assert.