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
i've created C code based on msbrogli's example. Protection against overflow is included
/*******************************************************************/
/* calculate a num/den fraction to given float with smallest error */
/*******************************************************************/
RFIXED128 CalcFractionToFloat(FLOAT64 in_Value, FLOAT64 in_MaxError, UINT64 in_MaxValue)
{
/* locals */
UINT64 lv_Gcd;
FLOAT64 lv_Now;
FLOAT64 lv_NowError;
FLOAT64 lv_Whole;
FLOAT64 lv_Fract;
RFIXED128 lv_NewAvg;
RFIXED128 lv_Avg;
RFIXED128 lv_Lo;
RFIXED128 lv_Hi;
// (default) max accepted error
if (in_MaxError <= 0)
in_MaxError = 1e-6;
// get the whole part
lv_Whole = floor(in_Value);
// get the fractional part, this is in range of (lo..hi) aka (0..1)
lv_Fract = in_Value - lv_Whole;
// init lower boundary (LoNum/LoDen = 0/1 = 0)
lv_Lo.num = 0;
lv_Lo.den = 1;
// init upper boundary (HiNum/HiDen = 1/1 = 1)
lv_Hi.num = 1;
lv_Hi.den = 1;
// init output in case the first avg calculation overflows immediate
lv_Avg.num = 0;
lv_Avg.den = 1;
// loop until error is below the limit
for (;;)
{
// calculate the average:
//
// average = (lo+hi)/2
//
// = (LoNum/LoDen + HiNum/HiDen) / 2
//
// = ((HiDen*LoNum)/(HiDen*LoDen) + (LoDen*HiNum)/(LoDen*HiDen)) / 2
//
// = (HiDen*LoNum + LoDen*HiNum) / (HiDen*LoDen*2)
//
lv_NewAvg.num = lv_Hi.den * lv_Lo.num + lv_Lo.den * lv_Hi.num;
lv_NewAvg.den = lv_Hi.den * lv_Lo.den * 2;
// check overflow if one is specified
if (in_MaxValue)
if (lv_NewAvg.num > in_MaxValue || lv_NewAvg.den > in_MaxValue)
break;
// calc greatest common divisor to reduce the average value
lv_Gcd = CalcGreatestCommonDivisor64(lv_NewAvg.num, lv_NewAvg.den);
// reduce the average value
lv_Avg.num = lv_NewAvg.num / lv_Gcd;
lv_Avg.den = lv_NewAvg.den / lv_Gcd;
// reconstruct the value represented by this fraction
lv_Now = (FLOAT64)lv_Avg.num / (FLOAT64)lv_Avg.den;
// new absolute fractional error
lv_NowError = fabsl(lv_Now - lv_Fract);
// reached the goal?
if (lv_NowError < in_MaxError)
break;
// binary search for better result
if (lv_Now > in_Value)
lv_Hi = lv_Avg;
else
lv_Lo = lv_Avg;
}
// add whole part
lv_Avg.num += (INT)lv_Whole * lv_Avg.den;
// return the result
return lv_Avg;
}
-- additional code/definitions
// as numerator/denominator - 64.64 signed FIXED-type, 128bit total
// - fraction is given by numerator/denominator
// - alias is 'rational'
typedef struct
{
INT64 num; // numerator, value aka whole part
UINT64 den; // denominator, fraction aka dividing part
} RFIXED128;
UINT64 CalcGreatestCommonDivisor64(UINT64 in_V1, UINT64 in_V2)
{
/* locals */
INT64 lv_PrevValQ;
INT64 lv_PrevValR;
INT64 lv_DivValQ;
INT64 lv_DivValR;
// validate
if (!in_V1 || !in_V2)
return FALSE;
// divide larger by smaller
if (in_V1 > in_V2)
{
// v1 is larger
lv_DivValQ = in_V1;
lv_DivValR = in_V2;
}
else
{
// v2 is larger
lv_DivValQ = in_V2;
lv_DivValR = in_V1;
}
// keep dividing the previous remainder with the new reminder until remainder is zero
// - this is called "Euclid's algorithm"
while (lv_DivValR > 0)
{
// remember previous remainder
lv_PrevValQ = lv_DivValQ;
lv_PrevValR = lv_DivValR;
// divide again
DivMod64(lv_DivValQ, lv_DivValR, &lv_DivValQ, &lv_DivValR);
// previous remainder is next quotient
lv_DivValQ = lv_PrevValR;
}
// the last remainder is the greatest common divisor
return lv_PrevValR;
}
Take into account that floats are always internally represented in computers as fractions, denominator of which is a power of 2 (as per IEEE 754, 32-bit floats have denominator of 2^24, and 64-bit floats have denominator of 2^53).
One particular consequence of this is that computers cannot represent most of real numbers, but only a limited subset of rational numbers. But this is indeed sufficient subset for various numerical algorithms which computers can perform; although these algorithms are always designed with the mentioned limitation in mind.
See my answer to a very similar question. I'll repost it here anyway:
ostringstream oss;
float num;
cin >> num;
oss << num;
string numStr = oss.str();
int i = numStr.length(), pow_ten = 0;
while (i > 0) {
if (numStr[i] == '.')
break;
pow_ten++;
i--;
}
for (int j = 1; j < pow_ten; j++) {
num *= 10.0;
}
cout << static_cast<int>(num) << "/" << pow(10, pow_ten - 1) << endl;
By converting the float to a string value, you can iterate through the string in reverse order until you reach the decimal point. Each iteration is a power of ten by which you need to multiply the original floating point value to obtain a floating point value with all zeros to the right of the decimal. The denominator of the fraction will be ten to the power that you calculated (the number of iterations). You'll need to reduce it to lowest terms, which is easy if you know the GCD.
