Working with increased precision of irrational numbers in python
<p>I am attempting to do a <a href="https://en.wikipedia.org/wiki/Continued_fraction" rel="nofollow">continued fraction derivation</a> of irrational numbers, e.g. sqrt(13), with Python. I have obtained a pretty good solution which is accurate for the first 10 or so iterations:</p>

<ol>
<li>Set the original number as current remainder</li>
<li>Append floor of current remainder to list of coefficients</li>
<li>Define new remainder as reciprocal of current remainder minus floor</li>
<li>Go to step 2 unless new remainder is 0</li>
</ol>

<p>This works very well, except for later iterations, where the <code>float</code> precision is producing erroneous coefficients. Once a single coefficient is off, the remaining will automatically be as well.</p>

<p>My question is therefore if there is a way to treat irrational numbers, e.g. sqrt(13), like placeholders (for later substitution) or in a more precise manner?</p>

<p>My current code is as below:</p>

<pre><code>import math


def continued_fraction(x, upper_limit=30):
    a = []
    # should in fact iterate until repetitive cycle is found 
    for i in range(upper_limit):
        a.append(int(x))
        x = 1.0/(x - a[-1])
    return a


if __name__ == '__main__':
    print continued_fraction(math.sqrt(13))
</code></pre>

<p>With the resulting output:</p>

<pre><code>[3, 1, 1, 1, 1, 6, 
    1, 1, 1, 1, 6, 
    1, 1, 1, 1, 6, 
    1, 1, 1, 1, 6, 
    1, 1, 1, 1, 7, 2, 1, 4, 2]
</code></pre>

<p>And I know for a fact, that the resulting output should be 3, followed by infinite repetitions of the cycle (1, 1, 1, 1, 6), as per <a href="https://projecteuler.net/problem=64" rel="nofollow">Project Euler Problem 64</a> (which I'm trying to solve).</p>

<p>You might cast an eye over <a href="https://rosettacode.org/wiki/Continued_fraction#Python" rel="nofollow">https://rosettacode.org/wiki/Continued_fraction#Python</a>. It uses the Fractions and Itertools modules.</p>

python precision