Как конвертировать поплавок в дробь?

Question

Это домашнее задание.Я хочу написать функцию для преобразования числа с плавающей точкой в ​​пару целых чисел: числитель и знаменатель.Например: float 0.5 должен быть преобразован в (1,2).

Я пытаюсь что-то сделать.(см. ниже), но, честно говоря, это выглядит не очень хорошо для меня.

// 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)

Как бы вы преобразовали число с плавающей точкой в ​​дробь?

Answer 1

Я создал код C на основе примера msbrogli. Защита от переполнения включена

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

Answer 2

Примите во внимание, что числа с плавающей точкой всегда представлены в компьютерах как дроби, знаменатель которых равен степени 2 (согласно IEEE 754, 32-разрядные числа имеют знаменатель 2 ^ 24, а 64-разрядные числа имеют знаменатель2 ^ 53.Но это действительно достаточное подмножество для различных численных алгоритмов, которые могут выполнять компьютеры;хотя эти алгоритмы всегда разрабатываются с учетом упомянутого ограничения.

Answer 3

Вы можете просто использовать Библиотека фракций .

Но, если вы хотите разработать алгоритм, вот предложение:

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

Answer 4

Смотрите мой ответ на очень похожий вопрос .В любом случае, я опубликую его здесь:

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;

Преобразовав число с плавающей точкой в ​​строковое значение, вы можете перебирать строку в обратном порядке до достижения десятичной точки.Каждая итерация представляет собой степень десяти, на которую вам нужно умножить исходное значение с плавающей запятой, чтобы получить значение с плавающей запятой со всеми нулями справа от десятичного числа.Знаменатель дроби будет равен десяти от рассчитанной вами степени (количества итераций).Вам нужно будет сократить его до минимальных сроков, что легко, если вы знаете GCD.