Greater or less than when comparing numbers with different signs?

[tungsten]

I'm I overthinking this?

I cannot think of a simple way to compare two numbers for all possible sign cases (both positive, both negative, one negative and the other positive).

Here is some Python code for the simplest thing I could think of. It performs a different calculation depending on whether the two numbers have the same sign or not.

The problem with the algorithm is that it uses the expensive `isNegative` function.

def isNegative ( x ):

        # Check most significant bit
        mask = 2 ** ( N_BITS - 1 )
        return ( x & mask ) == mask

def gte ( x, y ):

        xIsNeg = isNegative( x )
        yIsNeg = isNegative( y )

        if xIsNeg ^ yisNeg:  # opposite signs

                return not xIsNeg  # if x is positive and y is negative then x > y, and vice versa

        else:  # same signs

                diff = subtract( x, y )

                return not isNegative( diff )  # if the difference is not negative then x >= y

[cadet1620]

For Python, I think

    def isNegative(x):
        return bool(x >> (N_BITS-1))

or

    def isNegative(x):
        global SIGN_BIT   # 2**(N_BITS-1)
        return bool(x & SIGN_BIT)

would be much faster.


What are x and y? Python integers in range(0, 2**N_BITS) representing a 2's-complement integer?

If so, you can flip the sign bits in x and y and compare them directly.

    def gte(x, y):
        global SIGN_BIT   # 2**(N_BITS-1)
        return x ^ SIGN_BIT >= y ^ SIGN_BIT

--Mark

[tungsten]

Thanks for the reply!

A bit more context:

What are x and y? Python integers in range(0, 2**N_BITS) representing a 2's-complement integer?

Yes. The 'subtract' function performs the appropriate 2's-complement subtraction.

The Python code is a sort of pseudo code for what I need to implement in Hack's assembly language to perform a greater than comparison (and by modification a less than comparison). (I find it easier to think in a higher level language).

I realized in a roundabout way that the method I was using before (a simple comparison of the difference) doesn't always work when the numbers have different signs... ( for example '0 > ( - 32767 - 1 )' returns false when it should return true because the difference is...

Wait a sec... as I'm typing this it's occurred to me that this only fails with the number 32768... whose two complement is itself... so it's more of an edge case than a shortcoming...

Looking again at the code that sent me down this path I see my problem has nothing to do with the algorithm being wrong...

More context:

I had tried to allocate an array of size 32767 in order to test that the heap overflow error triggers. Instead the allocation cryptically worked... It turns out when I add the header ( 32767 + x ) in Memory.jack, the requested size becomes a negative number. I have a check along the lines of 'if freeSpace > requestedSize, perform allocation'. And with the header added on, of course 'freeSpace' is now greater than some negative number... So in fact the algorithm was not the culprit in this case... just my assumptions (insert facepalm emoji).

TLDR: Wasn't a problem to begin with... just a red herring.

[cadet1620]

You've seen the tip of the iceberg and successfully navigated around it; proper comparison is problematic on the Hack computer.

The simple algebraic manipulation
 a > b ↔ a−b > 0
hides a signed integer overflow.

The test code for the VM translator avoids any comparisons that will encounter the overflow. This allows student's simple implementations of the VM gt and lt commands to pass the tests.

Here's an example of the issue:

if (20000 > -30000)

gets compiled to VM code using the gt command which gets translated to ASM something like

@x
D=M     // D = 20000
@y
D=D-M   // D = 20000 - -30000 = 50000 = -15536
@TRUE
D;JGT   // Does not jump

Bulletproof translation of lt and gt does require special handling like your pseudocode to deal with the case when the signs are different.

The easiest way to check the sign bit is with JLT/JGE.

--Mark

[tungsten]

Hi Mark

I'm really interested in writing a bulletproof version (performance concerns are secondary to accuracy for my needs).

The easiest way to check the sign bit is with JLT/JGE

Do you mean something like,

def isNegative():

    return x < 0   # JLT

Also to implement, the Jack to VM compiler would translate a '>' or '<' symbol it encounters into an appropriate function call (such as the psuedocode). And the 'isNegative' function would need to be an assembly function in order to distinguish its use of the '<' symbol as a reference to the 'JLT' instruction and not a call to the wrapper function?

Regards

[cadet1620]

[Edit: fix return FALSE for mixed signs with x > y.]

tungsten wrote

Also to implement, the Jack to VM compiler would translate a '>' or '<' symbol it encounters into an appropriate function call (such as the psuedocode).

The Jack Compiler does not have anything to do with this. It continues to generate only a gt or lt VM command for comparisons.

This is all about the ASM code that is generated by the VM Translator for the gt and lt commands.

I find that pseudocode that includes subroutines is not so helpful when designing ASM sequences for a language that does not (easily) support nested subroutine calling at the machine level.

The code that is generated for correct comparisons will be significantly longer than the simple subtraction compare, so it should be written as assembly language routines the same way that call/return VM Commands are handled.

As such, your original pseudocode can be rewritten using only if/else and comparisons against 0 that the ASM supports, and it will be much more helpful:

// x < y code
if x < 0
    if y >= 0
        // signs don't match, x < y
        return TRUE
else
    // x is >= 0
    if y < 0
        // signs don't match, x > y
        return FALSE
// signs match; x - y won't overflow
if x - y < 0
    return TRUE
else
    return FALSE

--Mark