You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@commons.apache.org by Alex Herbert <al...@gmail.com> on 2020/04/07 12:43:50 UTC
Re: [numbers] Continued Fraction + Fraction updates
Continued Fraction
I've updated ContinuedFraction to use numerator a over denominator b.
This is consistent with the original source paper for the method.
Fraction
While looking at the fraction package it was very hard to compare
Fraction and BigFraction side-by-side. This is a problem as the two are
essentially the same using a different internal representation.
I also did a big arrangement of Fraction and BigFraction. The two had
diverged quite a bit in their internal method order and the javadoc. I
have updated them to be consistent. They should be easily compared
side-by-side and this will reduce maintenance burden when they are
updated together.
I copied the method order from Complex with changes as appropriate:
private constructors
factory constructors, including parse(String)
Properties:
zero(), one()
numerator(), denominator()
Computed properties:
signum
Conversions:
abs, negate, reciprocal
primitive values (double/float/int/longValue,etc)
Math:
Arithmetic
add,subtract,multiply,divide
Power functions
Standard object stuff:
toString(), compareTo, equals(), hashCode()
I spotted a bug in the Fraction.of(double, ...) constructors where there
was no validation of NaN or infinity so I have added this to Fraction
and BigFraction to throw an IllegalArgumentException.
Alex
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [numbers] Continued Fraction + Fraction updates
Posted by Gilles Sadowski <gi...@gmail.com>.
Le mer. 8 avr. 2020 à 15:58, Alex Herbert <al...@gmail.com> a écrit :
>
>
> On 08/04/2020 14:08, Gilles Sadowski wrote:
> > Le mer. 8 avr. 2020 à 14:26, Alex Herbert <al...@gmail.com> a écrit :
> >>
> >> On 08/04/2020 00:36, Gilles Sadowski wrote:
> >>> 2020-04-07 23:01 UTC+02:00, Alex Herbert <al...@gmail.com>:
> >>>>> On 7 Apr 2020, at 17:47, Gilles Sadowski <gi...@gmail.com> wrote:
> >>>>>
> >>>>> Le mar. 7 avr. 2020 à 14:54, Alex Herbert <alex.d.herbert@gmail.com
> >>>>> <ma...@gmail.com>> a écrit :
> >>>>>> On 07/04/2020 13:43, Alex Herbert wrote:
> >>>>>>> Fraction
> >>>>>>>
> >>>>>>> I also did a big arrangement of Fraction and BigFraction.
> >>>>> Thanks.
> >>>>>
> >>>>>> I noticed that hashCode is using some variant of the format used in
> >>>>>> Arrays.hashCode(...)
> >>>>>>
> >>>>>> I wondered if we should standardise on returning a value as if computed
> >>>>>> using e.g. Arrays.hashCode(new int[]{numerator, denominator}) as was
> >>>>>> done for Complex with its two parts.
> >>>>>>
> >>>>>> This would change in Fraction:
> >>>>>>
> >>>>>> public int hashCode() {
> >>>>>> return 37 * (37 * 17 + numerator) + denominator;
> >>>>>> }
> >>>>> Strange that the constant 37 * 17 was not pre-computed. ;-)
> >>>> Yes. Weird. It was like that in CM 3.6.1.
> >>>>
> >>>> Not knowing if one is better than the other
> >>> The "17" seems to come from "Effective Java" (where J. Bloch says
> >>> that it is arbitrary apart from being nonzero, so "1" is fine too I guess).
> >>>
> >>>> (do you just pick a small prime
> >>>> for the factor?) I’d just shift it to use the same method as Arrays.hashCode
> >>>> for consistency with Complex.
> >>> Fine.
> >>> The factor is indeed "31" in Effective Java, saying that it must be
> >>> odd, and that a prime is a traditional choice.
> >> hashCode was actually broken so it needed an update.
> >>
> >> These
> >>
> >> -1 / 3
> >>
> >> 1 / -3
> >>
> >> did not have the same hashCode even though they are equal. This violates
> >> the Object.hashCode contract.
> > Oops.
> > I overlooked that when we decided to allow both internal representations.
> >
> >> There were two options:
> >>
> >> 1. Create the hashCode using: |numerator|, |denominator|
> >>
> >> 2. Create the hashCode using: signum, |numerator|, |denominator|
> >>
> >> I went for option 2. Thus 1/3 and -1/3 have different hash codes.
> >>
> >> The hash code computation currently matches (for Fraction f):
> >>
> >> Arrays.hashCode(new int[] {f.signum(),
> >> Math.abs(f.getNumerator()),
> >> Math.abs(f.getDenominator())});
> >>
> >> The computation is done inline without delegating to Arrays.
> > I'd rather keep it simple and delegate to the JDK method above.
>
> I've documented the method to state what it is doing.
>
> Avoiding Arrays.hashCode will be faster due to lack of array
> instantiation and then boundary checking on the array during
> computation. In the case of BigFraction the method also avoids having to
> compute the abs() of the numerator and denominator.
>
> If you ever did need to have a hashCode then it is nicer to have a
> faster method.
Of course, but I can't come up with a use-case for "Set<Fraction>"
which you mentioned below.
If the rationale is "We do <...> every time we need to define a hashCode".
Then +1 to keep doing <...>.
> It you argue for Arrays.hashCode(Object[]) then you could also argue for
> Arrays.equals(Object[], Object[]) in the equals method using the sign,
> and absolute numerator and denominator. I think it better leave it
> functionally the same but implement the method explicitly to take
> advantage of knowing the internal object representation.
I'd assume that it's always the case. Then IIUC, the JDK methods
only exists for computing reference values in unit tests...
> I stopped short of adding this implementation detail to the javadoc for
> Fraction. However in Complex we mandated in the javadoc that equals and
> hashCode are equivalent to using Arrays.equals/hashCode with the two
> parts of the complex number.
>
> > Indeed, is there any reasonable use-case for using a fraction
> > as hash map key?
> > If not, IMO, better make the code self-documenting.
>
> Storage in a Set<Fraction> for unique values?
Not use-case, just an example.
Anyways, not strong arguments here; and absence of actual
usage would make it a total waste of time to set up benchmarks.
Do what you think is fine.
Best,
Gilles
> >> It could be changed to:
> >>
> >> f.signum() * Arrays.hashCode(new int[] {Math.abs(f.getNumerator()),
> >> Math.abs(f.getDenominator())});
> > -0
> > Same rationale as above.
> >
> >> The later would remove a single integer addition operation from the
> >> computation so probably no speed difference.
> > Zero difference if "hashCode()" is never called. ;-)
> >
> > Gilles
> >
> >> Any opinions on this? Given the signum is a 3-state flag it may be
> >> better moved outside the computation. This would mean that a fraction
> >> with the value 0 has the hashCode 0.
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [numbers] Continued Fraction + Fraction updates
Posted by Alex Herbert <al...@gmail.com>.
On 08/04/2020 14:08, Gilles Sadowski wrote:
> Le mer. 8 avr. 2020 à 14:26, Alex Herbert <al...@gmail.com> a écrit :
>>
>> On 08/04/2020 00:36, Gilles Sadowski wrote:
>>> 2020-04-07 23:01 UTC+02:00, Alex Herbert <al...@gmail.com>:
>>>>> On 7 Apr 2020, at 17:47, Gilles Sadowski <gi...@gmail.com> wrote:
>>>>>
>>>>> Le mar. 7 avr. 2020 à 14:54, Alex Herbert <alex.d.herbert@gmail.com
>>>>> <ma...@gmail.com>> a écrit :
>>>>>> On 07/04/2020 13:43, Alex Herbert wrote:
>>>>>>> Fraction
>>>>>>>
>>>>>>> I also did a big arrangement of Fraction and BigFraction.
>>>>> Thanks.
>>>>>
>>>>>> I noticed that hashCode is using some variant of the format used in
>>>>>> Arrays.hashCode(...)
>>>>>>
>>>>>> I wondered if we should standardise on returning a value as if computed
>>>>>> using e.g. Arrays.hashCode(new int[]{numerator, denominator}) as was
>>>>>> done for Complex with its two parts.
>>>>>>
>>>>>> This would change in Fraction:
>>>>>>
>>>>>> public int hashCode() {
>>>>>> return 37 * (37 * 17 + numerator) + denominator;
>>>>>> }
>>>>> Strange that the constant 37 * 17 was not pre-computed. ;-)
>>>> Yes. Weird. It was like that in CM 3.6.1.
>>>>
>>>> Not knowing if one is better than the other
>>> The "17" seems to come from "Effective Java" (where J. Bloch says
>>> that it is arbitrary apart from being nonzero, so "1" is fine too I guess).
>>>
>>>> (do you just pick a small prime
>>>> for the factor?) I’d just shift it to use the same method as Arrays.hashCode
>>>> for consistency with Complex.
>>> Fine.
>>> The factor is indeed "31" in Effective Java, saying that it must be
>>> odd, and that a prime is a traditional choice.
>> hashCode was actually broken so it needed an update.
>>
>> These
>>
>> -1 / 3
>>
>> 1 / -3
>>
>> did not have the same hashCode even though they are equal. This violates
>> the Object.hashCode contract.
> Oops.
> I overlooked that when we decided to allow both internal representations.
>
>> There were two options:
>>
>> 1. Create the hashCode using: |numerator|, |denominator|
>>
>> 2. Create the hashCode using: signum, |numerator|, |denominator|
>>
>> I went for option 2. Thus 1/3 and -1/3 have different hash codes.
>>
>> The hash code computation currently matches (for Fraction f):
>>
>> Arrays.hashCode(new int[] {f.signum(),
>> Math.abs(f.getNumerator()),
>> Math.abs(f.getDenominator())});
>>
>> The computation is done inline without delegating to Arrays.
> I'd rather keep it simple and delegate to the JDK method above.
I've documented the method to state what it is doing.
Avoiding Arrays.hashCode will be faster due to lack of array
instantiation and then boundary checking on the array during
computation. In the case of BigFraction the method also avoids having to
compute the abs() of the numerator and denominator.
If you ever did need to have a hashCode then it is nicer to have a
faster method.
It you argue for Arrays.hashCode(Object[]) then you could also argue for
Arrays.equals(Object[], Object[]) in the equals method using the sign,
and absolute numerator and denominator. I think it better leave it
functionally the same but implement the method explicitly to take
advantage of knowing the internal object representation.
I stopped short of adding this implementation detail to the javadoc for
Fraction. However in Complex we mandated in the javadoc that equals and
hashCode are equivalent to using Arrays.equals/hashCode with the two
parts of the complex number.
> Indeed, is there any reasonable use-case for using a fraction
> as hash map key?
> If not, IMO, better make the code self-documenting.
Storage in a Set<Fraction> for unique values?
>
>> It could be changed to:
>>
>> f.signum() * Arrays.hashCode(new int[] {Math.abs(f.getNumerator()),
>> Math.abs(f.getDenominator())});
> -0
> Same rationale as above.
>
>> The later would remove a single integer addition operation from the
>> computation so probably no speed difference.
> Zero difference if "hashCode()" is never called. ;-)
>
> Gilles
>
>> Any opinions on this? Given the signum is a 3-state flag it may be
>> better moved outside the computation. This would mean that a fraction
>> with the value 0 has the hashCode 0.
> ---------------------------------------------------------------------
> 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
Re: [numbers] Continued Fraction + Fraction updates
Posted by Gilles Sadowski <gi...@gmail.com>.
Le mer. 8 avr. 2020 à 14:26, Alex Herbert <al...@gmail.com> a écrit :
>
>
> On 08/04/2020 00:36, Gilles Sadowski wrote:
> > 2020-04-07 23:01 UTC+02:00, Alex Herbert <al...@gmail.com>:
> >>
> >>> On 7 Apr 2020, at 17:47, Gilles Sadowski <gi...@gmail.com> wrote:
> >>>
> >>> Le mar. 7 avr. 2020 à 14:54, Alex Herbert <alex.d.herbert@gmail.com
> >>> <ma...@gmail.com>> a écrit :
> >>>> On 07/04/2020 13:43, Alex Herbert wrote:
> >>>>> Fraction
> >>>>>
> >>>>> I also did a big arrangement of Fraction and BigFraction.
> >>> Thanks.
> >>>
> >>>> I noticed that hashCode is using some variant of the format used in
> >>>> Arrays.hashCode(...)
> >>>>
> >>>> I wondered if we should standardise on returning a value as if computed
> >>>> using e.g. Arrays.hashCode(new int[]{numerator, denominator}) as was
> >>>> done for Complex with its two parts.
> >>>>
> >>>> This would change in Fraction:
> >>>>
> >>>> public int hashCode() {
> >>>> return 37 * (37 * 17 + numerator) + denominator;
> >>>> }
> >>> Strange that the constant 37 * 17 was not pre-computed. ;-)
> >> Yes. Weird. It was like that in CM 3.6.1.
> >>
> >> Not knowing if one is better than the other
> > The "17" seems to come from "Effective Java" (where J. Bloch says
> > that it is arbitrary apart from being nonzero, so "1" is fine too I guess).
> >
> >> (do you just pick a small prime
> >> for the factor?) I’d just shift it to use the same method as Arrays.hashCode
> >> for consistency with Complex.
> > Fine.
> > The factor is indeed "31" in Effective Java, saying that it must be
> > odd, and that a prime is a traditional choice.
>
> hashCode was actually broken so it needed an update.
>
> These
>
> -1 / 3
>
> 1 / -3
>
> did not have the same hashCode even though they are equal. This violates
> the Object.hashCode contract.
Oops.
I overlooked that when we decided to allow both internal representations.
>
> There were two options:
>
> 1. Create the hashCode using: |numerator|, |denominator|
>
> 2. Create the hashCode using: signum, |numerator|, |denominator|
>
> I went for option 2. Thus 1/3 and -1/3 have different hash codes.
>
> The hash code computation currently matches (for Fraction f):
>
> Arrays.hashCode(new int[] {f.signum(),
> Math.abs(f.getNumerator()),
> Math.abs(f.getDenominator())});
>
> The computation is done inline without delegating to Arrays.
I'd rather keep it simple and delegate to the JDK method above.
Indeed, is there any reasonable use-case for using a fraction
as hash map key?
If not, IMO, better make the code self-documenting.
> It could be changed to:
>
> f.signum() * Arrays.hashCode(new int[] {Math.abs(f.getNumerator()),
> Math.abs(f.getDenominator())});
-0
Same rationale as above.
> The later would remove a single integer addition operation from the
> computation so probably no speed difference.
Zero difference if "hashCode()" is never called. ;-)
Gilles
> Any opinions on this? Given the signum is a 3-state flag it may be
> better moved outside the computation. This would mean that a fraction
> with the value 0 has the hashCode 0.
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [numbers] Continued Fraction + Fraction updates
Posted by Alex Herbert <al...@gmail.com>.
On 08/04/2020 00:36, Gilles Sadowski wrote:
> 2020-04-07 23:01 UTC+02:00, Alex Herbert <al...@gmail.com>:
>>
>>> On 7 Apr 2020, at 17:47, Gilles Sadowski <gi...@gmail.com> wrote:
>>>
>>> Le mar. 7 avr. 2020 à 14:54, Alex Herbert <alex.d.herbert@gmail.com
>>> <ma...@gmail.com>> a écrit :
>>>> On 07/04/2020 13:43, Alex Herbert wrote:
>>>>> Fraction
>>>>>
>>>>> I also did a big arrangement of Fraction and BigFraction.
>>> Thanks.
>>>
>>>> I noticed that hashCode is using some variant of the format used in
>>>> Arrays.hashCode(...)
>>>>
>>>> I wondered if we should standardise on returning a value as if computed
>>>> using e.g. Arrays.hashCode(new int[]{numerator, denominator}) as was
>>>> done for Complex with its two parts.
>>>>
>>>> This would change in Fraction:
>>>>
>>>> public int hashCode() {
>>>> return 37 * (37 * 17 + numerator) + denominator;
>>>> }
>>> Strange that the constant 37 * 17 was not pre-computed. ;-)
>> Yes. Weird. It was like that in CM 3.6.1.
>>
>> Not knowing if one is better than the other
> The "17" seems to come from "Effective Java" (where J. Bloch says
> that it is arbitrary apart from being nonzero, so "1" is fine too I guess).
>
>> (do you just pick a small prime
>> for the factor?) I’d just shift it to use the same method as Arrays.hashCode
>> for consistency with Complex.
> Fine.
> The factor is indeed "31" in Effective Java, saying that it must be
> odd, and that a prime is a traditional choice.
hashCode was actually broken so it needed an update.
These
-1 / 3
1 / -3
did not have the same hashCode even though they are equal. This violates
the Object.hashCode contract.
There were two options:
1. Create the hashCode using: |numerator|, |denominator|
2. Create the hashCode using: signum, |numerator|, |denominator|
I went for option 2. Thus 1/3 and -1/3 have different hash codes.
The hash code computation currently matches (for Fraction f):
Arrays.hashCode(new int[] {f.signum(),
Math.abs(f.getNumerator()),
Math.abs(f.getDenominator())});
The computation is done inline without delegating to Arrays.
It could be changed to:
f.signum() * Arrays.hashCode(new int[] {Math.abs(f.getNumerator()),
Math.abs(f.getDenominator())});
The later would remove a single integer addition operation from the
computation so probably no speed difference.
Any opinions on this? Given the signum is a 3-state flag it may be
better moved outside the computation. This would mean that a fraction
with the value 0 has the hashCode 0.
Alex
>
> Gilles
>
> ---------------------------------------------------------------------
> 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
Re: [numbers] Continued Fraction + Fraction updates
Posted by Gilles Sadowski <gi...@gmail.com>.
2020-04-07 23:01 UTC+02:00, Alex Herbert <al...@gmail.com>:
>
>
>> On 7 Apr 2020, at 17:47, Gilles Sadowski <gi...@gmail.com> wrote:
>>
>> Le mar. 7 avr. 2020 à 14:54, Alex Herbert <alex.d.herbert@gmail.com
>> <ma...@gmail.com>> a écrit :
>>>
>>> On 07/04/2020 13:43, Alex Herbert wrote:
>>>>
>>>> Fraction
>>>>
>>>> I also did a big arrangement of Fraction and BigFraction.
>>
>> Thanks.
>>
>>>
>>> I noticed that hashCode is using some variant of the format used in
>>> Arrays.hashCode(...)
>>>
>>> I wondered if we should standardise on returning a value as if computed
>>> using e.g. Arrays.hashCode(new int[]{numerator, denominator}) as was
>>> done for Complex with its two parts.
>>>
>>> This would change in Fraction:
>>>
>>> public int hashCode() {
>>> return 37 * (37 * 17 + numerator) + denominator;
>>> }
>>
>> Strange that the constant 37 * 17 was not pre-computed. ;-)
>
> Yes. Weird. It was like that in CM 3.6.1.
>
> Not knowing if one is better than the other
The "17" seems to come from "Effective Java" (where J. Bloch says
that it is arbitrary apart from being nonzero, so "1" is fine too I guess).
> (do you just pick a small prime
> for the factor?) I’d just shift it to use the same method as Arrays.hashCode
> for consistency with Complex.
Fine.
The factor is indeed "31" in Effective Java, saying that it must be
odd, and that a prime is a traditional choice.
Gilles
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [numbers] Continued Fraction + Fraction updates
Posted by Alex Herbert <al...@gmail.com>.
> On 7 Apr 2020, at 17:47, Gilles Sadowski <gi...@gmail.com> wrote:
>
> Le mar. 7 avr. 2020 à 14:54, Alex Herbert <alex.d.herbert@gmail.com <ma...@gmail.com>> a écrit :
>>
>> On 07/04/2020 13:43, Alex Herbert wrote:
>>>
>>> Fraction
>>>
>>> I also did a big arrangement of Fraction and BigFraction.
>
> Thanks.
>
>>
>> I noticed that hashCode is using some variant of the format used in
>> Arrays.hashCode(...)
>>
>> I wondered if we should standardise on returning a value as if computed
>> using e.g. Arrays.hashCode(new int[]{numerator, denominator}) as was
>> done for Complex with its two parts.
>>
>> This would change in Fraction:
>>
>> public int hashCode() {
>> return 37 * (37 * 17 + numerator) + denominator;
>> }
>
> Strange that the constant 37 * 17 was not pre-computed. ;-)
Yes. Weird. It was like that in CM 3.6.1.
Not knowing if one is better than the other (do you just pick a small prime for the factor?) I’d just shift it to use the same method as Arrays.hashCode for consistency with Complex.
>
>>
>> to
>>
>> public int hashCode() {
>> return 31 * (31 + numerator) + denominator;
>> }
>
> +0
>
> Gilles
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org <ma...@commons.apache.org>
> For additional commands, e-mail: dev-help@commons.apache.org <ma...@commons.apache.org>
Re: [numbers] Continued Fraction + Fraction updates
Posted by Gilles Sadowski <gi...@gmail.com>.
Le mar. 7 avr. 2020 à 14:54, Alex Herbert <al...@gmail.com> a écrit :
>
> On 07/04/2020 13:43, Alex Herbert wrote:
> >
> > Fraction
> >
> > I also did a big arrangement of Fraction and BigFraction.
Thanks.
>
> I noticed that hashCode is using some variant of the format used in
> Arrays.hashCode(...)
>
> I wondered if we should standardise on returning a value as if computed
> using e.g. Arrays.hashCode(new int[]{numerator, denominator}) as was
> done for Complex with its two parts.
>
> This would change in Fraction:
>
> public int hashCode() {
> return 37 * (37 * 17 + numerator) + denominator;
> }
Strange that the constant 37 * 17 was not pre-computed. ;-)
>
> to
>
> public int hashCode() {
> return 31 * (31 + numerator) + denominator;
> }
+0
Gilles
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [numbers] Continued Fraction + Fraction updates
Posted by Alex Herbert <al...@gmail.com>.
On 07/04/2020 13:43, Alex Herbert wrote:
>
> Fraction
>
> I also did a big arrangement of Fraction and BigFraction.
I noticed that hashCode is using some variant of the format used in
Arrays.hashCode(...)
I wondered if we should standardise on returning a value as if computed
using e.g. Arrays.hashCode(new int[]{numerator, denominator}) as was
done for Complex with its two parts.
This would change in Fraction:
public int hashCode() {
return 37 * (37 * 17 + numerator) + denominator;
}
to
public int hashCode() {
return 31 * (31 + numerator) + denominator;
}
Alex
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org