macOS Unsigned types in C

[mac2x]

I have a bug in a program (no it is not an assignment; I am working on my own this term) that uses unsigned ints.

Without going into the gory details (it's a large program), I need to take the factorial of an expression n - r. Of course, I want to test to be sure that I don't feed my factorial function a negative.

if ( n - r > 0 )
{...}

Both n and r are of type unsigned long int.

According the Harbison and Steele (5th edition):

These conversions can be surprising. For example, because unsigned integers are always non-negative, you would expect that the following test would always be true:

unsigned int u;
...
if  ( u > -1 ) ...

However, it is always false! the (signed) -1 is converted to an unsigned integer before the comparison, yielding the largest unsigned integer, and the value of u cannot be greater than that integer.

In my program, the problem happens when n is less than r, say 3 an 5 respectively. This means that the difference n - r is negative, and by the above is converted to an unsigned integer, which results in my factorial function being sent an enormous number which invariably crashes the program. Am I thinking correctly here?

I do not wish to be given the solution to this bug; I merely want to know if I am on the right track in finding it.


Xcode project is attached.

Thanks!

 

[kpua]

I suspect you're on the right track here. If n is greater than r, then n-r will wrap around to very large integer values.

I won't give you the solution straight out, but can you think of a mathematical equivalent to the relation (n - r > 0) that doesn't subtraction and is therefore immune from the integer underflow error?

 

[mac2x]

Indeed I can!

if (n > r)
{...}

The test fails if n = 3 and r = 5, and the function is not called. This is exactly what I wanted. Thanks again!

 

[kuwisdelu]

It may not be important for your program, but don't forget mathematically, 0! = 1, too.

 

[Sydde]

It may not be important for your program, but don't forget mathematically, 0! = 1, too.

Which raises an odd question (the kind only I would come up with). In Standard Apple Numerics Environment ("SANE", in Classic Mac OS) they note that a number has 3 important components: the mantissa (numeric value), the characteristic (exponent) and the sign. Because of this, you could have a number equal to negative zero. What I am unsure of is whether ( 0 == -0 ) could be counted on to return true or false.

 

[lee1210]

Which raises an odd question (the kind only I would come up with). In Standard Apple Numerics Environment ("SANE", in Classic Mac OS) they note that a number has 3 important components: the mantissa (numeric value), the characteristic (exponent) and the sign. Because of this, you could have a number equal to negative zero. What I am unsure of is whether ( 0 == -0 ) could be counted on to return true or false.

This sounds like IEEE-754 floating point, or similar. This is for floating point estimation in binary. Integers can be represented exactly in binary. In IEEE-754 zero and negative zero are not equal bit patterns (so a memcmp would call them different), but == should say they're the same.

-Lee