Do you think we really even need a BigFraction class at all in the context
of these upgrades? Or should one of the Fraction factory methods just take
BigInteger argumentsm and all fractions use the lazy dynamic method of
calculation you are proposing?
I don't quite understand what you mean by this. The BigInteger class
provides flexibility and the ability to store and operate on
(practically) unlimited values, which Fraction does not have. The
Fraction class, on the other hand, is faster and more memory efficient,
due to its use of primitive values, which is an advantage over
BigFraction. I am even more confused by your suggestion seeing as it was
you who banned BigInteger from Fraction.addSub(Fraction, boolean) in
https://issues.apache.org/jira/browse/NUMBERS-79 , which, even though
you were not aware of it at that time, did not limit the method's
functionality in any way whatsoever (the use of int rather than long
did, however, but this is now fixed).
What I meant by lazy calculation was that the helper method does not
return the complete simple continued fraction expansion of the given
double value at once, because not all coefficients are needed to
approximate the number if the denominator limit is exceeded before the
last convergent is calculated (or if the convergent is close enough to
the actual value, in epsilon mode). Rather, the coefficients can be
queried one-by-one through an iterator, so that they are only calculated
when they are really needed. I don't see how this could replace or help
with any other functionality of the two fraction classes, though. It's
not like any state associated with the fraction instance itself would be
lazily evaluated. The calculation of the continued fraction expansion is
only relevant for the creation of the instance.
In fact, I have already written the helper class including Javadoc and
unit tests. It turns out that I implemented more methods than I actually
need, but the unneeded methods don't hurt, so I've left them in the class.
I am also finished with implementing the algorithm for approximating a
double number with a denominator limit. The algorithm itself is not very
complicated, but what I found all the more difficult was explaining
_why_ it works without the code comments becoming a thesis, but still in
a way that a person who is not an expert with continued fractions will
understand (which includes me, so I should hopefully be able to tell …).
I'm using some sections from the book Continued Fractions by Aleksandr
Khinchin thatare available in the preview on Google Books as a
reference, in addition to a question from Math Stackexchange.
Now I'm going to delete the unit tests asserting that the factory method
throws an exception if the double value is outside the int range >D
By the way, I think I'll also add a method that allows just an epsilon
to be specified without a parameter maxIterations, because currently,
the only public method for an epsilon-approximation also requires a
maximum number of iterations to be specified, which I think is
ridiculous, not least because the number of iterations seems to me to be
an implementation detail which the user is not necessarily interested
in, and there is no reason not to guarantee that the method will return
an appropriate approximation.
On 7/16/19 6:52 PM, Eric Barnhill wrote:
Sorry for the delay, I was on vacation.
On Fri, Jul 5, 2019 at 2:09 PM Heinrich Bohne <heinrich.bo...@gmx.at> wrote:
Hello!
I think a re-design of the factory method BigFraction.from(double,
double, int, int) is in order, because I see several problems with it:
First, having a separate fraction class intended to overcome the
limitations of the int range with a factory method (formerly a
constructor) for approximating double values that can only produce
denominators within the int range because it has been copy-pasted from
Fraction (where this code is still a constructor) seems a bit like a
joke. I think it would be more useful to have this method accept a
BigInteger as an upper bound for the denominator instead of an int.
Quite right! I wanted to look this up before replying. It absolutely makes
sense to use a BigInteger there.
Second, the method only calculates the convergents of the corresponding
continued fraction, but never its semi-convergents, so it doesn't
necessarily produce the best rational approximation of the double number
within the given bounds. For example, the test method
BigFractionTest.testDigitLimitConstructor() asserts that the method
calculates 3/5 as an approximation of 0.6152 with the upper bound for
the denominator set to 9, but 5/8 = 0.625 is closer to 0.6152 than 3/5 =
0.6. Since the method is already using continued fractions to
approximate fractional numbers, I think it would be a pity if it didn't
take advantage of them for all that they're worth.
Wow. That is indeed problematic, nice catch.
Finally, the documentation of the method rightfully acknowledges the
latter's confusing design, with the method's general behavior being
dependent on some of its arguments and the validity of these arguments
also being dependent on each other. However, a better way to solve this
problem than to simply hide the design from the public would be to
improve it, e.g. by extracting the functionality that is common to both
the "maxDenominator mode" and the epsilon mode (which is the calculation
of the continued fraction), and separating the differences in the
functionality of the two modes into distinct methods that call the
common functionality.
Yes absolutely.
My suggestion for the third point above would be to create a separate
class (not necessarily public) that provides an interface for
calculating simple continued fractions and their convergents (I see that
there's an abstract class ContinuedFraction, but I don't think it will
be useful, because all the methods only return double values, and the
class also requires that all coefficients can be explicitly calculated
based on their index). The class would ideally be able to calculate the
continued fraction dynamically/lazily, because only a limited number of
coefficients are needed to approximate a fractional number within given
bounds.
That would be awesome.
What I think could be useful is if the class stores a list of
the coefficients internally in addition to the current and previous
convergent (two consecutive convergents are needed to calculate the next
one recursively based on the next coefficient), and has methods like
addCoefficient(BigInteger) and removeLastCoefficient() for building a
continued fraction, and also a static method like
coefficientsOf(BigFraction) that returns an Iterator<BigInteger> that
computes the coefficients only as they are queried through the iterator,
so that they can then be passed to addCoefficient(BigInteger).
+1
The maxDenominator factory method could then just iterate over the
coefficients of the continued fraction representation of the passed
double and build the continued fraction from them until the denominator
of the current convergent exceeds the upper bound,
yes.
and the epsilon
method could iterate over the coefficients of both the lower and upper
bound's continued fraction representation until the coefficients start
to differ, at which point it can build the continued fraction of the
close enough approximation from all coefficients at once (this would
also prevent any loss of precision when repeatedly performing arithmetic
operations with floating-point values).
right.
Furthermore, this code could not only be used by the approximation
factory methods in BigFraction, but also by those in Fraction, possibly
adjusted so that not only the denominator must be within a given bound,
but also the numerator needs to be within the int range.
Any opinions or objections?
All expressed very clearly. This will be a major upgrade for the package.
Do you think we really even need a BigFraction class at all in the context
of these upgrades? Or should one of the Fraction factory methods just take
BigInteger argumentsm and all fractions use the lazy dynamic method of
calculation you are proposing?
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
For additional commands, e-mail: dev-h...@commons.apache.org