# Greater or less than when comparing numbers with different signs?

6 messages
Open this post in threaded view
|

## Greater or less than when comparing numbers with different signs?

 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
Open this post in threaded view
|

## Re: Greater or less than when comparing numbers with different signs?

 Administrator 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
Open this post in threaded view
|

## Re: Greater or less than when comparing numbers with different signs?

 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.
Open this post in threaded view
|

## Re: Greater or less than when comparing numbers with different signs?

 Administrator 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
 Administrator This post was updated on . [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