commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Heinrich Bohne <heinrich.bo...@gmx.at>
Subject Re: [numbers-core] Special cases in greatest common divisor methods
Date Sat, 20 Jul 2019 16:08:00 GMT
> This separates the result into three:
>
> - representable signed integer
> - representable unsigned integer (your new Integer.MIN_VALUE case)
> - unknown result (exception)

Maybe I misunderstood you, but with my suggested changes, the method
would never throw an exception, because the gcd of two (signed) ints can
never be greater than 2^31 (just like with the methods Math.abs(int) and
Math.abs(long)), and the case of 2^31 is the /only/ case where the
method currently throws an 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've already looked through the usages of the two gcd methods in
[numbers], and there are very few, and none of them rely on the method
throwing an exception if the gcd is the max value of the corresponding
data type (although one usage case could be simplified, which is the
example in the Fraction(int, int) constructor I mentioned).

As you yourself said, separate methods like gcdUnsigned, while
potentially useful, would provide a solution to a completely different
problem than the one I described, which is that the /arguments/ should
be treated as unsigned integers, not the result.


On 7/20/19 2:30 PM, Alex Herbert wrote:
>
>> 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
>
>


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


Mime
View raw message