Commons Lang
  1. Commons Lang
  2. LANG-168

[lang][PATCH] lang.math.Fraction class deficiencies

    Details

    • Type: Improvement Improvement
    • Status: Closed
    • Priority: Minor Minor
    • Resolution: Fixed
    • Affects Version/s: 2.0
    • Fix Version/s: 2.1
    • Component/s: None
    • Labels:
      None
    • Environment:

      Operating System: Linux
      Platform: PC

      Description

      The attached patch addresses several deficiencies in the Fraction class:
      a) 'reduction' should never be necessary. The fraction is stored as a pair of
      relatively prime integers (i.e. always in simplified form). The reduce() and
      getReducedFraction() methods have been deprecated and are now a no-op, and
      identical to getFraction(), respectively. The static field TWO_QUARTERS is also
      deprecated; it is now identical to the field ONE_HALF.
      b) this also fixes the API oddity where currently a.compareTo(b)==0 does not
      imply that a.equals(b). Once fractions are simplified, equals() corresponds
      correctly to numerical equality.
      c) the hashCode() method currently has a race condition if used in
      multithreaded code: two threads accessing a hashcode which has not yet been
      hashed may obtain different values returned from hashCode().
      d) the gcd algorithm used in fraction has been changed to use a more efficient
      'binary' algorithm which does not require division.
      e) all code has been reviewed so that values at the edges of the range of
      integers (ie Integer.MIN_VALUE and Integer.MAX_VALUE) are handled correctly.
      Note that Integer.MIN_VALUE cannot be negated, so this entails typically
      maintaining values as negative numbers when magnitudes are required. [See for
      example the patch to Fraction.toProperString()]
      f) the current pow() algorithm suffers from numerical inaccuracies due to
      casting between double and int. It has been replaced by a double-and-multiply
      method which guarantees accuracy. The new pow algorithm supports negative
      powers as well (up to an including Integer.MIN_VALUE)
      g) A 'resolveObject' method has been added to maintain backwards-compatibility
      with existing serialized Fractions. These are now simplified on deserialization.
      h) The addition and multiplication algorithms used have been updated to conform
      to those described in Knuth's "The Art of Computer Programming" section 4.5.
      This also means they will operate with larger fractions before overflowing.
      i) All overflow conditions ought to throw an ArithmeticException. This was not
      the case in the existing code (some overflows silently corrupted the result).
      j) The JUnit tests for this class have been extended to test and verify all of
      the above. Clover now indicates very few uncovered lines of code, most of which
      are legitimately unreachable. Checkstyle emits no warnings. The javadoc for
      all methods has been extended and corrected.

      1. ASF.LICENSE.NOT.GRANTED--fractionPatch
        45 kB
        Phil Steitz
      2. ASF.LICENSE.NOT.GRANTED--lang-fraction.patch
        53 kB
        C. Scott Ananian
      3. ASF.LICENSE.NOT.GRANTED--lang-fraction-2.patch
        57 kB
        C. Scott Ananian
      4. ASF.LICENSE.NOT.GRANTED--lang-fraction-3.patch
        130 kB
        C. Scott Ananian
      5. ASF.LICENSE.NOT.GRANTED--lang-fraction-4.patch
        186 kB
        C. Scott Ananian
      6. ASF.LICENSE.NOT.GRANTED--lang-fraction-5.patch
        186 kB
        C. Scott Ananian
      7. ASF.LICENSE.NOT.GRANTED--lang-fraction-7x.patch
        15 kB
        C. Scott Ananian
      8. ASF.LICENSE.NOT.GRANTED--lang-fraction-8x.patch
        1 kB
        C. Scott Ananian

        Activity

        Hide
        Henri Yandell added a comment -

        Reopening then closing to deal with migration bug.

        Show
        Henri Yandell added a comment - Reopening then closing to deal with migration bug.
        Hide
        Henri Yandell added a comment -

        Reopening then closing to deal with migration bug.

        Show
        Henri Yandell added a comment - Reopening then closing to deal with migration bug.
        Hide
        Henri Yandell added a comment -

        2.1 released, closing.

        Show
        Henri Yandell added a comment - 2.1 released, closing.
        Hide
        Phil Steitz added a comment -

        Numeric fixes committed.

        Show
        Phil Steitz added a comment - Numeric fixes committed.
        Hide
        Phil Steitz added a comment -

        I need to lay hands on Knuth to review copyright notice and add a couple more
        test cases before committing. Will commit (assuming all is well) this weekend at
        the latest.

        Show
        Phil Steitz added a comment - I need to lay hands on Knuth to review copyright notice and add a couple more test cases before committing. Will commit (assuming all is well) this weekend at the latest.
        Hide
        Stephen Colebourne added a comment -

        Phil, can you apply the patch and lets take it from there. I am -1 on
        deprecating the class until a math release is out, so could you leave it
        undeprecated ATM.

        Show
        Stephen Colebourne added a comment - Phil, can you apply the patch and lets take it from there. I am -1 on deprecating the class until a math release is out, so could you leave it undeprecated ATM.
        Hide
        C. Scott Ananian added a comment -

        I should clarify my last comment: I put a decent amount of work into
        retrofitting my changes to Fraction to make them compatible with the old
        "broken" interfaces. I think that deprecating Fraction in commons-lang is a good
        idea, and it's good that a nice clean API will make it to commons-math (one
        hopes), but it's not entirely clear to me why my original patch couldn't be
        taken as is. I thought the whole point of having comprehensive test-suites was
        to allow large-ish source code changes while maintaining assurance that
        compatibility was preserved (which it was). I spent a lot of effort extending
        the test suite for Fraction to document this fact.

        Show
        C. Scott Ananian added a comment - I should clarify my last comment: I put a decent amount of work into retrofitting my changes to Fraction to make them compatible with the old "broken" interfaces. I think that deprecating Fraction in commons-lang is a good idea, and it's good that a nice clean API will make it to commons-math (one hopes), but it's not entirely clear to me why my original patch couldn't be taken as is. I thought the whole point of having comprehensive test-suites was to allow large-ish source code changes while maintaining assurance that compatibility was preserved (which it was). I spent a lot of effort extending the test suite for Fraction to document this fact.
        Hide
        C. Scott Ananian added a comment -

        You should be able to use the patch to FractionTest unmodified, then. Do you?
        [FractionTest used only the 'old' interface and FractionTest2 used only the
        'new' interface.]

        I'm disappointed that the "actually useful" version of Fraction is not going to
        make it into commons. I put a lot of work into this.

        Show
        C. Scott Ananian added a comment - You should be able to use the patch to FractionTest unmodified, then. Do you? [FractionTest used only the 'old' interface and FractionTest2 used only the 'new' interface.] I'm disappointed that the "actually useful" version of Fraction is not going to make it into commons. I put a lot of work into this.
        Hide
        Phil Steitz added a comment -

        Response to Scott's comment above:

        The "Consolidated bug fixes" patch does not add methods (e.g valueOf) or
        classes (e.g BigFraction, BadFraction). The improvements in valueOf are, as
        much as possible, incorporated into the existing Fraction class methods. No
        individual methods are deprecated, either. Assuming others are OK with this
        approach, I will add a deprecation notice to the whole class in the class
        header (indicating move to [math]). We should then open a separate ticket to
        [math] including the new class (BigFraction, maybe renamed "RationalNumber").

        Show
        Phil Steitz added a comment - Response to Scott's comment above: The "Consolidated bug fixes" patch does not add methods (e.g valueOf) or classes (e.g BigFraction, BadFraction). The improvements in valueOf are, as much as possible, incorporated into the existing Fraction class methods. No individual methods are deprecated, either. Assuming others are OK with this approach, I will add a deprecation notice to the whole class in the class header (indicating move to [math] ). We should then open a separate ticket to [math] including the new class (BigFraction, maybe renamed "RationalNumber").
        Hide
        C. Scott Ananian added a comment -

        Could you summarize the changes you made versus the latest patch I submitted?

        Show
        C. Scott Ananian added a comment - Could you summarize the changes you made versus the latest patch I submitted?
        Hide
        Phil Steitz added a comment -

        Created an attachment (id=12030)
        Consolidated bug fixes

        Show
        Phil Steitz added a comment - Created an attachment (id=12030) Consolidated bug fixes
        Hide
        Phil Steitz added a comment -

        I am attaching a patch that fixes the numerical problems identified in this bug,
        but does not change the public API or semantics. Other than more rigorous
        handling of overflows and better numerics, the only behavior change is that
        pow(int) returns a fraction in reduced form. All improvements are from patches
        submitted earlier by C. Scott Ananian.

        I agree with Scott that keeping fractions in non-reduced form is less efficient
        and more prone to overflows. I also do not see practical use cases for
        maintaining the distinction (non-equality) between equivalent fractions. The
        2.0-released version of the class does this, however, so (in agreement with
        Stephen) I think we need to keep the current semantics.

        If there are no objections, after one more review and adding a few more test
        cases, I will commit this patch (labelled "consolidated bug fixes").

        Show
        Phil Steitz added a comment - I am attaching a patch that fixes the numerical problems identified in this bug, but does not change the public API or semantics. Other than more rigorous handling of overflows and better numerics, the only behavior change is that pow(int) returns a fraction in reduced form. All improvements are from patches submitted earlier by C. Scott Ananian. I agree with Scott that keeping fractions in non-reduced form is less efficient and more prone to overflows. I also do not see practical use cases for maintaining the distinction (non-equality) between equivalent fractions. The 2.0-released version of the class does this, however, so (in agreement with Stephen) I think we need to keep the current semantics. If there are no objections, after one more review and adding a few more test cases, I will commit this patch (labelled "consolidated bug fixes").
        Hide
        C. Scott Ananian added a comment -

        If I understand your comment correctly (comparing against my original list of
        Fraction deficiencies), you want all of the improvements except you want to
        preserve unreduced fractions in the interface. The latest version of the patch
        does that; the only thing you might want to change is to remove the @deprecated
        flags on the interfaces which return unreduced fractions.

        Just for the record, no one has yet shown me any convincing reason to preserve
        unreduced fractions. And note that the original interface also silently reduced
        fractions when performing mathematical operations.

        But the final version of the patches are completely compatible with any existing
        users of Fraction.

        Show
        C. Scott Ananian added a comment - If I understand your comment correctly (comparing against my original list of Fraction deficiencies), you want all of the improvements except you want to preserve unreduced fractions in the interface. The latest version of the patch does that; the only thing you might want to change is to remove the @deprecated flags on the interfaces which return unreduced fractions. Just for the record, no one has yet shown me any convincing reason to preserve unreduced fractions. And note that the original interface also silently reduced fractions when performing mathematical operations. But the final version of the patches are completely compatible with any existing users of Fraction.
        Hide
        Phil Steitz added a comment -

        To resolve this bug for [lang], I propose that we adapt Scott's patch to address
        only items c), d), e), f), h) and i)in the Description. We can then consider
        including a class like the one defined by the full patch in [math].

        Show
        Phil Steitz added a comment - To resolve this bug for [lang] , I propose that we adapt Scott's patch to address only items c), d), e), f), h) and i)in the Description. We can then consider including a class like the one defined by the full patch in [math] .
        Hide
        C. Scott Ananian added a comment -

        Mailing list commentary:
        ------------------------------------
        Date: Tue, 8 Jun 2004 22:08:48 -0400 (EDT)
        From: Henri Yandell

        > Phil Steitz wrote:
        > > One thing that we might want to consider, given the magnitude of the
        > > changes, is deprecating this in [lang] and moving it to [math]. That
        > > way, among other things, the (better) continued fraction
        > > implementation in [math] could be used in getFraction(double). The
        > > improved gcd and checked integer arithmetic methods in the patch might
        > > also make good additions to o.a.c.math.MathUtils.

        +1 to this too. Deprecate in 2.1, remove in 3.0.

        I think Fraction will be better served by being in Math where it can
        combine with other code, than in Lang. I don't think there are many
        examples where Fraction will be of use but not other Math things, only an
        educational piece of code where majority of the maths in Math is too
        complex.

        Hen
        -------------------------------------------------
        Date: Wed, 9 Jun 2004 21:38:38 +0100
        From: Stephen Colebourne

        From: "Henri Yandell" <bayard@generationjava.com>
        > I think Fraction will be better served by being in Math where it can
        > combine with other code, than in Lang. I don't think there are many
        > examples where Fraction will be of use but not other Math things, only an
        > educational piece of code where majority of the maths in Math is too
        > complex.

        I agree that [math] is the best home for solving these problems fully,
        however I can't help feel that Fraction is a class that should be in the JDK
        and fits in [lang] scope. So, [lang] gets a (fixed) Fraction class, while
        [math] gets Ratio/BigFraction/Fraction/... whatever is appropriate.

        Stephen
        -------------------------------------
        Date: Wed, 09 Jun 2004 16:59:46 -0400
        From: Mark R. Diggory

        Stephen Colebourne wrote:
        >I agree that [math] is the best home for solving these problems fully,
        >however I can't help feel that Fraction is a class that should be in the JDK
        >and fits in [lang] scope. So, [lang] gets a (fixed) Fraction class, while
        >[math] gets Ratio/BigFraction/Fraction/... whatever is appropriate.

        This makes sense only if there is always a 1 to 1 mapping between
        o.a.c.lang and java.lang, meaning, somehow the contents we have in our
        lang represent things we would like to see in java.lang someday (whether
        truly plausable or not). I'm not convinced this is possible, there are
        too much content in java.lang that overlaps with other commons subprojects.

        As well, I consider "java.lang" is really a poorly named and poorly
        defined package in the first place, a kind of "catchall" for initial
        object hierarchy of Java (similarly, java.util is a poorly named
        "catchall" for the initial datastructures and collections) . I think
        there should have been a java.math package that housed Math, Number ...
        plus java.util.Random .... This would have been the home for something
        like Fraction in my little fantasy world.

        Either way, I think Math would be glad to support Fraction in the Math
        subproject if concensus proves it wanted.

        And don't mis[i]nterpret my opinion, +1 on patching it even if it stays
        where it is.

        -Mark

        Show
        C. Scott Ananian added a comment - Mailing list commentary: ------------------------------------ Date: Tue, 8 Jun 2004 22:08:48 -0400 (EDT) From: Henri Yandell > Phil Steitz wrote: > > One thing that we might want to consider, given the magnitude of the > > changes, is deprecating this in [lang] and moving it to [math] . That > > way, among other things, the (better) continued fraction > > implementation in [math] could be used in getFraction(double). The > > improved gcd and checked integer arithmetic methods in the patch might > > also make good additions to o.a.c.math.MathUtils. +1 to this too. Deprecate in 2.1, remove in 3.0. I think Fraction will be better served by being in Math where it can combine with other code, than in Lang. I don't think there are many examples where Fraction will be of use but not other Math things, only an educational piece of code where majority of the maths in Math is too complex. Hen ------------------------------------------------- Date: Wed, 9 Jun 2004 21:38:38 +0100 From: Stephen Colebourne From: "Henri Yandell" <bayard@generationjava.com> > I think Fraction will be better served by being in Math where it can > combine with other code, than in Lang. I don't think there are many > examples where Fraction will be of use but not other Math things, only an > educational piece of code where majority of the maths in Math is too > complex. I agree that [math] is the best home for solving these problems fully, however I can't help feel that Fraction is a class that should be in the JDK and fits in [lang] scope. So, [lang] gets a (fixed) Fraction class, while [math] gets Ratio/BigFraction/Fraction/... whatever is appropriate. Stephen ------------------------------------- Date: Wed, 09 Jun 2004 16:59:46 -0400 From: Mark R. Diggory Stephen Colebourne wrote: >I agree that [math] is the best home for solving these problems fully, >however I can't help feel that Fraction is a class that should be in the JDK >and fits in [lang] scope. So, [lang] gets a (fixed) Fraction class, while > [math] gets Ratio/BigFraction/Fraction/... whatever is appropriate. This makes sense only if there is always a 1 to 1 mapping between o.a.c.lang and java.lang, meaning, somehow the contents we have in our lang represent things we would like to see in java.lang someday (whether truly plausable or not). I'm not convinced this is possible, there are too much content in java.lang that overlaps with other commons subprojects. As well, I consider "java.lang" is really a poorly named and poorly defined package in the first place, a kind of "catchall" for initial object hierarchy of Java (similarly, java.util is a poorly named "catchall" for the initial datastructures and collections) . I think there should have been a java.math package that housed Math, Number ... plus java.util.Random .... This would have been the home for something like Fraction in my little fantasy world. Either way, I think Math would be glad to support Fraction in the Math subproject if concensus proves it wanted. And don't mis [i] nterpret my opinion, +1 on patching it even if it stays where it is. -Mark
        Hide
        C. Scott Ananian added a comment -

        Date: Tue, 08 Jun 2004 14:23:57 -0400
        From: Mark R. Diggory

        Phil Steitz wrote:

        > One thing that we might want to consider, given the magnitude of the
        > changes, is deprecating this in [lang] and moving it to [math]. That
        > way, among other things, the (better) continued fraction
        > implementation in [math] could be used in getFraction(double). The
        > improved gcd and checked integer arithmetic methods in the patch might
        > also make good additions to o.a.c.math.MathUtils.

        +1 On this, Fractions and Ratios should be managed by those who are
        aware of the numerical issues. While I think numerical comparators like
        min/max can hang out in lang, I really do think higher order numerical
        objects such as fraction are better housed and maintained by Math folks.
        Chances are, if your using Fractions and Ratio's you want other Math
        features as well.

        -Mark

        Show
        C. Scott Ananian added a comment - Date: Tue, 08 Jun 2004 14:23:57 -0400 From: Mark R. Diggory Phil Steitz wrote: > One thing that we might want to consider, given the magnitude of the > changes, is deprecating this in [lang] and moving it to [math] . That > way, among other things, the (better) continued fraction > implementation in [math] could be used in getFraction(double). The > improved gcd and checked integer arithmetic methods in the patch might > also make good additions to o.a.c.math.MathUtils. +1 On this, Fractions and Ratios should be managed by those who are aware of the numerical issues. While I think numerical comparators like min/max can hang out in lang, I really do think higher order numerical objects such as fraction are better housed and maintained by Math folks. Chances are, if your using Fractions and Ratio's you want other Math features as well. -Mark
        Hide
        C. Scott Ananian added a comment -

        More mailing list commentary:
        -----------------------------------------------------
        Date: Thu, 3 Jun 2004 22:16:03 +0100
        From: Stephen Colebourne

        "C. Scott Ananian" <cscott@cscott.net> write:
        > The idea is to remove the deprecated methods in some future version of
        > lang; at which point Fraction can be made final again (and BadFraction
        > completely disappears). It would be harder to purge BadFraction if its
        > code is mixed willy-nilly with the 'real' Fraction code.
        This presumes that everyone wants a reduced fraction. I believe that there
        are use cases for holding an unreduced one. The main one that strikes me is
        education.

        Somewhere along the line I've lost the reason why we should deprecate
        unreduced fractions. They are a valid representation of a fraction (so long
        as the internal calculations are done properly), so why not allow them?

        BTW, the 2/4 != 1/2 is consistent with the JDK - classes like BigDecimal
        IIRC will have similar 'odd' behaviour, eg 0.500 != 0.5.

        > The constructor for Fraction is package-private (or should be!) so no one
        > outside the lang package can create a subclass in any case.
        I hadn't noticed that, so the final is not an issue.

        Stephen
        --------------------
        Date: Thu, 3 Jun 2004 17:50:00 -0400 (EDT)
        From: C. Scott Ananian

        On Thu, 3 Jun 2004, Stephen Colebourne wrote:

        > This presumes that everyone wants a reduced fraction. I believe that there
        > are use cases for holding an unreduced one. The main one that strikes me is
        > education.

        The org.apache.commons.math.Fraction class is not targetted at education.
        It's intended to be useful for working programmers.

        If people complain about the deprecation, then the methods can be
        undeprecated. I doubt that will be the case.

        > Somewhere along the line I've lost the reason why we should deprecate
        > unreduced fractions. They are a valid representation of a fraction (so long
        > as the internal calculations are done properly), so why not allow them?

        The primary reason is programmer convenience. Fractions will overflow
        unless simplified regularly. Further, the user will 'expect' that
        1/2==2/4. Maintaining in 'simplified form' also allows more predictable
        overflow behavior. By making this the actual behavior, potential bugs are
        eliminated, and the user is not surprised.

        Again, it's not like the deprecation can't be removed during alpha, beta,
        or after release or some vocal existing user appears.

        > BTW, the 2/4 != 1/2 is consistent with the JDK - classes like BigDecimal
        > IIRC will have similar 'odd' behaviour, eg 0.500 != 0.5.

        In BigDecimal these numbers are arguably different: they have different
        precisions and thus round differently. For example:
        divide(0.5,2) != divide(0.500,2)

        Fraction is not intended to be used in this manner. Fractions
        are not rounded. Computing with an unsimplified fraction may result in
        overflow when a simplified fraction will not, but that is not a
        specifically-desired behavior (nor is it a well-specified one).

        Is there any other example of such behavior in the JDK?
        --scott
        ------------------------------------------------------------
        Date: Sat, 05 Jun 2004 11:37:47 -0700
        From: Phil Steitz

        C. Scott Ananian wrote:
        > The org.apache.commons.math.Fraction class is not targetted at education.
        > It's intended to be useful for working programmers.

        The problem is that we do not know what the "working programmers" are
        going to use this class for. Your view seems to be that "Fraction" should
        really be "RationalNumber" – so that two equivalent fractions are equal.
        The problem is that the class is not named or currently implemented that
        way (in terms of representation and identity). Representing the fractions
        themselves instead of collapsing immediately to the equivalence classes
        (rational numbers) is more flexible; though as you point out, more care
        has to be taken to prevent overflows and some efficiency in the arithmetic
        operations may be sacrificed as a result.

        If we just fix the computational bugs in the current implementation, the
        overflow situation should be OK with the arithmetic operations implemented
        as they are now, since they call reduce() before returning results. We
        may in fact want to add alternative methods that do not reduce returned
        fractions, or that otherwise restrict / control denominators. While I do
        not have specific use cases in mind, it could be that some
        number-theoretic applications for this sort of thing may exist.

        The fact that all current operations reduce returned values led me
        initially to agree that it was pointless to maintain the disctinction
        between equivalent fractions. Thinking about it some more, I am -0 to
        changing Fraction to "RationalNumber." I think our best path is to start
        by fixing the computational bugs and then see what sorts of applications
        emerge.

        Phil
        --------------------------------------------------------------
        Date: Sat, 5 Jun 2004 13:35:23 -0700 (PDT)
        From: Al Chou

        It seems to me that number-theoretic users would gravitate toward commons.math
        rather than commons.lang.math, and that such users (and no one else) might
        conceivably find non-reduced representations of fractions useful (it sure would
        be nice to have someone here with number theory experience to tell us; the only
        use I think I'd ever have is if I cared to know the exact history of the values
        in a calculation or derivation, but that would probably arise only in the
        context of computerized algebra, which I have never tried to program). That
        seems to argue for moving this class directly into commons.math as is, and
        leaving behind an always-reducing version of itself in commons.lang.math.

        But I am definitely +1 to first fixing the defects in the current class where
        it lives and deferring other decisions.

        Al
        -----------------------------------------------------------
        Date: Tue, 8 Jun 2004 13:58:06 -0400 (EDT)
        From: C. Scott Ananian

        On Sat, 5 Jun 2004, Phil Steitz wrote:

        > The problem is that we do not know what the "working programmers" are
        > going to use this class for. Your view seems to be that "Fraction" should
        > really be "RationalNumber" – so that two equivalent fractions are equal.

        Yes. Scheme has had this numeric class for a long time (1975) and it IS what
        "working programmers" find useful.

        > The problem is that the class is not named or currently implemented that
        > way (in terms of representation and identity). Representing the fractions
        > themselves instead of collapsing immediately to the equivalence classes
        > (rational numbers) is more flexible; though as you point out, more care
        > has to be taken to prevent overflows and some efficiency in the arithmetic
        > operations may be sacrificed as a result.

        ...and the current implementation allows both uses, although it deprecates
        the latter (due to its being harder for programmers to use correctly).
        It can be un-deprecated at some later time if there is outcry.

        > If we just fix the computational bugs in the current implementation, the
        > overflow situation should be OK with the arithmetic operations implemented
        > as they are now, since they call reduce() before returning results. We
        > may in fact want to add alternative methods that do not reduce returned
        > fractions, or that otherwise restrict / control denominators. While I do
        > not have specific use cases in mind, it could be that some
        > number-theoretic applications for this sort of thing may exist.

        This is always a really bad way to design software.

        > The fact that all current operations reduce returned values led me
        > initially to agree that it was pointless to maintain the disctinction
        > between equivalent fractions. Thinking about it some more, I am -0 to
        > changing Fraction to "RationalNumber." I think our best path is to start
        > by fixing the computational bugs and then see what sorts of applications
        > emerge.

        I have an application, and I made the changes that my application and decades
        of scheme experience have shown to be useful.
        --scott

        Show
        C. Scott Ananian added a comment - More mailing list commentary: ----------------------------------------------------- Date: Thu, 3 Jun 2004 22:16:03 +0100 From: Stephen Colebourne "C. Scott Ananian" <cscott@cscott.net> write: > The idea is to remove the deprecated methods in some future version of > lang; at which point Fraction can be made final again (and BadFraction > completely disappears). It would be harder to purge BadFraction if its > code is mixed willy-nilly with the 'real' Fraction code. This presumes that everyone wants a reduced fraction. I believe that there are use cases for holding an unreduced one. The main one that strikes me is education. Somewhere along the line I've lost the reason why we should deprecate unreduced fractions. They are a valid representation of a fraction (so long as the internal calculations are done properly), so why not allow them? BTW, the 2/4 != 1/2 is consistent with the JDK - classes like BigDecimal IIRC will have similar 'odd' behaviour, eg 0.500 != 0.5. > The constructor for Fraction is package-private (or should be!) so no one > outside the lang package can create a subclass in any case. I hadn't noticed that, so the final is not an issue. Stephen -------------------- Date: Thu, 3 Jun 2004 17:50:00 -0400 (EDT) From: C. Scott Ananian On Thu, 3 Jun 2004, Stephen Colebourne wrote: > This presumes that everyone wants a reduced fraction. I believe that there > are use cases for holding an unreduced one. The main one that strikes me is > education. The org.apache.commons.math.Fraction class is not targetted at education. It's intended to be useful for working programmers. If people complain about the deprecation, then the methods can be undeprecated. I doubt that will be the case. > Somewhere along the line I've lost the reason why we should deprecate > unreduced fractions. They are a valid representation of a fraction (so long > as the internal calculations are done properly), so why not allow them? The primary reason is programmer convenience. Fractions will overflow unless simplified regularly. Further, the user will 'expect' that 1/2==2/4. Maintaining in 'simplified form' also allows more predictable overflow behavior. By making this the actual behavior, potential bugs are eliminated, and the user is not surprised. Again, it's not like the deprecation can't be removed during alpha, beta, or after release or some vocal existing user appears. > BTW, the 2/4 != 1/2 is consistent with the JDK - classes like BigDecimal > IIRC will have similar 'odd' behaviour, eg 0.500 != 0.5. In BigDecimal these numbers are arguably different: they have different precisions and thus round differently. For example: divide(0.5,2) != divide(0.500,2) Fraction is not intended to be used in this manner. Fractions are not rounded. Computing with an unsimplified fraction may result in overflow when a simplified fraction will not, but that is not a specifically-desired behavior (nor is it a well-specified one). Is there any other example of such behavior in the JDK? --scott ------------------------------------------------------------ Date: Sat, 05 Jun 2004 11:37:47 -0700 From: Phil Steitz C. Scott Ananian wrote: > The org.apache.commons.math.Fraction class is not targetted at education. > It's intended to be useful for working programmers. The problem is that we do not know what the "working programmers" are going to use this class for. Your view seems to be that "Fraction" should really be "RationalNumber" – so that two equivalent fractions are equal. The problem is that the class is not named or currently implemented that way (in terms of representation and identity). Representing the fractions themselves instead of collapsing immediately to the equivalence classes (rational numbers) is more flexible; though as you point out, more care has to be taken to prevent overflows and some efficiency in the arithmetic operations may be sacrificed as a result. If we just fix the computational bugs in the current implementation, the overflow situation should be OK with the arithmetic operations implemented as they are now, since they call reduce() before returning results. We may in fact want to add alternative methods that do not reduce returned fractions, or that otherwise restrict / control denominators. While I do not have specific use cases in mind, it could be that some number-theoretic applications for this sort of thing may exist. The fact that all current operations reduce returned values led me initially to agree that it was pointless to maintain the disctinction between equivalent fractions. Thinking about it some more, I am -0 to changing Fraction to "RationalNumber." I think our best path is to start by fixing the computational bugs and then see what sorts of applications emerge. Phil -------------------------------------------------------------- Date: Sat, 5 Jun 2004 13:35:23 -0700 (PDT) From: Al Chou It seems to me that number-theoretic users would gravitate toward commons.math rather than commons.lang.math, and that such users (and no one else) might conceivably find non-reduced representations of fractions useful (it sure would be nice to have someone here with number theory experience to tell us; the only use I think I'd ever have is if I cared to know the exact history of the values in a calculation or derivation, but that would probably arise only in the context of computerized algebra, which I have never tried to program). That seems to argue for moving this class directly into commons.math as is, and leaving behind an always-reducing version of itself in commons.lang.math. But I am definitely +1 to first fixing the defects in the current class where it lives and deferring other decisions. Al ----------------------------------------------------------- Date: Tue, 8 Jun 2004 13:58:06 -0400 (EDT) From: C. Scott Ananian On Sat, 5 Jun 2004, Phil Steitz wrote: > The problem is that we do not know what the "working programmers" are > going to use this class for. Your view seems to be that "Fraction" should > really be "RationalNumber" – so that two equivalent fractions are equal. Yes. Scheme has had this numeric class for a long time (1975) and it IS what "working programmers" find useful. > The problem is that the class is not named or currently implemented that > way (in terms of representation and identity). Representing the fractions > themselves instead of collapsing immediately to the equivalence classes > (rational numbers) is more flexible; though as you point out, more care > has to be taken to prevent overflows and some efficiency in the arithmetic > operations may be sacrificed as a result. ...and the current implementation allows both uses, although it deprecates the latter (due to its being harder for programmers to use correctly). It can be un-deprecated at some later time if there is outcry. > If we just fix the computational bugs in the current implementation, the > overflow situation should be OK with the arithmetic operations implemented > as they are now, since they call reduce() before returning results. We > may in fact want to add alternative methods that do not reduce returned > fractions, or that otherwise restrict / control denominators. While I do > not have specific use cases in mind, it could be that some > number-theoretic applications for this sort of thing may exist. This is always a really bad way to design software. > The fact that all current operations reduce returned values led me > initially to agree that it was pointless to maintain the disctinction > between equivalent fractions. Thinking about it some more, I am -0 to > changing Fraction to "RationalNumber." I think our best path is to start > by fixing the computational bugs and then see what sorts of applications > emerge. I have an application, and I made the changes that my application and decades of scheme experience have shown to be useful. --scott
        Hide
        C. Scott Ananian added a comment -

        Created an attachment (id=11757)
        Small patch to explain "relatively prime" in the javadoc.

        Show
        C. Scott Ananian added a comment - Created an attachment (id=11757) Small patch to explain "relatively prime" in the javadoc.
        Hide
        C. Scott Ananian added a comment -

        My response to Stephen's comments (slightly edited for brevity):

        From: C. Scott Ananian

        On Thu, 3 Jun 2004, Stephen Colebourne wrote:

        > I had a 5 second look yesterday, and realised how big the change is. My
        > immediate concern is that the Fraction class has lost its final status,
        > making it less immutable.

        The idea is to remove the deprecated methods in some future version of
        lang; at which point Fraction can be made final again (and BadFraction
        completely disappears). It would be harder to purge BadFraction if its
        code is mixed willy-nilly with the 'real' Fraction code.

        The constructor for Fraction is package-private (or should be!) so no one
        outside the lang package can create a subclass in any case.

        > Also, I wasn't sure what 'relatively prime' actually meant. Its probably too
        > mathematical for the target audience in [lang].

        Formal definition: http://mathworld.wolfram.com/RelativelyPrime.html

        It just means that there is no integer greater than one which divides both
        numbers evenly (gcd(x,y)==1), or (equivalently) that the fraction is
        "simplified". I'll be glad to add that to the javadoc.

        > Finally, I believe that [lang] is the right place for these (including
        > BigFraction). They represent missing parts of the JDK, so [lang] is
        > appropriate.

        ok.
        --scott

        Show
        C. Scott Ananian added a comment - My response to Stephen's comments (slightly edited for brevity): From: C. Scott Ananian On Thu, 3 Jun 2004, Stephen Colebourne wrote: > I had a 5 second look yesterday, and realised how big the change is. My > immediate concern is that the Fraction class has lost its final status, > making it less immutable. The idea is to remove the deprecated methods in some future version of lang; at which point Fraction can be made final again (and BadFraction completely disappears). It would be harder to purge BadFraction if its code is mixed willy-nilly with the 'real' Fraction code. The constructor for Fraction is package-private (or should be!) so no one outside the lang package can create a subclass in any case. > Also, I wasn't sure what 'relatively prime' actually meant. Its probably too > mathematical for the target audience in [lang] . Formal definition: http://mathworld.wolfram.com/RelativelyPrime.html It just means that there is no integer greater than one which divides both numbers evenly (gcd(x,y)==1), or (equivalently) that the fraction is "simplified". I'll be glad to add that to the javadoc. > Finally, I believe that [lang] is the right place for these (including > BigFraction). They represent missing parts of the JDK, so [lang] is > appropriate. ok. --scott
        Hide
        C. Scott Ananian added a comment -

        Imported from commons-dev mailing list discussion for archival here:

        From: Stephen Colebourne
        Subject: Re: [lang] [math] org.apache.commons.lang.math.Fraction class

        I had a 5 second look yesterday, and realised how big the change is. My
        immediate concern is that the Fraction class has lost its final status,
        making it less immutable.

        I was wondering whether it would be possible to have just one class (rather
        than an additional BadFraction subclass) that held an additional field only
        used when using non-reduced fractions. Effectively merging the two classes
        into one?

        Also, I wasn't sure what 'relatively prime' actually meant. Its probably too
        mathematical for the target audience in [lang].

        Finally, I believe that [lang] is the right place for these (including
        BigFraction). They represent missing parts of the JDK, so [lang] is
        appropriate.

        Show
        C. Scott Ananian added a comment - Imported from commons-dev mailing list discussion for archival here: From: Stephen Colebourne Subject: Re: [lang] [math] org.apache.commons.lang.math.Fraction class I had a 5 second look yesterday, and realised how big the change is. My immediate concern is that the Fraction class has lost its final status, making it less immutable. I was wondering whether it would be possible to have just one class (rather than an additional BadFraction subclass) that held an additional field only used when using non-reduced fractions. Effectively merging the two classes into one? Also, I wasn't sure what 'relatively prime' actually meant. Its probably too mathematical for the target audience in [lang] . Finally, I believe that [lang] is the right place for these (including BigFraction). They represent missing parts of the JDK, so [lang] is appropriate.
        Hide
        C. Scott Ananian added a comment -

        Note that attachment #11700 already split the FractionTest class into two
        pieces: FractionTest tests the deprecated backwards-compatible interface, and
        FractionTest2 tests the 'new style' preferred interface. Accordingly,
        FractionTest still uses the old divideBy() and multiplyBy() method names, while
        FractionTest2 tests the new divide() and multiply() names.

        BigFraction just uses the new names, as there is no need for
        backwards-compatibility cruft there.

        Show
        C. Scott Ananian added a comment - Note that attachment #11700 already split the FractionTest class into two pieces: FractionTest tests the deprecated backwards-compatible interface, and FractionTest2 tests the 'new style' preferred interface. Accordingly, FractionTest still uses the old divideBy() and multiplyBy() method names, while FractionTest2 tests the new divide() and multiply() names. BigFraction just uses the new names, as there is no need for backwards-compatibility cruft there.
        Hide
        C. Scott Ananian added a comment -

        Created an attachment (id=11733)
        Patch, to be applied after the previous one, which gives multiply() and divide() their standard names.

        Show
        C. Scott Ananian added a comment - Created an attachment (id=11733) Patch, to be applied after the previous one, which gives multiply() and divide() their standard names.
        Hide
        C. Scott Ananian added a comment -

        While we're changing Fraction: the multiplyBy and divideBy methods should be
        renamed 'multiply' and 'divide' to match standard Java convention: see for
        example the BigInteger class. There's some discussion of (eventually) adding
        operator overloading to Java, which would use these 'standard named methods', so
        this could become even more important than it is at present.

        The next patch, which is separated out from the others and should be applied
        after attachment #11701, simply deprecates the current names and adds new
        methods with the 'correct' names. Old code will continue to work.

        Show
        C. Scott Ananian added a comment - While we're changing Fraction: the multiplyBy and divideBy methods should be renamed 'multiply' and 'divide' to match standard Java convention: see for example the BigInteger class. There's some discussion of (eventually) adding operator overloading to Java, which would use these 'standard named methods', so this could become even more important than it is at present. The next patch, which is separated out from the others and should be applied after attachment #11701, simply deprecates the current names and adds new methods with the 'correct' names. Old code will continue to work.
        Hide
        C. Scott Ananian added a comment -

        Created an attachment (id=11701)
        Update previous patch with some minor javadoc fixes.

        Show
        C. Scott Ananian added a comment - Created an attachment (id=11701) Update previous patch with some minor javadoc fixes.
        Hide
        C. Scott Ananian added a comment -

        Created an attachment (id=11700)
        New version of patch which preserves backwards-compatibility.

        Show
        C. Scott Ananian added a comment - Created an attachment (id=11700) New version of patch which preserves backwards-compatibility.
        Hide
        C. Scott Ananian added a comment -

        I've implemented option (b) from the previous comment. Fraction is now
        completely backwards-compatible, but getFraction and getReducedFraction have
        been deprecated in favor of a new 'valueOf' method (which is what the JDK
        subclasses of Number use, anyway). If you avoid getFraction(), you will never
        touch the backwards-compatibility code and your fractions will always be
        reduced. Serialization is compatible, too.

        Added a new test suite, FractionTest2. FractionTest now tests only the
        'backwards-compatible' interface (and you'll notice that the diff is smaller and
        the results of no existing tests have changed). FractionTest2 uses 'valueOf' to
        test the 'modern' interface. Diffing FractionTest against FractionTest2 gives a
        reasonably straight-forward diff which shows what behavior is changed by the new
        interface: basically fractions are always reduced, hashCode() and equals()
        reflect numerical equality, and fewer computations overflow.

        I hope this will address the backwards-compatibility concerns in a way that
        preserves a clean interface for new users.

        Show
        C. Scott Ananian added a comment - I've implemented option (b) from the previous comment. Fraction is now completely backwards-compatible, but getFraction and getReducedFraction have been deprecated in favor of a new 'valueOf' method (which is what the JDK subclasses of Number use, anyway). If you avoid getFraction(), you will never touch the backwards-compatibility code and your fractions will always be reduced. Serialization is compatible, too. Added a new test suite, FractionTest2. FractionTest now tests only the 'backwards-compatible' interface (and you'll notice that the diff is smaller and the results of no existing tests have changed). FractionTest2 uses 'valueOf' to test the 'modern' interface. Diffing FractionTest against FractionTest2 gives a reasonably straight-forward diff which shows what behavior is changed by the new interface: basically fractions are always reduced, hashCode() and equals() reflect numerical equality, and fewer computations overflow. I hope this will address the backwards-compatibility concerns in a way that preserves a clean interface for new users.
        Hide
        C. Scott Ananian added a comment -

        It has been mentioned that perhaps Fraction (and BigFraction) belong in the
        'math' package, instead of 'lang'. But also that a version of Fraction which
        fixed just the most glaring bugs might remain in 'lang' (hopefully deprecated).
        I responded on the commons-dev mailing list as follows:


        Two versions of the fraction class? One broken, one not? I don't understand
        this. Is there really an existing user complaining that we're taking away the
        "2/4 != 1/2" behavior?

        It seems to me, at least, that it makes sense to apply the change and wait for
        users to complain (that's what alpha, beta, and rc releases are for) before
        preserving "surprising" behavior. It's not like the patch can't be a) reverted,
        or b) hacked to preserve unreduced fractions for abs(), getFraction(), pow(),
        equals(), and hashCode() [but not other methods] later, if it seems to be an issue.

        For option b) I'd suggest a private subclass returned by getFraction() which
        overrode just abs(), pow(), equals(), and hashCode(). Then
        Fraction.getFraction() would be deprecated and users would be strongly
        encouraged to use Fraction.getReducedFraction() instead, which ensures that they
        will never touch the 'backwards compatibility' code.

        [Note that both abs() and pow() will always return a reduced fraction given a
        reduced fraction, as a little thinking should convince you.]

        But again, this seems like a long way to bend over backwards for users-who-care
        who have not yet been shown to exist. [google didn't help me find any.]

        Show
        C. Scott Ananian added a comment - It has been mentioned that perhaps Fraction (and BigFraction) belong in the 'math' package, instead of 'lang'. But also that a version of Fraction which fixed just the most glaring bugs might remain in 'lang' (hopefully deprecated). I responded on the commons-dev mailing list as follows: Two versions of the fraction class? One broken, one not? I don't understand this. Is there really an existing user complaining that we're taking away the "2/4 != 1/2" behavior? It seems to me, at least, that it makes sense to apply the change and wait for users to complain (that's what alpha, beta, and rc releases are for) before preserving "surprising" behavior. It's not like the patch can't be a) reverted, or b) hacked to preserve unreduced fractions for abs(), getFraction(), pow(), equals(), and hashCode() [but not other methods] later, if it seems to be an issue. For option b) I'd suggest a private subclass returned by getFraction() which overrode just abs(), pow(), equals(), and hashCode(). Then Fraction.getFraction() would be deprecated and users would be strongly encouraged to use Fraction.getReducedFraction() instead, which ensures that they will never touch the 'backwards compatibility' code. [Note that both abs() and pow() will always return a reduced fraction given a reduced fraction, as a little thinking should convince you.] But again, this seems like a long way to bend over backwards for users-who-care who have not yet been shown to exist. [google didn't help me find any.]
        Hide
        C. Scott Ananian added a comment -

        Created an attachment (id=11694)
        Added new BigFraction class (and test suite) which is an arbitrary-precision version of Fraction. Rest of patch (Fraction stuff) is identical to previous patch.

        Show
        C. Scott Ananian added a comment - Created an attachment (id=11694) Added new BigFraction class (and test suite) which is an arbitrary-precision version of Fraction. Rest of patch (Fraction stuff) is identical to previous patch.
        Hide
        C. Scott Ananian added a comment -

        Created an attachment (id=11693)
        New version of the patch which fixes getFraction(String) and some javadoc typos.

        Show
        C. Scott Ananian added a comment - Created an attachment (id=11693) New version of the patch which fixes getFraction(String) and some javadoc typos.
        Hide
        C. Scott Ananian added a comment -

        Found another bug: Fraction.getFraction("-7 1/2") gives incorrect results.
        Actually all negative proper fractions are wrong: the string is being parsed as
        "-7 + 1/2" with the result being -6 1/2.

        Also, I found some javadoc typos and javadoc mentions of 'reduction' which are
        no longer necessary.

        I'm attaching a new version of the patch which fixes both of these problems (and
        also adds new JUnit tests to identify the getFraction() problem).

        Show
        C. Scott Ananian added a comment - Found another bug: Fraction.getFraction("-7 1/2") gives incorrect results. Actually all negative proper fractions are wrong: the string is being parsed as "-7 + 1/2" with the result being -6 1/2. Also, I found some javadoc typos and javadoc mentions of 'reduction' which are no longer necessary. I'm attaching a new version of the patch which fixes both of these problems (and also adds new JUnit tests to identify the getFraction() problem).
        Hide
        C. Scott Ananian added a comment -

        Created an attachment (id=11692)
        Patch to address concerns of this bug.

        Show
        C. Scott Ananian added a comment - Created an attachment (id=11692) Patch to address concerns of this bug.

          People

          • Assignee:
            Unassigned
            Reporter:
            C. Scott Ananian
          • Votes:
            1 Vote for this issue
            Watchers:
            0 Start watching this issue

            Dates

            • Created:
              Updated:
              Resolved:

              Development