[Pythonmac-SIG] Finding repeating decimals

[Laurent Pierron]

Josh English a écrit:
> I am working on a fraction class object and one of the things I would
> like it to do is convert a decimal to a fraction. The fraction class
> simply has a numerator and a denominator as well as methods to add,
> subract, mulitply, and divide them with other fractions. 
> 
> I thought that if I converted a number like 0.333333 to a string it
> should assume that it means 1/3, and I can do that, but I have two problems:
> 

An algorithm, I've just invented it, maybe need a scientific report to 
the academy of science :-)

Let x your number and x less than 1, you must find integers a and b as
a/b < x < (a+1)/b, if 1/b < epsilon then x is equivalent to a/b (you 
must have to simplify a/b with gcd) else
b' = b+1 and a' = a if x<(a+1)/b' else a' = a+1 and loop back.

You're staying in the interval because you compare x to (a+1)/(b+1) and 
a/b < (a+1)/(b+1) < (a+1)/b
The interval is more and more small because the wide of the interval is 
1/b, and b is decreasing at each step.

It sounds like some Newton algorithm, so I think I'm plagiating Newton.

An example of Python function to do that, with some optimizations but 
not so good because you can obtain an Error : "maximum recursion depth 
exceeded" :

def quotient(x,a=0,b=1,err=0.001):
         assert(0<x<1)
         # The answer is a/b
	if a-err<b*x<a+err: return a,b
         # The answer is (a+1)/b
	if a+1-err<b*x<a+1+err: return a+1, b
         # Too much err, go one step deeper
	a,b = a+1,b+1
	if x*b < a: return quotient(x,a-1,b,err)
	return quotient(x,a,b,err)

 >>> quotient(0.33)
(33, 100)
 >>> quotient(0.333)
(1, 3)
 >>> quotient(0.3333)
(1, 3)
 >>> quotient(0.133333)
(2, 15)
 >>> quotient(0.14285714285714285)
(1, 7)

-- 
Laurent PIERRON                    -*- mailto:Laurent.Pierron@loria.fr

INRIA-Lorraine / LORIA             -*-     bureau : B 042
615, rue du Jardin Botanique       -*- mobile/SMS : +33 6 72 23 03 80
B.P. 101                           -*-       voix : +33 3 83 58 17 47
54602 Villers les Nancy (France)   -*-        fax : +33 3 83 27 83 19