# Decimals -> Fraction strings, my solution

François Pinard pinard at iro.umontreal.ca
Wed May 17 04:10:58 CEST 2000

```kain at cableadmin.com (Scott) writes:

> I've come up with one solution to my problem.  Its probably quite
> inefficient, but it does what I need for now.  Feel free to
> tear it apart and/or give any advice on how to better implement it.

OK, taken!  As a kind of rest, I tried to do it as well, as I was teased
by the fact your solution limits the denominator to be 2**N * 5**M.

> This code will take either a number or a string (ie '0.5') and return
> a string of the fraction (ie '1/2').  Here it is:

The code below defines `fraction(VALUE, TOLERANCE)', and return a string
representing the "simplest" fraction approximating VALUE, a float, with
an error not exceeding TOLERANCE, also a float which should not be too
close to zero (or else, the task may become impossible to achieve).

The value of `pi' was approximated by 3 in old times.  We often used 22:7
in school, probably you did that as well.  I later learned that 355:113
was a more precise approximation, and an easy one to remember.  We can
find all these values with `fraction'!   See:

>>> fraction(3.14159265359, 1)
'3:1'
>>> fraction(3.14159265359, 0.1)
'22:7'
>>> fraction(3.14159265359, 0.01)
'22:7'
>>> fraction(3.14159265359, 0.001)
'333:106'
>>> fraction(3.14159265359, 0.0001)
'333:106'
>>> fraction(3.14159265359, 0.00001)
'355:113'
>>> fraction(3.14159265359, 0.000001)
'355:113'
>>> fraction(3.14159265359, 0.0000001)
'103993:33102'
>>> fraction(3.14159265359, 0.00000001)
'103993:33102'
>>> fraction(3.14159265359, 0.000000001)
'103993:33102'
>>> fraction(3.14159265359, 0.0000000001)
'312689:99532'
>>> fraction(3.14159265359, 0.00000000001)
'833719:265381'

Here is the code, which is rather short, after all.  You may even delete
`__repr__' to make it shorter, but it makes debugging fun.  For example:

>>> ContinuedFraction(3.14159265359, 0.00000000001)
3+1/(7+1/(15+1/(1+1/(292+1/(1+1/(1+1/(1+1/(2))))))))

I do not think GCD is necessary, but I did not prove this to myself.
Also, the continued fraction may sometimes start with `0+' which can be
simplified out, but it was not worth doing in this given application.

def fraction(value, tolerance=0):
return '%d:%d' % ContinuedFraction(value, tolerance).eval()

class ContinuedFraction:

def __init__(self, value, tolerance):
integer = int(value)
residual = value - integer
self.integers = [integer]
while residual != 0 and abs(value - float(self)) > tolerance:
residual = 1.0 / residual
integer = int(residual)
residual = residual - integer
self.integers.insert(0, integer)

def __repr__(self):
import string
text = map(str, self.integers)
text.reverse()
return string.join(text, '+1/(') + ')' * (len(self.integers) - 1)

def __float__(self):
num, den = self.eval()
return float(num) / float(den)

def eval(self):
num, den = 1, 0
for integer in self.integers:
num, den = integer * num + den, num
return num, den

--
François Pinard   http://www.iro.umontreal.ca/~pinard

```

More information about the Python-list mailing list