Details

Type: Improvement

Status: Closed

Priority: 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 noop, 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 doubleandmultiply
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 backwardscompatibility
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.

 ASF.LICENSE.NOT.GRANTEDfractionPatch
 45 kB
 Phil Steitz

 ASF.LICENSE.NOT.GRANTEDlangfraction8x.patch
 1 kB
 C. Scott Ananian

 ASF.LICENSE.NOT.GRANTEDlangfraction7x.patch
 15 kB
 C. Scott Ananian

 ASF.LICENSE.NOT.GRANTEDlangfraction5.patch
 186 kB
 C. Scott Ananian

 ASF.LICENSE.NOT.GRANTEDlangfraction4.patch
 186 kB
 C. Scott Ananian

 ASF.LICENSE.NOT.GRANTEDlangfraction3.patch
 130 kB
 C. Scott Ananian

 ASF.LICENSE.NOT.GRANTEDlangfraction2.patch
 57 kB
 C. Scott Ananian

 ASF.LICENSE.NOT.GRANTEDlangfraction.patch
 53 kB
 C. Scott Ananian
Activity
 All
 Comments
 Work Log
 History
 Activity
 Transitions
Reopening then closing to deal with migration bug.
2.1 released, closing.
Numeric fixes committed.
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.
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.
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 commonslang is a good
idea, and it's good that a nice clean API will make it to commonsmath (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 testsuites was
to allow largeish 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.
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.
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").
Could you summarize the changes you made versus the latest patch I submitted?
Created an attachment (id=12030)
Consolidated bug fixes
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 nonreduced form is less efficient
and more prone to overflows. I also do not see practical use cases for
maintaining the distinction (nonequality) between equivalent fractions. The
2.0released 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").
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.
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].
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
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
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 willynilly 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 packageprivate (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
specificallydesired behavior (nor is it a wellspecified 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
numbertheoretic 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 numbertheoretic users would gravitate toward commons.math
rather than commons.lang.math, and that such users (and no one else) might
conceivably find nonreduced 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 alwaysreducing 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 undeprecated 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
> numbertheoretic 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
Created an attachment (id=11757)
Small patch to explain "relatively prime" in the javadoc.
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 willynilly with the 'real' Fraction code.
The constructor for Fraction is packageprivate (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
Imported from commonsdev 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 nonreduced 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.
Note that attachment #11700 already split the FractionTest class into two
pieces: FractionTest tests the deprecated backwardscompatible 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
backwardscompatibility cruft there.
Created an attachment (id=11733)
Patch, to be applied after the previous one, which gives multiply() and divide() their standard names.
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.
Created an attachment (id=11701)
Update previous patch with some minor javadoc fixes.
Created an attachment (id=11700)
New version of patch which preserves backwardscompatibility.
I've implemented option (b) from the previous comment. Fraction is now
completely backwardscompatible, 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 backwardscompatibility code and your fractions will always be
reduced. Serialization is compatible, too.
Added a new test suite, FractionTest2. FractionTest now tests only the
'backwardscompatible' 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 straightforward 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 backwardscompatibility concerns in a way that
preserves a clean interface for new users.
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 commonsdev 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 userswhocare
who have not yet been shown to exist. [google didn't help me find any.]
Created an attachment (id=11694)
Added new BigFraction class (and test suite) which is an arbitraryprecision version of Fraction. Rest of patch (Fraction stuff) is identical to previous patch.
Created an attachment (id=11693)
New version of the patch which fixes getFraction(String) and some javadoc typos.
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).
Created an attachment (id=11692)
Patch to address concerns of this bug.
Reopening then closing to deal with migration bug.