Re: Issue 55 in mpmath: implement continued fractions

[mpm...@googlecode.com]

Comment #10 on issue 55 by smichr: implement continued fractions
http://code.google.com/p/mpmath/issues/detail?id=55

Ondrej, when you say "we need some way how to choose the best answer" what
do you
mean? What are the constraints? Can you give an example of input and
desired output?

--
You received this message because you are listed in the owner
or CC fields of this issue, or because you starred this issue.
You may adjust your issue notification preferences at:
http://code.google.com/hosting/settings

[mpm...@googlecode.com]

Comment #11 on issue 55 by smi...@gmail.com: implement continued fractions
http://code.google.com/p/mpmath/issues/detail?id=55

btw, we have the tolerance keyword for nsimplify and the limit_denominator
method of Rational:

>>> a = float(53)/2420933
>>> nsimplify(a, tolerance=1e-6, rational=True)
1/45678
>>> Rational(a).limit_denominator(5000000)
53/2420933

[mpm...@googlecode.com]

Comment #12 on issue 55 by smi...@gmail.com: implement continued fractions
http://code.google.com/p/mpmath/issues/detail?id=55

def continued_fraction(r):
"""Calculate the continued fraction of the given Rational
or the Rational from the given continued fraction.

continued fractions are in the form [a0, a1, a2, a3, ...]
for a0 + 1/(a1 + 1/(a2 + 1/(a3 + ...

Any other input will raise a ValueError

Examples
========

>>> from sympy import Rational
>>> continued_fraction(Rational(3,14))
[0, 4, 1, 2]
>>> continued_fraction(_)
3/14
>>> continued_fraction(2 + _)
[2, 4, 1, 2]

"""
if isinstance(r, Rational):
p, q = r.p, r.q
rv = []
while q:
n = p // q
rv.append(int(n))
q, p = p - q*n, q
return rv
elif isinstance(r, list):
cf = r or [S.Zero]
rv = Integer(cf.pop())
while cf:
rv = Integer(cf.pop()) + S.One/rv
return rv
else:
raise ValueError

[mpm...@googlecode.com]

Comment #13 on issue 55 by alberhem...@gmail.com: implement continued
fractions
http://code.google.com/p/mpmath/issues/detail?id=55

In the minds of most people continued fractions are tied up with integers
and rationals. Not so for Euclid whose algorithm works perfectly well with
floating
point numbers. Actually he might might have been thinking of ratio's of
line segments, whit just fitting the smaller an integer number of times
onto the larger. This amounts to repeatedly splitting x into floor(x) and a
remainder.
If the remainder is zero the process ends.
x1 = floor(x)
x = 1/(x-x1)
x2 = floor(x)
x= 1/(x-x2)
Bottom line x = x1 + 1/(x2 + 1/(x3 _ ...)

A brilliant reference about cd is gopher.txt (google for it, it is
everywhere).


--
You received this message because this project is configured to send all
issue notifications to this address.
You may adjust your notification preferences at:
https://code.google.com/hosting/settings

[mpm...@googlecode.com]

Comment #14 on issue 55 by alberhem...@gmail.com: implement continued
fractions
http://code.google.com/p/mpmath/issues/detail?id=55

While I'm at it, I might as well show how its done without rationals:
-----------------
from sympy import *
from math import frexp

def contfrac( x):
while True:
n = floor(x)
yield int(n)
if n==x: return
x=1/(x-n)

def convergents(cf):
p, q, r, s = 1, 0, 0, 1
for c in cf:
p, q, r, s = c*p+r, c*q+s, p, q
yield p, q

def simplify(x, d=100):
p, q = 0, 0
for r, s in convergents(contfrac(x)):
if s > d and q:
break
p, q = r, s
return Rational(p, q)

print simplify(0.1)
print simplify(0.501)
print simplify(0.499)
print simplify(0.666)
print simplify(7.2323)
print simplify(3.1415926535897932)
print simplify(3.1415926535897932, 1)
print simplify(3.1415926535897932, 3000)

# (d is the maximum acceptable denominator)
--------------------------------------
This gives the exact same output as in message #6