You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@commons.apache.org by Phil Steitz <ph...@steitz.com> on 2003/08/10 23:48:54 UTC
[lang] Fraction.getFraction(double) uses magic numbers
o.a.c.l.math.Fraction includes a getFraction factory method that takes a
double and uses continued fractions to find a fractional approximation
of the input. The continued fraction implementation has a hard-coded
maximum number of iterations (25) and maximum denominator (1000). These
should be documented (and the ArithmeticException if maximum iterations
is reached before convergence). Better (IMHO) would be to add another
version that takes these as parameters, possibly even replacing the
current method (I think this is new in 2.0, so there would be no problem
with backward compatability).
If there are no objections, I will submit a patch that clarifies current
behavior and adds another method that takes maximum iterations and
maximum denominator as additional parameters.
I would also like to improve the implementation, but this can wait until
after 2.0.
Phil
Re: [lang] Fraction.getFraction(double) uses magic numbers
Posted by Phil Steitz <st...@yahoo.com>.
OK, but this should really be fixed "soon". We might want to consider
dropping this from 2.0 and adding a better version later. In any case, I
will submit a patch documenting current behavior.
One more thing that shows up in this method and elsewhere is poorly defined
behavior on integer overflows. Shouldn't we be checking for these and
throwing ArithmeticExceptions? If not, we should document (maybe at the
class level) that Integer arithmetic is being performed everywhere and
overflows will result in spurious values. My vote would be to add the
checks and throw ArithmeticExceptions on overflow. I will add this as a
separate patch.
Phil
--- Stephen Colebourne <sc...@btopenworld.com> wrote:
> Bear in mind that this came from a contributer. I don't know the maths of
> it!
>
> I added the 25 limit, to avoid infinite recursion. The test cases
> demostrate
> that the method returns the correct result for many, many cases. But I'm
> sure it could be improved. For 2.0 I would suggest documenting behaviour
> rather than adding a new method to control the value '25'.
>
> Stephen
>
>
> ----- Original Message -----
> From: "Phil Steitz" <ph...@steitz.com>
> To: "Jakarta Commons Developers List" <co...@jakarta.apache.org>
> Sent: Monday, August 11, 2003 4:24 AM
> Subject: Re: [lang] Fraction.getFraction(double) uses magic numbers
>
>
> > Brian S O'Neill wrote:
> > > I don't understand why the continued fraction implementation exists
> at
> all.
> > > Why not just get the bits from the double floating point number
> directly
> > > rather than introduce error? The floating point number is already a
> > > fraction, just encoded specially.
> >
> > The point as I see it is to get the best rational approximation of a
> > double value with bounded denominator. The continued fraction
> > decomposition will do this better and more efficiently than just
> > reducing the fraction implied by the decimal or binary representation
> of
> > the number. Consider, for example, the number 0.66666, to be
> > represented by a fraction with denominator <=10,000. The direct
> > approach using the decimal representation would give 6667/10000, which
> > is not as good as 2/3, which you would get by continued fractions.
> >
> > Phil
> >
> > >
> > > ----- Original Message -----
> > > From: "Phil Steitz" <ph...@steitz.com>
> > > To: "Jakarta Commons Developers List"
> <co...@jakarta.apache.org>
> > > Sent: Sunday, August 10, 2003 02:48 P
> > > Subject: [lang] Fraction.getFraction(double) uses magic numbers
> > >
> > >
> > >
> > >>o.a.c.l.math.Fraction includes a getFraction factory method that
> takes a
> > >>double and uses continued fractions to find a fractional
> approximation
> > >>of the input. The continued fraction implementation has a hard-coded
> > >>maximum number of iterations (25) and maximum denominator (1000).
> These
> > >>should be documented (and the ArithmeticException if maximum
> iterations
> > >>is reached before convergence). Better (IMHO) would be to add
> another
> > >>version that takes these as parameters, possibly even replacing the
> > >>current method (I think this is new in 2.0, so there would be no
> problem
> > >>with backward compatability).
> > >>
> > >>If there are no objections, I will submit a patch that clarifies
> current
> > >>behavior and adds another method that takes maximum iterations and
> > >>maximum denominator as additional parameters.
> > >>
> > >>I would also like to improve the implementation, but this can wait
> until
> > >>after 2.0.
> > >>
> > >>Phil
> > >>
> > >>
> > >>---------------------------------------------------------------------
> > >>To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
> > >>For additional commands, e-mail: commons-dev-help@jakarta.apache.org
> > >>
> > >
> > >
> > >
> > > ---------------------------------------------------------------------
> > > To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
> > > For additional commands, e-mail: commons-dev-help@jakarta.apache.org
> > >
> >
> >
> >
> >
> > ---------------------------------------------------------------------
> > To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
> > For additional commands, e-mail: commons-dev-help@jakarta.apache.org
> >
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
> For additional commands, e-mail: commons-dev-help@jakarta.apache.org
>
__________________________________
Do you Yahoo!?
Yahoo! SiteBuilder - Free, easy-to-use web site design software
http://sitebuilder.yahoo.com
---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org
Re: [lang] Fraction.getFraction(double) uses magic numbers
Posted by Phil Steitz <st...@yahoo.com>.
OK, but this should really be fixed "soon". We might want to consider
dropping this from 2.0 and adding a better version later. In any case, I
will submit a patch documenting current behavior.
One more thing that shows up in this method and elsewhere is poorly defined
behavior on integer overflows. Shouldn't we be checking for these and
throwing ArithmeticExceptions? If not, we should document (maybe at the
class level) that Integer arithmetic is being performed everywhere and
overflows will result in spurious values. My vote would be to add the
checks and throw ArithmeticExceptions on overflow. I will add this as a
separate patch.
Phil
--- Stephen Colebourne <sc...@btopenworld.com> wrote:
> Bear in mind that this came from a contributer. I don't know the maths of
> it!
>
> I added the 25 limit, to avoid infinite recursion. The test cases
> demostrate
> that the method returns the correct result for many, many cases. But I'm
> sure it could be improved. For 2.0 I would suggest documenting behaviour
> rather than adding a new method to control the value '25'.
>
> Stephen
>
>
> ----- Original Message -----
> From: "Phil Steitz" <ph...@steitz.com>
> To: "Jakarta Commons Developers List" <co...@jakarta.apache.org>
> Sent: Monday, August 11, 2003 4:24 AM
> Subject: Re: [lang] Fraction.getFraction(double) uses magic numbers
>
>
> > Brian S O'Neill wrote:
> > > I don't understand why the continued fraction implementation exists
> at
> all.
> > > Why not just get the bits from the double floating point number
> directly
> > > rather than introduce error? The floating point number is already a
> > > fraction, just encoded specially.
> >
> > The point as I see it is to get the best rational approximation of a
> > double value with bounded denominator. The continued fraction
> > decomposition will do this better and more efficiently than just
> > reducing the fraction implied by the decimal or binary representation
> of
> > the number. Consider, for example, the number 0.66666, to be
> > represented by a fraction with denominator <=10,000. The direct
> > approach using the decimal representation would give 6667/10000, which
> > is not as good as 2/3, which you would get by continued fractions.
> >
> > Phil
> >
> > >
> > > ----- Original Message -----
> > > From: "Phil Steitz" <ph...@steitz.com>
> > > To: "Jakarta Commons Developers List"
> <co...@jakarta.apache.org>
> > > Sent: Sunday, August 10, 2003 02:48 P
> > > Subject: [lang] Fraction.getFraction(double) uses magic numbers
> > >
> > >
> > >
> > >>o.a.c.l.math.Fraction includes a getFraction factory method that
> takes a
> > >>double and uses continued fractions to find a fractional
> approximation
> > >>of the input. The continued fraction implementation has a hard-coded
> > >>maximum number of iterations (25) and maximum denominator (1000).
> These
> > >>should be documented (and the ArithmeticException if maximum
> iterations
> > >>is reached before convergence). Better (IMHO) would be to add
> another
> > >>version that takes these as parameters, possibly even replacing the
> > >>current method (I think this is new in 2.0, so there would be no
> problem
> > >>with backward compatability).
> > >>
> > >>If there are no objections, I will submit a patch that clarifies
> current
> > >>behavior and adds another method that takes maximum iterations and
> > >>maximum denominator as additional parameters.
> > >>
> > >>I would also like to improve the implementation, but this can wait
> until
> > >>after 2.0.
> > >>
> > >>Phil
> > >>
> > >>
> > >>---------------------------------------------------------------------
> > >>To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
> > >>For additional commands, e-mail: commons-dev-help@jakarta.apache.org
> > >>
> > >
> > >
> > >
> > > ---------------------------------------------------------------------
> > > To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
> > > For additional commands, e-mail: commons-dev-help@jakarta.apache.org
> > >
> >
> >
> >
> >
> > ---------------------------------------------------------------------
> > To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
> > For additional commands, e-mail: commons-dev-help@jakarta.apache.org
> >
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
> For additional commands, e-mail: commons-dev-help@jakarta.apache.org
>
__________________________________
Do you Yahoo!?
Yahoo! SiteBuilder - Free, easy-to-use web site design software
http://sitebuilder.yahoo.com
Re: [lang] Fraction.getFraction(double) uses magic numbers
Posted by Stephen Colebourne <sc...@btopenworld.com>.
Bear in mind that this came from a contributer. I don't know the maths of
it!
I added the 25 limit, to avoid infinite recursion. The test cases demostrate
that the method returns the correct result for many, many cases. But I'm
sure it could be improved. For 2.0 I would suggest documenting behaviour
rather than adding a new method to control the value '25'.
Stephen
----- Original Message -----
From: "Phil Steitz" <ph...@steitz.com>
To: "Jakarta Commons Developers List" <co...@jakarta.apache.org>
Sent: Monday, August 11, 2003 4:24 AM
Subject: Re: [lang] Fraction.getFraction(double) uses magic numbers
> Brian S O'Neill wrote:
> > I don't understand why the continued fraction implementation exists at
all.
> > Why not just get the bits from the double floating point number directly
> > rather than introduce error? The floating point number is already a
> > fraction, just encoded specially.
>
> The point as I see it is to get the best rational approximation of a
> double value with bounded denominator. The continued fraction
> decomposition will do this better and more efficiently than just
> reducing the fraction implied by the decimal or binary representation of
> the number. Consider, for example, the number 0.66666, to be
> represented by a fraction with denominator <=10,000. The direct
> approach using the decimal representation would give 6667/10000, which
> is not as good as 2/3, which you would get by continued fractions.
>
> Phil
>
> >
> > ----- Original Message -----
> > From: "Phil Steitz" <ph...@steitz.com>
> > To: "Jakarta Commons Developers List" <co...@jakarta.apache.org>
> > Sent: Sunday, August 10, 2003 02:48 P
> > Subject: [lang] Fraction.getFraction(double) uses magic numbers
> >
> >
> >
> >>o.a.c.l.math.Fraction includes a getFraction factory method that takes a
> >>double and uses continued fractions to find a fractional approximation
> >>of the input. The continued fraction implementation has a hard-coded
> >>maximum number of iterations (25) and maximum denominator (1000). These
> >>should be documented (and the ArithmeticException if maximum iterations
> >>is reached before convergence). Better (IMHO) would be to add another
> >>version that takes these as parameters, possibly even replacing the
> >>current method (I think this is new in 2.0, so there would be no problem
> >>with backward compatability).
> >>
> >>If there are no objections, I will submit a patch that clarifies current
> >>behavior and adds another method that takes maximum iterations and
> >>maximum denominator as additional parameters.
> >>
> >>I would also like to improve the implementation, but this can wait until
> >>after 2.0.
> >>
> >>Phil
> >>
> >>
> >>---------------------------------------------------------------------
> >>To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
> >>For additional commands, e-mail: commons-dev-help@jakarta.apache.org
> >>
> >
> >
> >
> > ---------------------------------------------------------------------
> > To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
> > For additional commands, e-mail: commons-dev-help@jakarta.apache.org
> >
>
>
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
> For additional commands, e-mail: commons-dev-help@jakarta.apache.org
>
Re: [lang] Fraction.getFraction(double) uses magic numbers
Posted by Stephen Colebourne <sc...@btopenworld.com>.
Bear in mind that this came from a contributer. I don't know the maths of
it!
I added the 25 limit, to avoid infinite recursion. The test cases demostrate
that the method returns the correct result for many, many cases. But I'm
sure it could be improved. For 2.0 I would suggest documenting behaviour
rather than adding a new method to control the value '25'.
Stephen
----- Original Message -----
From: "Phil Steitz" <ph...@steitz.com>
To: "Jakarta Commons Developers List" <co...@jakarta.apache.org>
Sent: Monday, August 11, 2003 4:24 AM
Subject: Re: [lang] Fraction.getFraction(double) uses magic numbers
> Brian S O'Neill wrote:
> > I don't understand why the continued fraction implementation exists at
all.
> > Why not just get the bits from the double floating point number directly
> > rather than introduce error? The floating point number is already a
> > fraction, just encoded specially.
>
> The point as I see it is to get the best rational approximation of a
> double value with bounded denominator. The continued fraction
> decomposition will do this better and more efficiently than just
> reducing the fraction implied by the decimal or binary representation of
> the number. Consider, for example, the number 0.66666, to be
> represented by a fraction with denominator <=10,000. The direct
> approach using the decimal representation would give 6667/10000, which
> is not as good as 2/3, which you would get by continued fractions.
>
> Phil
>
> >
> > ----- Original Message -----
> > From: "Phil Steitz" <ph...@steitz.com>
> > To: "Jakarta Commons Developers List" <co...@jakarta.apache.org>
> > Sent: Sunday, August 10, 2003 02:48 P
> > Subject: [lang] Fraction.getFraction(double) uses magic numbers
> >
> >
> >
> >>o.a.c.l.math.Fraction includes a getFraction factory method that takes a
> >>double and uses continued fractions to find a fractional approximation
> >>of the input. The continued fraction implementation has a hard-coded
> >>maximum number of iterations (25) and maximum denominator (1000). These
> >>should be documented (and the ArithmeticException if maximum iterations
> >>is reached before convergence). Better (IMHO) would be to add another
> >>version that takes these as parameters, possibly even replacing the
> >>current method (I think this is new in 2.0, so there would be no problem
> >>with backward compatability).
> >>
> >>If there are no objections, I will submit a patch that clarifies current
> >>behavior and adds another method that takes maximum iterations and
> >>maximum denominator as additional parameters.
> >>
> >>I would also like to improve the implementation, but this can wait until
> >>after 2.0.
> >>
> >>Phil
> >>
> >>
> >>---------------------------------------------------------------------
> >>To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
> >>For additional commands, e-mail: commons-dev-help@jakarta.apache.org
> >>
> >
> >
> >
> > ---------------------------------------------------------------------
> > To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
> > For additional commands, e-mail: commons-dev-help@jakarta.apache.org
> >
>
>
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
> For additional commands, e-mail: commons-dev-help@jakarta.apache.org
>
---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org
Re: [lang] Fraction.getFraction(double) uses magic numbers
Posted by Phil Steitz <ph...@steitz.com>.
Brian S O'Neill wrote:
> I don't understand why the continued fraction implementation exists at all.
> Why not just get the bits from the double floating point number directly
> rather than introduce error? The floating point number is already a
> fraction, just encoded specially.
The point as I see it is to get the best rational approximation of a
double value with bounded denominator. The continued fraction
decomposition will do this better and more efficiently than just
reducing the fraction implied by the decimal or binary representation of
the number. Consider, for example, the number 0.66666, to be
represented by a fraction with denominator <=10,000. The direct
approach using the decimal representation would give 6667/10000, which
is not as good as 2/3, which you would get by continued fractions.
Phil
>
> ----- Original Message -----
> From: "Phil Steitz" <ph...@steitz.com>
> To: "Jakarta Commons Developers List" <co...@jakarta.apache.org>
> Sent: Sunday, August 10, 2003 02:48 P
> Subject: [lang] Fraction.getFraction(double) uses magic numbers
>
>
>
>>o.a.c.l.math.Fraction includes a getFraction factory method that takes a
>>double and uses continued fractions to find a fractional approximation
>>of the input. The continued fraction implementation has a hard-coded
>>maximum number of iterations (25) and maximum denominator (1000). These
>>should be documented (and the ArithmeticException if maximum iterations
>>is reached before convergence). Better (IMHO) would be to add another
>>version that takes these as parameters, possibly even replacing the
>>current method (I think this is new in 2.0, so there would be no problem
>>with backward compatability).
>>
>>If there are no objections, I will submit a patch that clarifies current
>>behavior and adds another method that takes maximum iterations and
>>maximum denominator as additional parameters.
>>
>>I would also like to improve the implementation, but this can wait until
>>after 2.0.
>>
>>Phil
>>
>>
>>---------------------------------------------------------------------
>>To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
>>For additional commands, e-mail: commons-dev-help@jakarta.apache.org
>>
>
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
> For additional commands, e-mail: commons-dev-help@jakarta.apache.org
>
Re: [lang] Fraction.getFraction(double) uses magic numbers
Posted by Phil Steitz <ph...@steitz.com>.
Brian S O'Neill wrote:
> I don't understand why the continued fraction implementation exists at all.
> Why not just get the bits from the double floating point number directly
> rather than introduce error? The floating point number is already a
> fraction, just encoded specially.
The point as I see it is to get the best rational approximation of a
double value with bounded denominator. The continued fraction
decomposition will do this better and more efficiently than just
reducing the fraction implied by the decimal or binary representation of
the number. Consider, for example, the number 0.66666, to be
represented by a fraction with denominator <=10,000. The direct
approach using the decimal representation would give 6667/10000, which
is not as good as 2/3, which you would get by continued fractions.
Phil
>
> ----- Original Message -----
> From: "Phil Steitz" <ph...@steitz.com>
> To: "Jakarta Commons Developers List" <co...@jakarta.apache.org>
> Sent: Sunday, August 10, 2003 02:48 P
> Subject: [lang] Fraction.getFraction(double) uses magic numbers
>
>
>
>>o.a.c.l.math.Fraction includes a getFraction factory method that takes a
>>double and uses continued fractions to find a fractional approximation
>>of the input. The continued fraction implementation has a hard-coded
>>maximum number of iterations (25) and maximum denominator (1000). These
>>should be documented (and the ArithmeticException if maximum iterations
>>is reached before convergence). Better (IMHO) would be to add another
>>version that takes these as parameters, possibly even replacing the
>>current method (I think this is new in 2.0, so there would be no problem
>>with backward compatability).
>>
>>If there are no objections, I will submit a patch that clarifies current
>>behavior and adds another method that takes maximum iterations and
>>maximum denominator as additional parameters.
>>
>>I would also like to improve the implementation, but this can wait until
>>after 2.0.
>>
>>Phil
>>
>>
>>---------------------------------------------------------------------
>>To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
>>For additional commands, e-mail: commons-dev-help@jakarta.apache.org
>>
>
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
> For additional commands, e-mail: commons-dev-help@jakarta.apache.org
>
---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org
Re: [lang] Fraction.getFraction(double) uses magic numbers
Posted by Brian S O'Neill <br...@earthlink.net>.
I don't understand why the continued fraction implementation exists at all.
Why not just get the bits from the double floating point number directly
rather than introduce error? The floating point number is already a
fraction, just encoded specially.
----- Original Message -----
From: "Phil Steitz" <ph...@steitz.com>
To: "Jakarta Commons Developers List" <co...@jakarta.apache.org>
Sent: Sunday, August 10, 2003 02:48 P
Subject: [lang] Fraction.getFraction(double) uses magic numbers
> o.a.c.l.math.Fraction includes a getFraction factory method that takes a
> double and uses continued fractions to find a fractional approximation
> of the input. The continued fraction implementation has a hard-coded
> maximum number of iterations (25) and maximum denominator (1000). These
> should be documented (and the ArithmeticException if maximum iterations
> is reached before convergence). Better (IMHO) would be to add another
> version that takes these as parameters, possibly even replacing the
> current method (I think this is new in 2.0, so there would be no problem
> with backward compatability).
>
> If there are no objections, I will submit a patch that clarifies current
> behavior and adds another method that takes maximum iterations and
> maximum denominator as additional parameters.
>
> I would also like to improve the implementation, but this can wait until
> after 2.0.
>
> Phil
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
> For additional commands, e-mail: commons-dev-help@jakarta.apache.org
>
Re: [lang] Fraction.getFraction(double) uses magic numbers
Posted by Brian S O'Neill <br...@earthlink.net>.
I don't understand why the continued fraction implementation exists at all.
Why not just get the bits from the double floating point number directly
rather than introduce error? The floating point number is already a
fraction, just encoded specially.
----- Original Message -----
From: "Phil Steitz" <ph...@steitz.com>
To: "Jakarta Commons Developers List" <co...@jakarta.apache.org>
Sent: Sunday, August 10, 2003 02:48 P
Subject: [lang] Fraction.getFraction(double) uses magic numbers
> o.a.c.l.math.Fraction includes a getFraction factory method that takes a
> double and uses continued fractions to find a fractional approximation
> of the input. The continued fraction implementation has a hard-coded
> maximum number of iterations (25) and maximum denominator (1000). These
> should be documented (and the ArithmeticException if maximum iterations
> is reached before convergence). Better (IMHO) would be to add another
> version that takes these as parameters, possibly even replacing the
> current method (I think this is new in 2.0, so there would be no problem
> with backward compatability).
>
> If there are no objections, I will submit a patch that clarifies current
> behavior and adds another method that takes maximum iterations and
> maximum denominator as additional parameters.
>
> I would also like to improve the implementation, but this can wait until
> after 2.0.
>
> Phil
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
> For additional commands, e-mail: commons-dev-help@jakarta.apache.org
>
---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org