Absolute value of signed 32-bit random integer

[John B. Matthews]

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)>

 

[Joshua Cranmer]

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?

 

[markspace]

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.

 

[Arne Vajhøj]

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]

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

 

[Eric Sosman]

[...]
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?

 

[Joshua Cranmer]

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.

 

[markspace]

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]

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

Show me one that doesn't.

 

[Joshua Cranmer]

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.

 

[Tom Anderson]

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'

 

[Arne Vajhøj]

Show me one that doesn't.

Alpha

Arne

 

[Arne Vajhøj]

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.

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]

[...]

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]

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]

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]

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]

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]

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

 

[markspace]

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.