diff options
author | Raymond Hettinger <python@rcn.com> | 2008-01-24 00:54:21 (GMT) |
---|---|---|
committer | Raymond Hettinger <python@rcn.com> | 2008-01-24 00:54:21 (GMT) |
commit | cf10926088c1e8a4f2d3097e095fa0fd7d5d681a (patch) | |
tree | 62335adb430d706e1c5cd7b9caae5eb0a08450c2 /Lib/rational.py | |
parent | 9acc387bcfca60f4f641f52914e70714034b085c (diff) | |
download | cpython-cf10926088c1e8a4f2d3097e095fa0fd7d5d681a.zip cpython-cf10926088c1e8a4f2d3097e095fa0fd7d5d681a.tar.gz cpython-cf10926088c1e8a4f2d3097e095fa0fd7d5d681a.tar.bz2 |
Add first-cut at an approximation function (still needs rounding tweaks). Add continued fraction conversions.
Diffstat (limited to 'Lib/rational.py')
-rwxr-xr-x | Lib/rational.py | 36 |
1 files changed, 36 insertions, 0 deletions
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 |