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. 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. 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. 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. 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). 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, 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). 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? --------------------------------------------------------------------- To unsubscribe, e-mail: [hidden email] For additional commands, e-mail: [hidden email] |
Hello Heinrich.
Le ven. 5 juil. 2019 à 23:09, Heinrich Bohne <[hidden email]> a écrit : > > 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. > > 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. > > 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. > > 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. 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). > > 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, 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). > > 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? Thanks a lot for these suggestions. It seems like a plan towards better consistency, increased robustness and higher precision. Best, Gilles --------------------------------------------------------------------- To unsubscribe, e-mail: [hidden email] For additional commands, e-mail: [hidden email] |
In reply to this post by Heinrich Bohne
Sorry for the delay, I was on vacation.
On Fri, Jul 5, 2019 at 2:09 PM Heinrich Bohne <[hidden email]> 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? |
> 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 <[hidden email]> 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: [hidden email] For additional commands, e-mail: [hidden email] |
On Tue, Jul 16, 2019 at 2:41 PM Heinrich Bohne <[hidden email]>
wrote: > > 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. That's fine. > 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). > I don't know what you mean by "functionality" but constructing a BigInteger for every fraction multiplication uses up more memory and operations than necessary and scales poorly. BigIntegers are not fast. However, I understand why the previous coders incorporated a BigInteger and I'm not sure that you do. The reason it was done was because Knuth proved (as in mathematical proof) that a long is insufficient for certain fraction multiplications where both numerator and denominator are large ints; 65 rather than 64 bits are necessary and a long will not suffice. For me, these cases are so extreme and likely so rare that we might as well let them fail, report to the user that these cases need to be handled with BigFraction and leave it there. It could easily be handled in a try catch block and such a block would be high performance. That was the judgment I made and it is open to interpretation, provided such interpretation agrees with Knuth's proof. We are entitled to our own opinions but not our own facts. Anyway I think your approximation schemes sound good and implement them however you see fit. Eric |
> The reason it was done was because Knuth proved
> (as in mathematical proof) that a long is insufficient for certain fraction > multiplications where both numerator and denominator are large ints; 65 > rather than 64 bits are necessary and a long will not suffice. You seem to have missed my comment in ticket https://issues.apache.org/jira/browse/NUMBERS-79 , which you created – I don't have the book by D. Knuth, but I can only assume that the section referenced by the code talks about unsigned integers, because by the logic in the comment I left in the JIRA ticket, long values are **always** sufficient in Fraction.addSub(Fraction, boolean). But this is beside the point, I only mentioned it because I didn't understand why you suggested to remove the BigFraction class, and actually, I still don't, as the class BigFraction provides functionality that Fraction cannot have, both with and without my suggested alterations. On 7/17/19 2:29 AM, Eric Barnhill wrote: > On Tue, Jul 16, 2019 at 2:41 PM Heinrich Bohne<[hidden email]> > wrote: > >>> 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. > That's fine. > > >> 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). >> > I don't know what you mean by "functionality" but constructing a BigInteger > for every fraction multiplication uses up more memory and operations than > necessary and scales poorly. BigIntegers are not fast. > > However, I understand why the previous coders incorporated a BigInteger and > I'm not sure that you do. The reason it was done was because Knuth proved > (as in mathematical proof) that a long is insufficient for certain fraction > multiplications where both numerator and denominator are large ints; 65 > rather than 64 bits are necessary and a long will not suffice. For me, > these cases are so extreme and likely so rare that we might as well let > them fail, report to the user that these cases need to be handled with > BigFraction and leave it there. It could easily be handled in a try catch > block and such a block would be high performance. > > That was the judgment I made and it is open to interpretation, provided > such interpretation agrees with Knuth's proof. We are entitled to our own > opinions but not our own facts. > > Anyway I think your approximation schemes sound good and implement them > however you see fit. > > Eric > --------------------------------------------------------------------- To unsubscribe, e-mail: [hidden email] For additional commands, e-mail: [hidden email] |
It just occured to me that you might have misunderstood my sentence:
> 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 "which" was referring to your removal of BigInteger, not to the use of BigInteger prior to your edits, so what I meant to say was, by removing BigInteger, you did not limit the method's functionality. On 7/17/19 10:10 AM, Heinrich Bohne wrote: >> The reason it was done was because Knuth proved >> (as in mathematical proof) that a long is insufficient for certain >> fraction >> multiplications where both numerator and denominator are large ints; 65 >> rather than 64 bits are necessary and a long will not suffice. > > You seem to have missed my comment in ticket > https://issues.apache.org/jira/browse/NUMBERS-79 , which you created – I > don't have the book by D. Knuth, but I can only assume that the section > referenced by the code talks about unsigned integers, because by the > logic in the comment I left in the JIRA ticket, long values are > **always** sufficient in Fraction.addSub(Fraction, boolean). > > But this is beside the point, I only mentioned it because I didn't > understand why you suggested to remove the BigFraction class, and > actually, I still don't, as the class BigFraction provides functionality > that Fraction cannot have, both with and without my suggested > alterations. > > > On 7/17/19 2:29 AM, Eric Barnhill wrote: >> On Tue, Jul 16, 2019 at 2:41 PM Heinrich Bohne<[hidden email]> >> wrote: >> >>>> 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. >> That's fine. >> >> >>> 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). >>> >> I don't know what you mean by "functionality" but constructing a >> BigInteger >> for every fraction multiplication uses up more memory and operations >> than >> necessary and scales poorly. BigIntegers are not fast. >> >> However, I understand why the previous coders incorporated a >> BigInteger and >> I'm not sure that you do. The reason it was done was because Knuth >> proved >> (as in mathematical proof) that a long is insufficient for certain >> fraction >> multiplications where both numerator and denominator are large ints; 65 >> rather than 64 bits are necessary and a long will not suffice. For me, >> these cases are so extreme and likely so rare that we might as well let >> them fail, report to the user that these cases need to be handled with >> BigFraction and leave it there. It could easily be handled in a try >> catch >> block and such a block would be high performance. >> >> That was the judgment I made and it is open to interpretation, provided >> such interpretation agrees with Knuth's proof. We are entitled to our >> own >> opinions but not our own facts. >> >> Anyway I think your approximation schemes sound good and implement them >> however you see fit. >> >> Eric >> > > > --------------------------------------------------------------------- > To unsubscribe, e-mail: [hidden email] > For additional commands, e-mail: [hidden email] > > --------------------------------------------------------------------- To unsubscribe, e-mail: [hidden email] For additional commands, e-mail: [hidden email] |
So, I think the code I have so far is ripe for a pull request, so I
submitted one. I changed the contracts of the epsilon and max-denominator factory methods, because the old specifications were not very useful, especially that of the max-denominator method – the only guarantee you could get from it was that /some/ fraction with a denominator not greater than the specified maximum would be returned, without any relation to the double value that should be approximated. The simple continued fraction is now created from an exact BigFraction representation of the double value rather than with floating-point arithmetic on the double value itself, to preserve maximum precision (the old epsilon algorithm produces a fraction of 1/3 when passed the double value obtained from the expression 1.0/3.0 and an epsilon of 5 * 2^(-58), which is incorrect because the distance between the rational number 1/3 and its closest double representative is larger than 5 * 2^(-58); I added a corresponding unit test). The methods setLastCoefficient(BigInteger) and removeLastCoefficient() in the new class SimpleContinuedFraction are unused. I wrote this class before I implemented the algorithms, and I thought these methods might be useful in the max-denominator method, but this turned out not to be the case. However, from a design-perspective, these two methods complement the functionality of addCoefficient(BigInteger), so I thought their presence is still tolerable. I solved the problem with the maxIterations argument in the epsilon method by simply not limiting the number of iterations if this argument is negative. Maybe this parameter was necessary in the old algorithm which calculated the simple continued fraction with floating-point arithmetic, to prevent an infinite loop or something. On 7/17/19 10:20 AM, Heinrich Bohne wrote: > It just occured to me that you might have misunderstood my sentence: > >> 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 "which" was referring to your removal of BigInteger, not to the use > of BigInteger prior to your edits, so what I meant to say was, by > removing BigInteger, you did not limit the method's functionality. > > > On 7/17/19 10:10 AM, Heinrich Bohne wrote: >>> The reason it was done was because Knuth proved >>> (as in mathematical proof) that a long is insufficient for certain >>> fraction >>> multiplications where both numerator and denominator are large ints; 65 >>> rather than 64 bits are necessary and a long will not suffice. >> >> You seem to have missed my comment in ticket >> https://issues.apache.org/jira/browse/NUMBERS-79 , which you created – I >> don't have the book by D. Knuth, but I can only assume that the section >> referenced by the code talks about unsigned integers, because by the >> logic in the comment I left in the JIRA ticket, long values are >> **always** sufficient in Fraction.addSub(Fraction, boolean). >> >> But this is beside the point, I only mentioned it because I didn't >> understand why you suggested to remove the BigFraction class, and >> actually, I still don't, as the class BigFraction provides functionality >> that Fraction cannot have, both with and without my suggested >> alterations. >> >> >> On 7/17/19 2:29 AM, Eric Barnhill wrote: >>> On Tue, Jul 16, 2019 at 2:41 PM Heinrich Bohne<[hidden email]> >>> wrote: >>> >>>>> 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. >>> That's fine. >>> >>> >>>> 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). >>>> >>> I don't know what you mean by "functionality" but constructing a >>> BigInteger >>> for every fraction multiplication uses up more memory and operations >>> than >>> necessary and scales poorly. BigIntegers are not fast. >>> >>> However, I understand why the previous coders incorporated a >>> BigInteger and >>> I'm not sure that you do. The reason it was done was because Knuth >>> proved >>> (as in mathematical proof) that a long is insufficient for certain >>> fraction >>> multiplications where both numerator and denominator are large ints; 65 >>> rather than 64 bits are necessary and a long will not suffice. For me, >>> these cases are so extreme and likely so rare that we might as well let >>> them fail, report to the user that these cases need to be handled with >>> BigFraction and leave it there. It could easily be handled in a try >>> catch >>> block and such a block would be high performance. >>> >>> That was the judgment I made and it is open to interpretation, provided >>> such interpretation agrees with Knuth's proof. We are entitled to our >>> own >>> opinions but not our own facts. >>> >>> Anyway I think your approximation schemes sound good and implement them >>> however you see fit. >>> >>> Eric >>> >> >> >> --------------------------------------------------------------------- >> To unsubscribe, e-mail: [hidden email] >> For additional commands, e-mail: [hidden email] >> >> > > > --------------------------------------------------------------------- > To unsubscribe, e-mail: [hidden email] > For additional commands, e-mail: [hidden email] > > --------------------------------------------------------------------- To unsubscribe, e-mail: [hidden email] For additional commands, e-mail: [hidden email] |
I'm looking forward to reviewing your code within my limited knowledge,
however I can't guarantee a quick time frame since Apache GSoC mentor milestones are due next week and I think that could get time consuming. Thanks for the contribution, Eric On Thu, Jul 18, 2019 at 4:13 PM Heinrich Bohne <[hidden email]> wrote: > So, I think the code I have so far is ripe for a pull request, so I > submitted one. I changed the contracts of the epsilon and > max-denominator factory methods, because the old specifications were not > very useful, especially that of the max-denominator method – the only > guarantee you could get from it was that /some/ fraction with a > denominator not greater than the specified maximum would be returned, > without any relation to the double value that should be approximated. > > The simple continued fraction is now created from an exact BigFraction > representation of the double value rather than with floating-point > arithmetic on the double value itself, to preserve maximum precision > (the old epsilon algorithm produces a fraction of 1/3 when passed the > double value obtained from the expression 1.0/3.0 and an epsilon of 5 * > 2^(-58), which is incorrect because the distance between the rational > number 1/3 and its closest double representative is larger than 5 * > 2^(-58); I added a corresponding unit test). > > The methods setLastCoefficient(BigInteger) and removeLastCoefficient() > in the new class SimpleContinuedFraction are unused. I wrote this class > before I implemented the algorithms, and I thought these methods might > be useful in the max-denominator method, but this turned out not to be > the case. However, from a design-perspective, these two methods > complement the functionality of addCoefficient(BigInteger), so I thought > their presence is still tolerable. > > I solved the problem with the maxIterations argument in the epsilon > method by simply not limiting the number of iterations if this argument > is negative. Maybe this parameter was necessary in the old algorithm > which calculated the simple continued fraction with floating-point > arithmetic, to prevent an infinite loop or something. > > On 7/17/19 10:20 AM, Heinrich Bohne wrote: > > It just occured to me that you might have misunderstood my sentence: > > > >> 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 "which" was referring to your removal of BigInteger, not to the use > > of BigInteger prior to your edits, so what I meant to say was, by > > removing BigInteger, you did not limit the method's functionality. > > > > > > On 7/17/19 10:10 AM, Heinrich Bohne wrote: > >>> The reason it was done was because Knuth proved > >>> (as in mathematical proof) that a long is insufficient for certain > >>> fraction > >>> multiplications where both numerator and denominator are large ints; 65 > >>> rather than 64 bits are necessary and a long will not suffice. > >> > >> You seem to have missed my comment in ticket > >> https://issues.apache.org/jira/browse/NUMBERS-79 , which you created – > I > >> don't have the book by D. Knuth, but I can only assume that the section > >> referenced by the code talks about unsigned integers, because by the > >> logic in the comment I left in the JIRA ticket, long values are > >> **always** sufficient in Fraction.addSub(Fraction, boolean). > >> > >> But this is beside the point, I only mentioned it because I didn't > >> understand why you suggested to remove the BigFraction class, and > >> actually, I still don't, as the class BigFraction provides functionality > >> that Fraction cannot have, both with and without my suggested > >> alterations. > >> > >> > >> On 7/17/19 2:29 AM, Eric Barnhill wrote: > >>> On Tue, Jul 16, 2019 at 2:41 PM Heinrich Bohne<[hidden email]> > >>> wrote: > >>> > >>>>> 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. > >>> That's fine. > >>> > >>> > >>>> 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). > >>>> > >>> I don't know what you mean by "functionality" but constructing a > >>> BigInteger > >>> for every fraction multiplication uses up more memory and operations > >>> than > >>> necessary and scales poorly. BigIntegers are not fast. > >>> > >>> However, I understand why the previous coders incorporated a > >>> BigInteger and > >>> I'm not sure that you do. The reason it was done was because Knuth > >>> proved > >>> (as in mathematical proof) that a long is insufficient for certain > >>> fraction > >>> multiplications where both numerator and denominator are large ints; 65 > >>> rather than 64 bits are necessary and a long will not suffice. For me, > >>> these cases are so extreme and likely so rare that we might as well let > >>> them fail, report to the user that these cases need to be handled with > >>> BigFraction and leave it there. It could easily be handled in a try > >>> catch > >>> block and such a block would be high performance. > >>> > >>> That was the judgment I made and it is open to interpretation, provided > >>> such interpretation agrees with Knuth's proof. We are entitled to our > >>> own > >>> opinions but not our own facts. > >>> > >>> Anyway I think your approximation schemes sound good and implement them > >>> however you see fit. > >>> > >>> Eric > >>> > >> > >> > >> --------------------------------------------------------------------- > >> To unsubscribe, e-mail: [hidden email] > >> For additional commands, e-mail: [hidden email] > >> > >> > > > > > > --------------------------------------------------------------------- > > To unsubscribe, e-mail: [hidden email] > > For additional commands, e-mail: [hidden email] > > > > > > > --------------------------------------------------------------------- > To unsubscribe, e-mail: [hidden email] > For additional commands, e-mail: [hidden email] > > |
Sure, no problem, thanks for letting me know!
On 7/19/19 6:22 PM, Eric Barnhill wrote: > I'm looking forward to reviewing your code within my limited knowledge, > however I can't guarantee a quick time frame since Apache GSoC mentor > milestones are due next week and I think that could get time consuming. > > Thanks for the contribution, > Eric > > On Thu, Jul 18, 2019 at 4:13 PM Heinrich Bohne <[hidden email]> > wrote: > >> So, I think the code I have so far is ripe for a pull request, so I >> submitted one. I changed the contracts of the epsilon and >> max-denominator factory methods, because the old specifications were not >> very useful, especially that of the max-denominator method – the only >> guarantee you could get from it was that /some/ fraction with a >> denominator not greater than the specified maximum would be returned, >> without any relation to the double value that should be approximated. >> >> The simple continued fraction is now created from an exact BigFraction >> representation of the double value rather than with floating-point >> arithmetic on the double value itself, to preserve maximum precision >> (the old epsilon algorithm produces a fraction of 1/3 when passed the >> double value obtained from the expression 1.0/3.0 and an epsilon of 5 * >> 2^(-58), which is incorrect because the distance between the rational >> number 1/3 and its closest double representative is larger than 5 * >> 2^(-58); I added a corresponding unit test). >> >> The methods setLastCoefficient(BigInteger) and removeLastCoefficient() >> in the new class SimpleContinuedFraction are unused. I wrote this class >> before I implemented the algorithms, and I thought these methods might >> be useful in the max-denominator method, but this turned out not to be >> the case. However, from a design-perspective, these two methods >> complement the functionality of addCoefficient(BigInteger), so I thought >> their presence is still tolerable. >> >> I solved the problem with the maxIterations argument in the epsilon >> method by simply not limiting the number of iterations if this argument >> is negative. Maybe this parameter was necessary in the old algorithm >> which calculated the simple continued fraction with floating-point >> arithmetic, to prevent an infinite loop or something. >> >> On 7/17/19 10:20 AM, Heinrich Bohne wrote: >>> It just occured to me that you might have misunderstood my sentence: >>> >>>> 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 "which" was referring to your removal of BigInteger, not to the use >>> of BigInteger prior to your edits, so what I meant to say was, by >>> removing BigInteger, you did not limit the method's functionality. >>> >>> >>> On 7/17/19 10:10 AM, Heinrich Bohne wrote: >>>>> The reason it was done was because Knuth proved >>>>> (as in mathematical proof) that a long is insufficient for certain >>>>> fraction >>>>> multiplications where both numerator and denominator are large ints; 65 >>>>> rather than 64 bits are necessary and a long will not suffice. >>>> You seem to have missed my comment in ticket >>>> https://issues.apache.org/jira/browse/NUMBERS-79 , which you created – >> I >>>> don't have the book by D. Knuth, but I can only assume that the section >>>> referenced by the code talks about unsigned integers, because by the >>>> logic in the comment I left in the JIRA ticket, long values are >>>> **always** sufficient in Fraction.addSub(Fraction, boolean). >>>> >>>> But this is beside the point, I only mentioned it because I didn't >>>> understand why you suggested to remove the BigFraction class, and >>>> actually, I still don't, as the class BigFraction provides functionality >>>> that Fraction cannot have, both with and without my suggested >>>> alterations. >>>> >>>> >>>> On 7/17/19 2:29 AM, Eric Barnhill wrote: >>>>> On Tue, Jul 16, 2019 at 2:41 PM Heinrich Bohne<[hidden email]> >>>>> wrote: >>>>> >>>>>>> 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. >>>>> That's fine. >>>>> >>>>> >>>>>> 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). >>>>>> >>>>> I don't know what you mean by "functionality" but constructing a >>>>> BigInteger >>>>> for every fraction multiplication uses up more memory and operations >>>>> than >>>>> necessary and scales poorly. BigIntegers are not fast. >>>>> >>>>> However, I understand why the previous coders incorporated a >>>>> BigInteger and >>>>> I'm not sure that you do. The reason it was done was because Knuth >>>>> proved >>>>> (as in mathematical proof) that a long is insufficient for certain >>>>> fraction >>>>> multiplications where both numerator and denominator are large ints; 65 >>>>> rather than 64 bits are necessary and a long will not suffice. For me, >>>>> these cases are so extreme and likely so rare that we might as well let >>>>> them fail, report to the user that these cases need to be handled with >>>>> BigFraction and leave it there. It could easily be handled in a try >>>>> catch >>>>> block and such a block would be high performance. >>>>> >>>>> That was the judgment I made and it is open to interpretation, provided >>>>> such interpretation agrees with Knuth's proof. We are entitled to our >>>>> own >>>>> opinions but not our own facts. >>>>> >>>>> Anyway I think your approximation schemes sound good and implement them >>>>> however you see fit. >>>>> >>>>> Eric >>>>> >>>> >>>> --------------------------------------------------------------------- >>>> To unsubscribe, e-mail: [hidden email] >>>> For additional commands, e-mail: [hidden email] >>>> >>>> >>> >>> --------------------------------------------------------------------- >>> To unsubscribe, e-mail: [hidden email] >>> For additional commands, e-mail: [hidden email] >>> >>> >> >> --------------------------------------------------------------------- >> To unsubscribe, e-mail: [hidden email] >> For additional commands, e-mail: [hidden email] >> >> --------------------------------------------------------------------- To unsubscribe, e-mail: [hidden email] For additional commands, e-mail: [hidden email] |
Free forum by Nabble | Edit this page |