Comment convertir un flotteur en fraction?

Question

Ceci est un problème de devoirs. Je veux écrire une fonction pour convertir un float en une paire d'entiers: numérateur et dénominateur. Par exemple: float 0.5 devrait être converti en (1,2).

Je suis en train d'essayer. (voir ci-dessous) mais franchement ça ne me va pas très bien.

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

Comment convertir un flottant en fraction?

Answer 1

Vous pouvez simplement utiliser Fraction library.

Mais, si vous souhaitez développer l'algorithme, voici une 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 

Answer 2

Prenez en compte que les flotteurs sont toujours représentés en interne dans les ordinateurs sous forme de fractions, dénominateur est une puissance de 2 (selon IEEE 754, les flottants de 32 bits ont un dénominateur de 2^24, et les flottants de 64 bits ont un dénominateur de 2^53).

Une conséquence particulière est que les ordinateurs ne peuvent pas représenter la plupart des nombres réels , mais seulement un sous-ensemble limité de rationnels numéros. Mais c'est en effet un sous-ensemble suffisant pour divers algorithmes numériques que les ordinateurs peuvent effectuer; Bien que ces algorithmes sont toujours conçus avec la limitation mentionnée en tête.

Answer 3

See my answer to a very similar question. Je vais republier ici de toute façon:

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; 

En convertissant le flotteur à une valeur de chaîne, vous pouvez parcourir la chaîne dans l'ordre inverse jusqu'à la virgule. Chaque itération est une puissance de dix par laquelle vous devez multiplier la valeur à virgule flottante d'origine pour obtenir une valeur à virgule flottante avec tous les zéros à droite de la décimale. Le dénominateur de la fraction sera de dix au pouvoir que vous avez calculé (le nombre d'itérations). Vous devrez le réduire aux termes les plus bas, ce qui est facile si vous connaissez le GCD.

Answer 4

J'ai créé du code C basé sur l'exemple de msbrogli. Protection contre le débordement est inclus

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