From cf10926088c1e8a4f2d3097e095fa0fd7d5d681a Mon Sep 17 00:00:00 2001
From: Raymond Hettinger <python@rcn.com>
Date: Thu, 24 Jan 2008 00:54:21 +0000
Subject: Add first-cut at an approximation function (still needs rounding
 tweaks).  Add continued fraction conversions.

---
 Lib/rational.py           | 36 ++++++++++++++++++++++++++++++++++++
 Lib/test/test_rational.py | 12 ++++++++++++
 2 files changed, 48 insertions(+)

diff --git a/Lib/rational.py b/Lib/rational.py
index 19e7f14..5d21a8f 100755
--- a/Lib/rational.py
+++ b/Lib/rational.py
@@ -172,6 +172,42 @@ class Rational(RationalAbc):
         else:
             return cls(digits, 10 ** -exp)
 
+    @classmethod
+    def from_continued_fraction(cls, seq):
+        'Build a Rational from a continued fraction expessed as a sequence'
+        n, d = 1, 0
+        for e in reversed(seq):
+            n, d = d, n
+            n += e * d
+        return cls(n, d)
+
+    def as_continued_fraction(self):
+        'Return continued fraction expressed as a list'
+        n = self.numerator
+        d = self.denominator
+        cf = []
+        while d:
+            e = int(n // d)
+            cf.append(e)
+            n -= e * d
+            n, d = d, n
+        return cf
+
+    @classmethod
+    def approximate_from_float(cls, f, max_denominator):
+        'Best rational approximation to f with a denominator <= max_denominator'
+        # XXX First cut at algorithm
+        # Still needs rounding rules as specified at
+        #       http://en.wikipedia.org/wiki/Continued_fraction
+        cf = cls.from_float(f).as_continued_fraction()
+        result = new = Rational(0, 1)
+        for i in range(1, len(cf)):
+            new = cls.from_continued_fraction(cf[:i])
+            if new.denominator > max_denominator:
+                break
+            result = new
+        return result
+
     @property
     def numerator(a):
         return a._numerator
diff --git a/Lib/test/test_rational.py b/Lib/test/test_rational.py
index 5ee7b7d..76757ba 100644
--- a/Lib/test/test_rational.py
+++ b/Lib/test/test_rational.py
@@ -135,6 +135,18 @@ class RationalTest(unittest.TestCase):
             TypeError, "Cannot convert sNaN to Rational.",
             R.from_decimal, Decimal("snan"))
 
+    def testFromContinuedFraction(self):
+        self.assertRaises(TypeError, R.from_continued_fraction, None)
+        phi = R.from_continued_fraction([1]*100)
+        self.assertEquals(round(phi - (1 + 5 ** 0.5) / 2, 10), 0.0)
+
+    def testAsContinuedFraction(self):
+        self.assertEqual(R.from_float(math.pi).as_continued_fraction()[:15],
+                         [3, 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14, 3, 3])
+
+    def testApproximateFromFloat(self):
+        self.assertEqual(R.approximate_from_float(math.pi, 10000), R(355, 113))
+
     def testConversions(self):
         self.assertTypedEquals(-1, trunc(R(-11, 10)))
         self.assertTypedEquals(-2, R(-11, 10).__floor__())
-- 
cgit v0.12