Add first-cut at an approximation function (still needs rounding tweaks). Add continued fraction conversions.
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 @@
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 @@
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__())