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 |
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] |
In reply to this post by Eric Barnhill
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 <[hidden email]> 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 > |
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 <[hidden email]> 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 <[hidden email]> > 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 > > > |
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 <[hidden email]> 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 <[hidden email]> > 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 <[hidden email]> >> 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 >> > >> > |
On Fri, 30 Nov 2018 15:56:54 -0800, Eric Barnhill wrote:
> 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. Does this mean that computations can "unpredictably" overflow (or throw an exception)? Is it acceptable, or should we enclose the problematic code in a "try" block and redo the computation with "BigInteger" when necessary? What is the performance hit of using "BigFraction" rather than "Fraction"? Are there use-cases that would need the ultimate performance from "Fraction" while not worry about overflow? Regards, Gilles > > > On Fri, Nov 9, 2018 at 4:33 PM Eric Barnhill <[hidden email]> > 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 >> <[hidden email]> >> 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 >>> <[hidden email]> >>> 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 >>> > >>> >> --------------------------------------------------------------------- To unsubscribe, e-mail: [hidden email] For additional commands, e-mail: [hidden email] |
>
> > Does this mean that computations can "unpredictably" overflow > (or throw an exception)? > The ArithmeticUtils() methods mulAndCheck and addAndCheck throw exceptions if there is overflow during primitive operations. That is the "check" part of the method name. > Is it acceptable, or should we enclose the problematic code in > a "try" block and redo the computation with "BigInteger" when > necessary? > > What is the performance hit of using "BigFraction" rather than > "Fraction"? > I once used BigDecimal for a project, it is great code but the performance is nothing close to using primitives. > Are there use-cases that would need the ultimate performance from > "Fraction" while not worry about overflow? > You would need a greatest common factor between the two fractions that was larger than 64 bits. Again, BigFraction is there for anyone worried about such a case and there is no significant performance hit to switching over to BigFraction compared to a Fraction class that was using BigInteger under the hood. But I suspect there would be a substantial performance gain if longs were being used under the hood for the Fraction class for the more common use case of smaller fractions. If it would be best practice, a bit of microbenchmarking could be done to check. A FractionOverflowException could be specifically tailored to this use case and the error message can suggest using BigFraction. Or as you suggest, the catch block could silently or with warning return a BigFraction. If we have class inheritance straight, and both Fraction and BigFraction have the exact same interface, this could be an elegant solution. Eric |
Hi Eric.
On Mon, 3 Dec 2018 10:01:39 -0800, Eric Barnhill wrote: >> >> >> Does this mean that computations can "unpredictably" overflow >> (or throw an exception)? >> > > The ArithmeticUtils() methods mulAndCheck and addAndCheck throw > exceptions > if there is overflow during primitive operations. That is the "check" > part > of the method name. > > >> Is it acceptable, or should we enclose the problematic code in >> a "try" block and redo the computation with "BigInteger" when >> necessary? >> >> What is the performance hit of using "BigFraction" rather than >> "Fraction"? >> > > I once used BigDecimal for a project, it is great code but the > performance > is nothing close to using primitives. > > >> Are there use-cases that would need the ultimate performance from >> "Fraction" while not worry about overflow? >> > > You would need a greatest common factor between the two fractions > that was > larger than 64 bits. > > Again, BigFraction is there for anyone worried about such a case and > there > is no significant performance hit to switching over to BigFraction > compared > to a Fraction class that was using BigInteger under the hood. But I > suspect there would be a substantial performance gain if longs were > being > used under the hood for the Fraction class for the more common use > case of > smaller fractions. If it would be best practice, a bit of > microbenchmarking > could be done to check. > > A FractionOverflowException could be specifically tailored to this > use case > and the error message can suggest using BigFraction. Or as you > suggest, the > catch block could silently or with warning return a BigFraction. If > we have > class inheritance straight, and both Fraction and BigFraction have > the > exact same interface, this could be an elegant solution. Maybe I misunderstood, but I thought that only intermediate results would require "BigInteger"; if the result needs to be converted to "BigFraction", than I'd favour raising an exception (with the advice which you mention). If later on someone comes up with a use-case for the alternate solution, we can revisit. Regards, Gilles > > Eric --------------------------------------------------------------------- To unsubscribe, e-mail: [hidden email] For additional commands, e-mail: [hidden email] |
Free forum by Nabble | Edit this page |