Hacker News new | ask | show | jobs
by dunham 1039 days ago
The pascal code cuts when it hits a certain accuracy (passed in as an argument).
1 comments
eesmith 1039 days ago
The main issue I see is that the algorithm - unlike the mediant version - does not generate maximally successive accurate approximations.

Yes, you can stop the algorithm at a certain accuracy, but that doesn't mean you can't get better for that given accuracy.

Consider the pi = 3.14159265359 case, and you want it precise to 1/1,000,000. The float64 algorithm gives 1146408/364913 or 5419351/1725033 because:

     ...
    1146408/364913 = 3.141592653591404 (diff: -1.403765992336048e-12)
      --- want a solution here ---
    5419351/1725033 = 3.1415926535898153 (diff: 1.8474111129762605e-13)
     ...
The mediant method, on the other hand, gives an intermediate solution:

  >>> import fractions
  >>> fractions.Fraction("3.14159265359").limit_denominator(1000000)
  Fraction(3126535, 995207)
  >>> float(fractions.Fraction("3.14159265359").limit_denominator(1000000))
  3.1415926535886505
That's a difference of -1.3495871087343403e-12 which is more accurate than 1146408/364913, and is not a solution found by the other algorithm.

Or, if you want a denominator of 364913 or 1725033 you can do that with mediants:

  >>> fractions.Fraction("3.14159265359").limit_denominator(364913)
  Fraction(1146408, 364913)
  >>> fractions.Fraction(3.14159265359).limit_denominator(1725033)
  Fraction(5419351, 1725033)
Another issue is the numerical range. Consider the input "1.5e-318". It causes overflow in the float, decimal, and fraction implementations I gave:

  % python frac.py 1.5e-318 --method float
  Using float64 for '1.5e-318'
  Traceback (most recent call last):
    File "frac.py", line 40, in <module>
      print("solution:", to_frac(Q))
    File "tmp.py", line 31, in to_frac
      Dc = Db * int(Zb) + Da
  OverflowError: cannot convert float infinity to integer


  % python frac.py 1.5e-318 --method fraction
  Using fractions for '1.5e-318'
   1/666666666... many 6s removed ...6666 = 1/666666666... many 6s removed ...6666
      (diff: -1/666 .. more 6s removed ... 6600.. even more zeros removed ...00)
  Traceback (most recent call last):
    File "frac.py", line 40, in <module>
      print("solution:", to_frac(Q))
    File "frac.py", line 35, in to_frac
      if float(N) / float(Dc) == float(X):
  OverflowError: int too large to convert to float
while with the mediant solution I don't need to worry about the input range beyond infinity and NaN:

  >>> from fractions import Fraction
  >>> Fraction(1.5e-318).limit_denominator(1000000)
  Fraction(0, 1)
(I used the float() calls to ensure the fraction and decimal methods stop at the limits of float64. If I remove them I still end up with numbers like 3/2E319 which would not be representable as a Turbo Pascal integer, while the Turbo Pascal mediant implementation would not have a problem.)

Finally, the mediant solution is easier to implement.

link