commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Alex Herbert <alex.d.herb...@gmail.com>
Subject Re: [numbers-core] Special cases in greatest common divisor methods
Date Sat, 20 Jul 2019 12:30:01 GMT


> On 20 Jul 2019, at 10:53, Heinrich Bohne <heinrich.bohne@gmx.at> wrote:
> 
> I have suggestion regarding what to do with the special cases
> Integer.MIN_VALUE and Long.MIN_VALUE in the methods from ArithmeticUtils
> that calculate the greatest common divisor of two ints or longs.
> Currently, these methods throw an ArithmeticException if the GCD of the
> arguments is 2^31 or 2^63, respectively. However, what if, instead,
> these methods simply returned -2^31 and -2^63 in these special cases? I
> think this would have several advantages:
> 
>  - By returning -2^31 and -2^63, the methods will /always/ return a
> unique "representation" of the GCD, even if this representation may,
> under one predictable circumstance, not be the GCD itself but its
> additive inverse. An exception, on the other hand, implies that the GCD
> cannot be represented and is therefore less useful.
>  - Throwing an exception is more expensive than returning -2^31 or -2^63.
>  - If the distinction between the GCD and its additive inverse matters
> to the caller, the caller would have to handle the case of
> Integer.MIN_VALUE or Long.MIN_VALUE separately in any case, whether the
> method throws an exception or returns -2^31 or -2^63. There may,
> however, be cases, where this distinction does not matter, for example,
> if the caller just wants to check if two numbers are coprime or not (in
> fact, there already is such a case, namely in the constructor
> Fraction(int, int) from the fraction module). An exception would then
> force the caller to handle the case separately, whereas this would not
> be necessary if the method returned -2^31 or -2^63.
>  - The practice of returning Integer.MIN_VALUE and Long.MIN_VALUE in
> place of 2^31 and 2^63 is precedented in the Java library itself:
> Math.abs(int) and Math.abs(long) return the respective min values if the
> argument is that min value, so a similar design in the gcd methods would
> be more consistent with the Java API than throwing an exception.

This separates the result into three:

- representable signed integer
- representable unsigned integer (your new Integer.MIN_VALUE case)
- unknown result (exception)

If you change the current method, documented to never return a negative value, dependent downstream
code may break. Since this is unreleased code the downstream code can be assumed to be just
that in [numbers] so this may not be a major issue.

I can see the usefulness in this approach if the input int/long are treated as unsigned integers.
If treated as signed integers then to get the Integer.MIN_VALUE case for the GCD would require
at least one argument being Integer.MIN_VALUE. This is an extreme edge case. 

Is there merit in a duplicate method to handle unsigned integers:

ArithmeticUtils.gcdUnsigned(int, int)
ArithmeticUtils.gcdUnsigned(long, long)

However if this follows the JDK 8 unsigned method convention (Integer.toUnsignedString, Integer.divideUnsigned,
etc) the input would be assumed to already be unsigned bits. So if you are working with signed
integers you would have to call this using Math.abs() to convert twos compliment negative
values to unsigned:

int v1 = Integer.MIN_VALUE;
int v2 = Integer.MIN_VALUE;
// Greatest common divisor as unsigned 32-bit int
int gcd = ArithmeticUtils.gcdUnsigned(Math.abs(v1), Math.abs(v2));

This is more work than updating the current method, documented to only work in the range up
to 2^31-1, and I don’t have use cases to determine if an extra method is worth it.

So:

1. Make your changes and fix any dependent code in [numbers]
2. Add new unsigned methods and change any dependent code in [numbers] that care about this
edge case result

Note: I am not familiar with the GCD algorithm and have had a quick look to see if it can
be converted for unsigned. Given it seems to use Math.abs and Math.min on numbers that must
be positive signed integers I would say it would work with a bit of conversion to use custom
functions wrapping Integer.compareUnsigned(). The rest of the code just uses bit shifts and
integer subtraction which work the same for signed and unsigned numbers. (The bit shift would
have to be changed from >>= to >>>=).

Opinions?

> 
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> For additional commands, e-mail: dev-help@commons.apache.org
> 


---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org


Mime
View raw message