Velocity Reviews > Java > Absolute value of signed 32-bit random integer

# Absolute value of signed 32-bit random integer

John B. Matthews
Guest
Posts: n/a

 11-07-2009
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

Joshua Cranmer
Guest
Posts: n/a

 11-07-2009
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

markspace
Guest
Posts: n/a

 11-07-2009
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.

Arne Vajhøj
Guest
Posts: n/a

 11-07-2009
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
Guest
Posts: n/a

 11-07-2009
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

Eric Sosman
Guest
Posts: n/a

 11-07-2009
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
http://www.velocityreviews.com/forums/(E-Mail Removed)lid

Joshua Cranmer
Guest
Posts: n/a

 11-07-2009
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

markspace
Guest
Posts: n/a

 11-08-2009
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
Guest
Posts: n/a

 11-08-2009
Arne Vajhøj wrote:

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

Show me one that doesn't.

Joshua Cranmer
Guest
Posts: n/a

 11-08-2009
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