Absolute value of signed 32-bit random integer

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

1. John B. MatthewsGuest

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;

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

John B. Matthews, Nov 7, 2009

2. Joshua CranmerGuest

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

3. markspaceGuest

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
4. Arne VajhÃ¸jGuest

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
5. Arne VajhÃ¸jGuest

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
6. Eric SosmanGuest

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
7. Joshua CranmerGuest

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
8. markspaceGuest

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

> 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
9. markspaceGuest

Arne VajhÃ¸j wrote:

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

Show me one that doesn't.

markspace, Nov 8, 2009
10. Joshua CranmerGuest

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
11. Tom AndersonGuest

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
12. Arne VajhÃ¸jGuest

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
13. Arne VajhÃ¸jGuest

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

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
14. Arne VajhÃ¸jGuest

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
15. Arne VajhÃ¸jGuest

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
16. Arne VajhøjGuest

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
17. Arne VajhøjGuest

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
18. Arne VajhøjGuest

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
19. Arne VajhøjGuest

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
20. markspaceGuest

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