division - Python 2.7 - Continued Fraction Expansion - Understanding the error -

this question has answer here:

• is floating point math broken? 20 answers

i've written code calculate continued fraction expansion of rational number n using euclidean algorithm:

from __future__ import division  def contfract(n):     while true:         yield n//1         f = n - (n//1)         if f == 0:             break         n = 1/f 

if n 3.245 function never ending apparently f never equals 0. first 10 terms of expansion are:

[3.0, 4.0, 12.0, 3.0, 1.0, 247777268231.0, 4.0, 1.0, 2.0, 1.0]

which error since actual expansion only:

[3;4,12,3,1] or [3;4,12,4]

what's causing problem here? sort of rounding error?

the issue you're testing f == 0 (integer 0) never true floats. loop goes on forever.

instead, check precision of equivalent 0 (which can wrong sometimes):

>>> __future__ import division >>> >>> def contfract(n): ...     while true: ...         yield n//1 ...         f = n - (n//1) ...         if f < 0.0001:  # or whatever precision consider close enough 0 ...             break ...         n = 1/f ... >>> >>> list(contfract(3.245)) [3.0, 4.0, 12.0, 3.0, 1.0] >>> 

and in case f can negative, either -0.0001 < f < 0.0001 or abs(f) < 0.0001. considered inaccurate, see linked article.

and wrt comment use int(n) instead of n//1 because it's clearer - slightly less efficient:

>>> import timeit >>> timeit.timeit('n = 2.245; n//1', number=10000000) 1.5497028078715456 >>> timeit.timeit('n = 2.245; int(n)', number=10000000) 1.7633858824068103