# [numbers] Fraction() and Knuth 4.5.1 -- overflow, BigInteger, long, and rounding Classic List Threaded 8 messages Open this post in threaded view
|

## [numbers] Fraction() and Knuth 4.5.1 -- overflow, BigInteger, long, and rounding

 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
Open this post in threaded view
|

## Re: [numbers] Fraction() and Knuth 4.5.1 -- overflow, BigInteger, long, and rounding

 Hi. On Wed, 7 Nov 2018 09:52:30 -0800, Eric Barnhill 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 Thanks a lot for the fact-checking. Gilles --------------------------------------------------------------------- To unsubscribe, e-mail: [hidden email] For additional commands, e-mail: [hidden email]
Open this post in threaded view
|

## Re: [numbers] Fraction() and Knuth 4.5.1 -- overflow, BigInteger, long, and rounding

Open this post in threaded view
|

## Re: [numbers] Fraction() and Knuth 4.5.1 -- overflow, BigInteger, long, and rounding

Open this post in threaded view
|

## Re: [numbers] Fraction() and Knuth 4.5.1 -- overflow, BigInteger, long, and rounding

Open this post in threaded view
|