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 <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
>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
For additional commands, e-mail: dev-h...@commons.apache.org
