Absolute value of signed 32-bit random integer

Discussion in 'Java' started by John B. Matthews, Nov 7, 2009.

  1. Given an instance of java.util.Random, FindBugs correctly warns [1]
    that taking the absolute value of a signed 32-bit random integer can
    (rarely) produce a negative number, e.g.:

    int randomIndex = Math.abs(random.nextInt()) % fortuneArray.length;

    I had initially thought to mask the high bit:

    int randomIndex = (random.nextInt() & 0x7fffffff) % fortuneArray.length;

    Reflecting on the limitations of Linear Congruential Generators (LCG)
    [2], I was then inclined to discard the low-order bit using the
    unsigned right shift operator:

    int randomIndex = (random.nextInt() >>> 1) % fortuneArray.length;

    Then I realized that the preferred method is already in the API [3]:

    int randomIndex = random.nextInt(fortuneArray.length);

    D'oh. Long odyssey; back in Ithaca; comments welcomed.

    [1] "Bad attempt to compute absolute value of signed 32-bit random
    integer. This code generates a random signed integer and then computes
    the absolute value of that random integer. If the number returned by
    the random number generator is Integer.MIN_VALUE, then the result will
    be negative as well (since Math.abs(Integer.MIN_VALUE) ==
    Integer.MIN_VALUE)."
    [2]<http://en.wikipedia.org/wiki/Linear_congruential_generator>
    [3]<http://java.sun.com/javase/6/docs/api/java/util/Random.html#nextInt(int)>

    --
    John B. Matthews
    trashgod at gmail dot com
    <http://sites.google.com/site/drjohnbmatthews>
    John B. Matthews, Nov 7, 2009
    #1
    1. Advertising

  2. On 11/07/2009 02:48 PM, Peter Duniho wrote:
    > All I can say is that I learned a lot from your post. First, that Java
    > has this broken Math.abs() function that can return a negative number
    > (duh!).


    abs(-2^31) == -2^31 will hold true for many computer systems (pretty
    much everyone who uses 32-bit 2's complement arithmetic). What would you
    rather it return?

    --
    Beware of bugs in the above code; I have only proved it correct, not
    tried it. -- Donald E. Knuth
    Joshua Cranmer, Nov 7, 2009
    #2
    1. Advertising

  3. John B. Matthews

    markspace Guest

    Joshua Cranmer wrote:
    > On 11/07/2009 02:48 PM, Peter Duniho wrote:
    >> All I can say is that I learned a lot from your post. First, that Java
    >> has this broken Math.abs() function that can return a negative number
    >> (duh!).

    >
    > abs(-2^31) == -2^31 will hold true for many computer systems (pretty
    > much everyone who uses 32-bit 2's complement arithmetic). What would you
    > rather it return?



    I'd prefer some sort of arithemic overflow exception, because that's
    what happened, you overflowed a positive number to a negative number.
    All CPUs have two overflow bits, one for signed math (which would be the
    correct one to use for this case) and one for unsigned math. If you're
    working with signed numbers, use the right bit.
    markspace, Nov 7, 2009
    #3
  4. markspace wrote:
    > Joshua Cranmer wrote:
    >> On 11/07/2009 02:48 PM, Peter Duniho wrote:
    >>> All I can say is that I learned a lot from your post. First, that Java
    >>> has this broken Math.abs() function that can return a negative number
    >>> (duh!).

    >>
    >> abs(-2^31) == -2^31 will hold true for many computer systems (pretty
    >> much everyone who uses 32-bit 2's complement arithmetic). What would
    >> you rather it return?

    >
    > I'd prefer some sort of arithemic overflow exception,


    I agree.

    > because that's
    > what happened, you overflowed a positive number to a negative number.


    But Java in general does not do that.

    > All CPUs have two overflow bits, one for signed math (which would be the
    > correct one to use for this case) and one for unsigned math. If you're
    > working with signed numbers, use the right bit.


    I very much doubt that *all* CPU's have that.

    Arne
    Arne Vajhøj, Nov 7, 2009
    #4
  5. Peter Duniho wrote:
    > Joshua Cranmer wrote:
    >> On 11/07/2009 02:48 PM, Peter Duniho wrote:
    >>> All I can say is that I learned a lot from your post. First, that Java
    >>> has this broken Math.abs() function that can return a negative number
    >>> (duh!).

    >>
    >> abs(-2^31) == -2^31 will hold true for many computer systems (pretty
    >> much everyone who uses 32-bit 2's complement arithmetic). What would
    >> you rather it return?

    >
    > I'd rather it not return anything. As "markspace" says, an exception
    > would be preferable.


    I agree.

    > The point of a framework like Java is to isolate the user from
    > machine-dependent behaviors.


    Strictly speaking it is not machine dependent - Java requires
    2's complement of 8/16/32/64 bit.

    > A negative number is _clearly_ an
    > incorrect result of taking the absolute value of some number.


    It is not really incorrect. It works as specified in the documentation.

    But it is very non-intuitive and a bad decision to define it that way.

    Arne
    Arne Vajhøj, Nov 7, 2009
    #5
  6. John B. Matthews

    Eric Sosman Guest

    Peter Duniho wrote:
    > [...]
    > All I can say is that I learned a lot from your post. First, that Java
    > has this broken Math.abs() function that can return a negative number
    > (duh!).


    What fix would you suggest?

    --
    Eric Sosman
    lid
    Eric Sosman, Nov 7, 2009
    #6
  7. On 11/07/2009 05:50 PM, Peter Duniho wrote:
    > Getting the _actual_ absolute value of some number will never correctly
    > return a negative result. So, either Math.abs() isn't really a function
    > returning the absolute value of the input, or it's not behaving correctly.


    By that argument, most of the operations in Java or almost every other
    programming language are also not mathematically correct. For example,
    if I do 2000000000 * 2 in Java, I do not get 4000000000, but a very
    large negative number. Obviously it doesn't do multiplication, it just
    does something that looks like multiplication.

    I would argue that Math.abs is correct, modulo the limitations of the
    Java virtual machine.

    > But the fact remains, if one is _actually_ taking the absolute value of
    > some number, it's an incorrect result to produce a negative number.
    > That's fundamental to the concept of "absolute value".


    An alternate way to look at it: the returning of a negative number is a
    very fast way of indicating the error condition of "cannot compute
    absolute value." The vast majority of calls to Math.abs will not have
    INT_MIN as their argument: I suspect in many cases, such calls would
    have been filtered out by range limitations on user data entry. It is
    very simple to check for this error condition (if (abs(x) == x)) and
    convert it into a real overflow exception, for the few cases that it
    would come up as input.

    --
    Beware of bugs in the above code; I have only proved it correct, not
    tried it. -- Donald E. Knuth
    Joshua Cranmer, Nov 7, 2009
    #7
  8. John B. Matthews

    markspace Guest

    Joshua Cranmer wrote:

    > By that argument, most of the operations in Java or almost every other
    > programming language are also not mathematically correct. For example,
    > if I do 2000000000 * 2 in Java, I do not get 4000000000, but a very
    > large negative number. Obviously it doesn't do multiplication, it just
    > does something that looks like multiplication.


    This is C thinking -- return the result that the machine does. I
    believe Java should have allowed for at least the option of generating
    exceptions on overflow.

    I realize we're unlikely to see even an option at this date, but I can
    still gripe about it.


    > An alternate way to look at it: the returning of a negative number is a
    > very fast way of indicating the error condition of "cannot compute
    > absolute value."


    Checking a return value rather than throwing an exception is a known
    anti-pattern.


    > The vast majority of calls to Math.abs will not have
    > INT_MIN as their argument:


    So we now program based on "mostly works?"
    markspace, Nov 8, 2009
    #8
  9. John B. Matthews

    markspace Guest

    Arne Vajhøj wrote:

    > I very much doubt that *all* CPU's have that.


    Show me one that doesn't.
    markspace, Nov 8, 2009
    #9
  10. On 11/07/2009 06:48 PM, Peter Duniho wrote:
    > The bottom line: Java absolutely could have been designed differently,
    > and while you may argue that the current design has some abstract
    > advantage of being more "coherent", in reality that's little better an
    > explanation than simply "well, that's just how Java is" (which, in some
    > sense, it not really that bad an explanation). The fact remains,
    > Math.abs() is broken.


    Look at it like this: `int' defines an element of the set of integer
    numbers which can be represented by a 32-bit 2's complement integer. It
    does not define the element of the set of integers: 2^31 in particular
    does not contain it. It is clear, then, in this set, that the
    mathematical absolute value is defined for all points except -2^31. Java
    decided to extend this limited absolute value function to the value
    -2^31 by defining abs(-2^31) := -2^31--it is an extension of the
    mathematical absolute value, and so it is mathematically correct.

    If you wish to reduce it to the absolute value function you know and
    love from mathematics, just exclude -2^31 from its domain. Really, it's
    not hard.

    --
    Beware of bugs in the above code; I have only proved it correct, not
    tried it. -- Donald E. Knuth
    Joshua Cranmer, Nov 8, 2009
    #10
  11. John B. Matthews

    Tom Anderson Guest

    On Sat, 7 Nov 2009, Joshua Cranmer wrote:

    > On 11/07/2009 05:50 PM, Peter Duniho wrote:
    >
    >> Getting the _actual_ absolute value of some number will never correctly
    >> return a negative result. So, either Math.abs() isn't really a function
    >> returning the absolute value of the input, or it's not behaving correctly.

    >
    > By that argument, most of the operations in Java or almost every other
    > programming language are also not mathematically correct.


    You're quite right. They aren't. We've mostly put up with it because we
    don't know any better and we're terrified of the performance cost of doing
    it right [1], but they're still wrong.

    tom

    [1] Even though we happily use XML, RDBMSs, J2EE, etc.

    --
    We had two bags of grass, seventy-five pellets of mescaline, five sheets
    of high powered blotter acid, a salt shaker half full of cocaine, and a
    whole galaxy of multi colored uppers, downers, screamers, laughers... and
    also a quart of tequila, a quart of rum, a case of beer, a pint of raw
    ether and two dozen amyls. Not that we needed all this for the trip,
    but once you get locked in a serious drug collection, the tendency is
    to push it as far as you can. -- Hunter S. Thompson, 'Fear and loathing
    in Las Vegas'
    Tom Anderson, Nov 8, 2009
    #11
  12. markspace wrote:
    > Arne Vajhøj wrote:
    >> I very much doubt that *all* CPU's have that.

    >
    > Show me one that doesn't.


    Alpha

    Arne
    Arne Vajhøj, Nov 8, 2009
    #12
  13. markspace wrote:
    > Joshua Cranmer wrote:
    >> By that argument, most of the operations in Java or almost every other
    >> programming language are also not mathematically correct. For example,
    >> if I do 2000000000 * 2 in Java, I do not get 4000000000, but a very
    >> large negative number. Obviously it doesn't do multiplication, it just
    >> does something that looks like multiplication.

    >
    > This is C thinking -- return the result that the machine does. I
    > believe Java should have allowed for at least the option of generating
    > exceptions on overflow.


    Check for integer overflow is a good thing.

    I think Java should have had it.

    Or at least an option to enable it.

    > I realize we're unlikely to see even an option at this date,


    Yup.

    > but I can
    > still gripe about it.


    Sure.

    Just don't call it incorrect.

    >> The vast majority of calls to Math.abs will not have INT_MIN as their
    >> argument:

    >
    > So we now program based on "mostly works?"


    No we program based on that that code should work as described
    in the documentation.

    Arne
    Arne Vajhøj, Nov 8, 2009
    #13
  14. Peter Duniho wrote:
    > Arne Vajhøj wrote:
    >> [...]
    >>> A negative number is _clearly_ an
    >>> incorrect result of taking the absolute value of some number.

    >>
    >> It is not really incorrect. It works as specified in the documentation.

    >
    > You misunderstand my words. Mathematically, the absolute value of some
    > number is always non-negative. A negative result is "clearly incorrect".
    >
    > Yes, the specification/documentation stipulates the behavior observed.
    > But the specification is just as incorrect as the behavior, with respect
    > to the mathematical definition of "absolute value".
    >
    > Specific to what I wrote: as I said elsewhere, the Math.abs() method in
    > Java does not actually produce the absolute value of some number. It
    > produces something that _looks_ a _lot_ like the absolute value of the
    > input, but which in reality is subtly different.
    >
    > Getting the _actual_ absolute value of some number will never correctly
    > return a negative result. So, either Math.abs() isn't really a function
    > returning the absolute value of the input, or it's not behaving correctly.
    >
    > I agree that given the docs, it's behaving correctly. I.e. while a
    > negative result is incorrect when getting the absolute value of some
    > number, that doesn't mean that Math.abs() is "incorrect" in the sense of
    > the documentation. It just means that the documentation never claims
    > the function returns the _actual_ absolute value of the input.
    >
    > And some may argue that it doesn't matter that Math.abs() isn't actually
    > an absolute value function. Personally, I think if the function's not
    > intended to be a true absolute value, it shouldn't be named "abs()". :)
    >
    > But the fact remains, if one is _actually_ taking the absolute value of
    > some number, it's an incorrect result to produce a negative number.
    > That's fundamental to the concept of "absolute value".


    Programming is programming. Code that works as it is intended is
    correct code.

    If the name of some method has a name that happen to give you
    associations to a concept in math which has different semantics,
    then the only think that is incorrect is your assumption that
    programming should work like math.

    This is essential stuff for software development - it is the difference
    between a bug report and a change request.

    You have not found a bug in Math.abs - you have found something
    you want changed.

    Arne
    Arne Vajhøj, Nov 8, 2009
    #14
  15. Joshua Cranmer wrote:
    > On 11/07/2009 05:50 PM, Peter Duniho wrote:
    >> But the fact remains, if one is _actually_ taking the absolute value of
    >> some number, it's an incorrect result to produce a negative number.
    >> That's fundamental to the concept of "absolute value".

    >
    > An alternate way to look at it: the returning of a negative number is a
    > very fast way of indicating the error condition of "cannot compute
    > absolute value." The vast majority of calls to Math.abs will not have
    > INT_MIN as their argument: I suspect in many cases, such calls would
    > have been filtered out by range limitations on user data entry. It is
    > very simple to check for this error condition (if (abs(x) == x)) and
    > convert it into a real overflow exception, for the few cases that it
    > would come up as input.


    Throwing an exception would create more readable code.

    Arne
    Arne Vajhøj, Nov 8, 2009
    #15
  16. John B. Matthews

    Arne Vajhøj Guest

    Peter Duniho wrote:
    > Thomas Pornin wrote:
    >> According to Peter Duniho <>:
    >>> You misunderstand my words. Mathematically, the absolute value of
    >>> some number is always non-negative. A negative result is "clearly
    >>> incorrect".

    >>
    >> Note that if you add two positive values of type 'int' you may also get
    >> a negative result. This is no more and no less incorrect than Math.abs()
    >> returning a negative value.

    >
    > That depends on your point of view, I suppose. In the sense that many
    > consider arithmetic operators more "fundamental" than a call to a Math
    > function, it is more reasonable to define the method to always throw an
    > exception on invalid input than to require the same from the basic
    > arithmetic operators.
    >
    > More importantly of course, there are computational (non-mathematical)
    > justifications for allowing silent overflow for basic arithmetic, but
    > not for higher-level operations.
    >
    > But in the sense that it's "no more and no less incorrect" of one or the
    > other, then yes...they are both incorrect behavior.


    If they work like described in JLS and JVM spec, then they are correct.

    Arne
    Arne Vajhøj, Nov 8, 2009
    #16
  17. John B. Matthews

    Arne Vajhøj Guest

    Tom Anderson wrote:
    > On Sat, 7 Nov 2009, Joshua Cranmer wrote:
    >> On 11/07/2009 05:50 PM, Peter Duniho wrote:
    >>> Getting the _actual_ absolute value of some number will never correctly
    >>> return a negative result. So, either Math.abs() isn't really a function
    >>> returning the absolute value of the input, or it's not behaving
    >>> correctly.

    >>
    >> By that argument, most of the operations in Java or almost every other
    >> programming language are also not mathematically correct.

    >
    > You're quite right. They aren't. We've mostly put up with it because we
    > don't know any better and we're terrified of the performance cost of
    > doing it right [1], but they're still wrong.


    If they work as documented, then they are correct.

    We may still want that the specs were different.

    Arne
    Arne Vajhøj, Nov 8, 2009
    #17
  18. John B. Matthews

    Arne Vajhøj Guest

    Joshua Cranmer wrote:
    > On 11/07/2009 06:48 PM, Peter Duniho wrote:
    >> The bottom line: Java absolutely could have been designed differently,
    >> and while you may argue that the current design has some abstract
    >> advantage of being more "coherent", in reality that's little better an
    >> explanation than simply "well, that's just how Java is" (which, in some
    >> sense, it not really that bad an explanation). The fact remains,
    >> Math.abs() is broken.

    >
    > Look at it like this: `int' defines an element of the set of integer
    > numbers which can be represented by a 32-bit 2's complement integer. It
    > does not define the element of the set of integers: 2^31 in particular
    > does not contain it. It is clear, then, in this set, that the
    > mathematical absolute value is defined for all points except -2^31. Java
    > decided to extend this limited absolute value function to the value
    > -2^31 by defining abs(-2^31) := -2^31--it is an extension of the
    > mathematical absolute value, and so it is mathematically correct.
    >
    > If you wish to reduce it to the absolute value function you know and
    > love from mathematics, just exclude -2^31 from its domain. Really, it's
    > not hard.


    Throwing and exception inside Math.abs for that value is
    a implementation of that.

    Arne
    Arne Vajhøj, Nov 8, 2009
    #18
  19. John B. Matthews

    Arne Vajhøj Guest

    Thomas Pornin wrote:
    > 2. Raise errors on overflow / underflow (i.e. throw an exception, in
    > Java terminology).


    > Design 2 is common in Ada.


    Ada was designed to prevent programming errors.

    Which by definition makes ideas from Ada interesting in my
    opinion.

    Arne
    Arne Vajhøj, Nov 8, 2009
    #19
  20. John B. Matthews

    markspace Guest

    Arne Vajhøj wrote:
    > markspace wrote:
    >> Arne Vajhøj wrote:
    >>> I very much doubt that *all* CPU's have that.

    >>
    >> Show me one that doesn't.

    >
    > Alpha



    It seems to not have a condition code register at all, for "speed."
    That's the problem with RISC, they don't count all the instructions you
    have to execute just to get a meaningful result. With no condition code
    register the problem of even finding an overflow goes up.

    *shrug* it was released in 1994, and abandoned in 2001. That's a pretty
    old CPU.
    markspace, Nov 8, 2009
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Replies:
    14
    Views:
    2,077
    CBFalconer
    Jun 18, 2005
  2. globalrev
    Replies:
    4
    Views:
    745
    Gabriel Genellina
    Apr 20, 2008
  3. Fore
    Replies:
    29
    Views:
    15,191
    Rashad
    Sep 21, 2008
  4. Robert Somerville
    Replies:
    5
    Views:
    2,153
    Irmen de Jong
    Jan 8, 2010
  5. Robert Somerville
    Replies:
    0
    Views:
    423
    Robert Somerville
    Jan 8, 2010
Loading...

Share This Page