[Python-Dev] Comparing heterogeneous types

[Andrew Koenig]

> Do you think you can come up with a patch, or at least a description
> of an algorithm that someone without a wizard level understanding of
> the issues could implement?

The following code is lightly but not exhaustively tested, but I do think it
gives a good idea of the algorithm.  In particular, note that
compare(fmagic, lmagic+1) is -1 even though (fmagic==lmagic+1) yields True.


lmagic = 1
fmagic = 1.0
while fmagic + 1.0 != fmagic:
    fmagic += fmagic
    lmagic += lmagic
assert fmagic + 1.0 == fmagic
assert fmagic - 1.0 != fmagic

# fmagic and lmagic are the float and long representations of the
# smallest power of 2 for which the floating-point LSB is strictly
# greater than 1.  Accordingly, adding 1 to this magic value doesn't
# change it, but subtracting 1 does (because it is a power of 2, so
# the subtraction makes the representation one bit shorter).

# Because of the properties of fmagic and lmagic, converting an
# integer that is < lmagic to floating-point will lose no information,
# and converting a floating-point number that is >= fmagic to long
# will also lose no information.

def sign(x):
    if x > 0:
        return 1
    if x < 0:
        return -1
    return 0

def simple_compare(x, y):               # arguments both float or neither
    if x < y:
        return -1
    if x > y:
        return 1
    return 0

def compare(x, y):
    # We handle only integers and floats
    if type(x) not in [int, long, float]:
        raise TypeError, "left argument to compare not integer or float"
    if type(y) not in [int, long, float]:
        raise TypeError, "right argument to compare not integer or float"

    # If the arguments are the same type (counting int and long as
    # the same), there's nothing special to do
    if (type(x) == float) == (type(y) == float):
        return simple_compare(x, y)

    # Perhaps the signs will make the comparison unnecessary
    signx = sign(x)
    signy = sign(y)
    if signx != signy or signx == 0:
        return simple_compare(signx, signy)

    # Now we know that both arguments are nonzero and have the same
    # sign.  We'll use signx to remember the original sign and make
    # the arguments both positive for convenience.
    if signx < 0:
        x = -x
        y = -y

    # We have reduced the problem to one where the arguments are both
    # positive and exactly one of them is float--but we don't know
    # which one.  For convenience, we'll make x float by swapping x
    # and y if necessary, adjusting signx as appropriate.
    if type(y) == float:
        x, y = y, x
        signx = -signx

    assert type(x) == float
    assert type(y) in [int, long]
    assert x > 0 and y > 0

    # If x and y are on different sides of the magic barrier, we're
    # done.
    if x >= fmagic and y < lmagic:
        return signx
    if x < fmagic and y >= lmagic:
        return -signx

    # Now we know that x and y are on the same side of the barrier.
    # Depending on which side, we will convert x to long or y to
    # float, then compare.
    if x >= fmagic:
        x = long(x)
    else:
        y = float(y)
    return signx * simple_compare(x, y)