How to convert float to fraction?

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 i开发者_Python百科t 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

---

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.

---

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;
}

---

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.