Here is what I propose for the Fraction doc text regarding this issue:
* Implement add and subtract. This algorithm is similar to that
* described in Knuth 4.5.1. while making some concessions to
* performance. Note Knuth 4.5.1 Exercise 7, which observes that
* adding two fractions with 32-bit numerators and denominators
* requires 65 bits in extreme cases. Here calculations are performed
* with 64-bit longs and the BigFraction class is recommended for
numbers
* that may grow large enough to be in danger of overflow.
On Fri, Nov 9, 2018 at 4:33 PM Eric Barnhill <ericbarnh...@gmail.com> wrote:
> Addendum to the above. In an exercise in the Knuth book Knuth does indeed
> state that "If the inputs are n-bit binary numbers, 2N+1 bits may be
> necessary to represent t." where t is a derived quantity that would take
> some time to explain.
>
> So that means in extreme cases, the needed precision to represent a
> fraction operation with 32 bits ints is 65 bits, one more than a long has.
>
> The present code solves this by using BigInteger briefly in the code,
> which strikes me as an awfully big performance hit for what must surely be
> very occasional and very extreme cases.
>
> I think the most sensible strategy would be to restrict the precision of
> Fraction to longs, with user guidance to use BigFraction if there is
> concern of overflow.
>
> Eric
>
>
>
>
>
>
>
> On Thu, Nov 8, 2018 at 11:11 AM Gary Gregory <garydgreg...@gmail.com>
> wrote:
>
>> I'm all for the Javadoc made to reflect the reality of the code. It is
>> fine
>> to have an additional section that points out Knuth and how we may want to
>> change things as a hint or request to contributors.
>>
>> Gary
>>
>> On Wed, Nov 7, 2018 at 10:52 AM Eric Barnhill <ericbarnh...@gmail.com>
>> wrote:
>>
>> > I read Kunth's "Art of Computer Programming 4.5.1" that is referenced
>> many
>> > times in the doc as the guidance for the commons-math/commons-numbers
>> > Fraction class. It is an interesting read. Also, for all the times it is
>> > cited in the doc, it is interesting that Fraction doesn't really use it
>> as
>> > implemented. Here is one example.
>> >
>> > Knuth is concerned about overflow in multiplication and division,
>> because
>> > numerator of f1 is multiplied by denominator of f2 and so forth, so he
>> > suggests a technique called "mediant rounding" that allows for
>> intermediate
>> > quantities in fraction multiplication to be rounded.
>> >
>> > It is a clever technique and probably works well, however the current
>> > Fraction class cites this chapter, then implements multiplication with
>> > BigInteger instead, ignoring this suggestion.
>> >
>> > First of all, the doc should be clear that the code is NOT following
>> 4.5.1,
>> > while it gives the opposite impression. And that's ok but the use of
>> > BigInteger creates additional inconsistency: Multiply and divide are
>> > accomplished using ArithmeticUtils.addAndCheck and
>> > ArithmeticUtils.mulAndCheck . These convert the relevant ints to longs,
>> > then perform the operation, then if the resulting long is greater than
>> the
>> > range of an int, throw an OverflowException. So some parts of Fraction
>> > check for overflow using longs and others use BigInteger.
>> >
>> > It seems to me that BigInteger is overkill here for the vast majority of
>> > practical uses of Fraction in a way that could be damaging for
>> performance.
>> > And furthermore, we already have a BigFraction class to handle cases
>> that
>> > require BigInteger.
>> >
>> > So, I propose rewriting the doc to say the opposite of what it currently
>> > says when appropriate, and get usages of BigInteger out of Fraction, use
>> > them only in BigFraction, and use the long-based ArithmeticUtils
>> methods to
>> > check for overflow and underflow in fraction addition and subtraction.
>> >
>> > Eric
>> >
>>
>
