commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "C. Scott Ananian" <csc...@cscott.net>
Subject [lang] lang.math.Fraction class
Date Sat, 29 May 2004 05:24:37 GMT
The Fraction class in commons Lang 2.0 is decidedly suboptimal. As Knuth
describes in Chapter 4.5, the Fraction should be maintained as a pair of
integers which are relatively prime.  No 'reduction' of fractions is ever
required, and the user isn't forced to repeatedly call 'reduce()' to
prevent overflow.  In addition, the gcd algorithm in Fraction would be
better implemented with a modern algorithm which uses subtraction instead
of division (see Knuth 4.5.2, 'A binary method').  The Fraction.pow()
implementation is currently very dangerous, in that it assumed the double
returned by Math.pow() can be accurately converted to an int.  A better
method would preserve precision by computing nth powers using doubling and
adding (the 'ancient Egyptian' method).  Fraction.hashCode() currently has
a race condition which could lead to bogus return values in multithreaded
code.

Using the unique relatively prime integers in Fraction introduces some
minor backwards-compatibility issues: reduce() would become deprecated and
a no-op, and some applications might notice that the numerator and
denominator of un-simplified fractions (for example,
Fraction.TWO_QUARTERS) have changed. The (unintuitive current) behavior of
equals() and hashCode() will change slightly as well, as numerical
accuracy will become equivalent to Fraction.equals()==true.  Compatibility
of serialized objects can be preserved by performing fraction
simplification at deserialization time.

Attached is a patch which implements these algorithmic improvements and
greatly expands the test suite for Fraction as well. Particular attention
has been paid to overflow situations to ensure that an exception is always
thrown where warranted, and as far as possible, no overflow is thrown when
the result (as opposed to the intermediate results) can be represented as
a pair of ints.  We should also handle Integer.MAX_VALUE and
Integer.MIN_VALUE better now as well (in general, we handle larger
fractions better than before).

The checkstyle target reports no warnings or errors on the new code,
and clover reports excellent test suite coverage.

I hope that this contribution is useful to you.
Comments are welcome.
 --scott

NRA pending domestic disruption plutonium milita Nazi insurgent ASW
Boston kibo agent Rule Psix colonel Legion of Doom Sudan postcard
                         ( http://cscott.net/ )
Mime
View raw message