[Python-ideas] Python Float Update

[Case Van Horsen]

On Sun, May 31, 2015 at 8:27 PM, David Mertz <mertz at gnosis.cx> wrote:

> What is the computational complexity of a hypothetical
> float.as_simplest_integer_ratio() method?  How hard that is to find is not
> obvious to me (probably it should be, but I'm not sure).
>
Here is a (barely tested) implementation based on the Stern-Brocot tree:

def as_simple_integer_ratio(x):
    x = abs(float(x))
    left = (int(x), 1)
    right = (1, 0)
    while True:
        mediant = (left[0] + right[0], left[1] + right[1])
        test = mediant[0] / mediant[1]
        print(left, right, mediant, test)
        if test == x:
            return mediant
        elif test < x:
            left = mediant
        else:
            right = mediant

print(as_simple_integer_ratio(41152/263))

The approximations are printed so you can watch the convergence.

casevh