I need a really good technical explantion on the absolute value

This is a discussion on I need a really good technical explantion on the absolute value within the C Programming forums, part of the General Programming Boards category; How can something like Code: define abs(x) (((x) >= 0) ? (x) : -(x)) Cause a possilbe overflow. But something ...

  1. #1
    Banned
    Join Date
    May 2007
    Location
    Berkeley, CA
    Posts
    329

    I need a really good technical explantion on the absolute value

    How can something like

    Code:
    define abs(x) (((x) >= 0) ? (x) : -(x))
    Cause a possilbe overflow.

    But something like
    Code:
    define abs(x) (((x) < 0) ? -(x) : (x))
    is passable

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,433
    hmm... with two's complement arithmetic, they both seem susceptible to overflow when the most negative value for the given type is used.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,235
    Quote Originally Posted by laserlight View Post
    hmm... with two's complement arithmetic, they both seem susceptible to overflow when the most negative value for the given type is used.
    Thinking back on it, maybe it would have made more sense to design an arithmetic where INT_MIN == INT_MAX - 1, instead of the other way around.

    Can you imagine any tradeoff, aside from eliminating the problem in this example?

  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,295
    Quote Originally Posted by brewbuck View Post
    Thinking back on it, maybe it would have made more sense to design an arithmetic where INT_MIN == INT_MAX - 1, instead of the other way around.

    Can you imagine any tradeoff, aside from eliminating the problem in this example?
    I've thought that exact same thing myself many times.


    In order to protect yourself against 0x80000000 you would need something like this, which turns it into zero instead:
    Code:
    #define abs(x) (((x) >= 0) ? (x) : (-(x) >= 0 ? -(x) : 0))
    Or you could make the result unsigned, though this wont stop someone from assigning it to a signed int and stuffing that up:
    Code:
    #define abs(x) ((unsigned)(((x) >= 0) ? (x) : -(x)))
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  5. #5
    Registered User
    Join Date
    Mar 2004
    Posts
    536
    In fact, as laserlight said, for two's complement number systems both forms give "bad" results for exactly one particular value of integer.

    Implementing either form will necessarily cause "integer overflow" for a value that is equal to the most negative representable integer. (Since the negative of that integer is not representable in the same number system.)

    There is no mathematical reason that either form would give bad results for any other value of integer. If either form gives bad results for any other value, then that's a bug, and should be reported to your compiler vendor.

    Interestingly, in the C standard (ISO/IEC 9899) there is the following comment in section 3.4.3 (defining defined behavior), that says:

    "EXAMPLE An example of undefined behavior is the behavior on integer overflow."

    This is absolutely shocking, since millions of programs (probably more) depend on benign behavior from integer overflow. Furthermore, the language Standards documents don't require that implementations give a way to detect or prevent integer overflow in the first place.

    However, in informational Annex H (talking about "Language-independent Arithmetic"), it specifically says that:

    "C’s unsigned integer types are ‘‘modulo’’ in the LIA−1 sense in that overflows or out-of-bounds results silently wrap."

    That's the behavior upon which all of those millions of programs depend: The legacy behavior of the "silent wrap," which means that upper bits are ignored and the lower bits are what they are.

    The C++ standard ISO/IEC 114884 has this to say about integer overflow (in Section 5, about Expressions)

    "If during the evaluation of an expression, the result is not mathematically defined or not in the range of representable values for its type, the behavior is undefined, unless such an expression is a constant expression (5.19), in which case the program is ill-formed."

    Creepy.

    But then they add:
    "[Note: most existing implementations of C + + ignore integer overflows...]"


    Both Standards documents have a lot to say about floating point arithmetic overflows, but not much about integer overflows.

    K&R2 simply says that, "The handling of overflow...is not defined by the language. Most existing implementations of C ignore overflow in evaluation of signed integral expressions and assignments, but this behavior is not guaranteed."

    Even though the Standards say that the result of integer overflow is undefined behavior, my feeling is that programmers are free to continue the assumption that integer overflows will be handled by throwing away the upper bits from the result and keeping the lower bits.

    (Of course, nothing in the Standards requires that integers be represented as two's complement binary quantities in the first place, but that's what we usually see these days, and that is what this discussion is about---I think.)

    D.
    Last edited by Dave Evans; 01-06-2008 at 11:49 AM.

  6. #6
    Registered User
    Join Date
    Mar 2004
    Posts
    536
    Quote Originally Posted by brewbuck View Post
    ... INT_MIN == INT_MAX - 1...Can you imagine
    Since INT_MIN is the most negative value, I think you probably mean
    INT_MIN == -(INT_MAX -1)

    I'll answer a question with a couple of questions:

    Is there any advantage of such a system over the binary two's complement representation of integers other than its being closed under the "absolute value" operation?

    Are there any disadvantages in implementation of such a system?

    Note that the one's complement system is symmetrical since INT_MIN==-INT_MAX, and computers have been built around one's complement integers. There was never a problem with abs(). We just don't see many of them these days. Have you ever wondered why?

    Of course, a C compiler doesn't have to use the computer's native number representation for its integer data types, but, given the intent of the original C author (to write operating systems), it really wouldn't make much sense, I think, to have a compiler use anything other than what is most efficient for the target architecture.

    D.
    Last edited by Dave Evans; 01-06-2008 at 01:01 PM.

  7. #7
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,295
    Quote Originally Posted by Dave Evans View Post
    Since INT_MIN is the most negative value, I think you probably mean
    INT_MIN == -(INT_MAX -1)
    I knew that's what he meant.
    Actually I've realised that this wouldn't be without it's problems either.
    Consider a = -abs(b);
    Now you have one case where a positive can't be turned into a negative!
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. In a game Engine...
    By Shamino in forum Game Programming
    Replies: 28
    Last Post: 02-19-2006, 10:30 AM
  2. Good books for learning WIN32 API
    By Junior89 in forum Windows Programming
    Replies: 6
    Last Post: 01-05-2006, 04:38 PM
  3. Good forum for computer hardware questions?
    By PJYelton in forum A Brief History of Cprogramming.com
    Replies: 8
    Last Post: 03-27-2005, 07:17 AM
  4. Good resources for maths and electronics
    By nickname_changed in forum A Brief History of Cprogramming.com
    Replies: 8
    Last Post: 12-22-2004, 03:23 PM
  5. Question about going to a technical school
    By Goalie35 in forum C++ Programming
    Replies: 1
    Last Post: 08-30-2001, 11:34 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21