This is a homework problem. I want to write a function to convert a float to a pair of integers: numerator and denominator. For instance: float 0.5 should be converted to (1,2).
I am trying smth. (see below) but frankly it does not look great for me.
// f is the input float
int n = 1
while(fractional_part(f) > 0)
f *= 10;
n++
int m = f;
gcd = gcd(m, n)
return (m/gcd, n/gcd)
How would you convert a float to a fraction ?
You could just use Fraction library.
But, if you would like to develop the algorithm, here is a suggestion:
from math import floor
from fractions import gcd
def func(v, tol=1e-4):
"""
Don't handle negative values.
Use binary search to find the fraction of a float.
The algorithm is based in a very simple theorem: If a < b then a < (a+b)/2 < b.
"""
f = v - floor(v)
lo = (0, 1)
hi = (1, 1)
while True:
# mid = (lo + hi)/2
# if lo = a/b and hi = c/d, then mid = (ad+bc)/(2ad)
mid = (lo[0]*hi[1] + hi[0]*lo[1], 2*lo[1]*hi[1])
# gcd to reduce fraction
k = gcd(mid[0], mid[1])
mid = (mid[0]/k, mid[1]/k)
d = 1.*mid[0]/mid[1]
# are we close enough?
if abs(f - d) < tol:
break
# if we are above our goal, get high to middle
elif d > f:
hi = mid
# if we are under our goal, get lower to middle
else:
lo = mid
# Add integer part
mid = (mid[0] + int(floor(v))*mid[1], mid[1])
# Debug comparing to Fraction library solution.
#print v, mid, Fraction('%s' % v)
return mid