algorithm to convert decimal to fraction expression

Question

supposing I have a decimal like

0.30000000000000027

What would be the best algorithm to know the same number expressed as a fraction So given certain x find y that satisfies x=1/y in c or haskell

I was thinking

 1/3> 0.30 >1/4

Iterating left and right side til one of them converges and > becomes = so first iteration would look like

1/1  >  0.30000000000000027  > 1/somethinghere
1/2  >  0.30000000000000027  > 1/increase or decrease this 
1/3  >  0.30000000000000027 ...

I want to clarify that I could easily do

0.30000000000000027  =  30000000000000027/  10^17

but I want to do

0.30000000000000027 = 1/x

In c or haskell

Not all numbers can be thus expressed, for example, 0.8 = 4/5. — Koterpillar, Apr 06 '13 at 06:13
yes got it but if algorithm does not converge, then I have a number with this quality — edgarmtze, Apr 06 '13 at 06:15
Then you just want a fraction simplification algorithm, see, i.e. http://stackoverflow.com/questions/7777142/how-to-simplify-a-fraction. — Koterpillar, Apr 06 '13 at 06:18
Every fraction will be between `1/n` and `1/(n+1)`, so just iterate until you find such a pair. — Barmar, Apr 06 '13 at 06:19
@Koterpillar No, that assumes he already has a fraction. He's trying to find the fraction in the first place. — Barmar, Apr 06 '13 at 06:20
why dont you do `y = 1.0/x'? i.e `1.0/0.30000whatever` will give the number? — Koushik Shetty, Apr 06 '13 at 06:20
well, I was even thinking that adding a imaginary number or something like that may solve the issue on those cases, maybe I am wrong — edgarmtze, Apr 06 '13 at 06:27
Imaginary numbers solve problems with roots, they have nothing to do with multiplication and division. — Barmar, Apr 06 '13 at 06:34
Possible duplicate of [Algorithm for simplifying decimal to fractions](http://stackoverflow.com/questions/5124743/algorithm-for-simplifying-decimal-to-fractions) — MT0, May 10 '16 at 14:49

score 4 · Answer 1 · answered Apr 06 '13 at 06:22

4

Voila (converts almost properly to a normal fraction):

int gcd(int a, int b)
{
    if (a == 0) return b;
    if (b == 0) return a;

    if (a > b)
        return gcd(b, a % b);
    else
        return gcd(a, b % a);
}

struct frac {
    int num;
    int denom;
};

struct frac to_frac(double x, int precision)
{
    int denom = 1;
    for (int i = 0; i < precision; i++) {
        denom *= 10;
    }

    int num = x * denom + 0.5; // hack: round if imprecise
    int gcdiv = gcd(num, denom);

    struct frac f;
    f.num = num / gcdiv;
    f.denom = denom / gcdiv;

    return f;
}

answered Apr 06 '13 at 06:22

1

Sidenote: this is not production-ready, some refining is needed if you want it to work in all circumstances - that's left as an exercise, this much code should be enough to get OP started. – Apr 06 '13 at 06:28
1

He wants his numerator always to be 1. His statement about possibly using imaginary numbers shows how confused he is about math. – Barmar Apr 06 '13 at 06:33
1

@Barmar ... (but you **can't express any fraction with a numerator of 1!**) – Apr 06 '13 at 06:34
1

@Barmar Still, you're right, but what he wants is impossible, I'm not even sure that's exactly what he wants. This is the closest answer I can imagine that makes sense. – Apr 06 '13 at 06:35

score 3 · Accepted Answer · answered Apr 06 '13 at 11:00

3

Have you looked into continued fractions? They give very good approximations of numbers.

answered Apr 06 '13 at 11:00

md2perpe

3,372
2
18
22

score 2 · Answer 3 · answered Apr 06 '13 at 06:27

2

Don't know haskell, here it is in pseudo-code:

raw_denom = 1/x;
print "1/" floor(raw_denom) " >= " x " >= 1/" ceil(raw_denom)

answered Apr 06 '13 at 06:27

Barmar

741,623
53
500
612

`1/1 >= 0.8 >= 1/2` IT all depends on the (ill defined) design requirements, but that meets some interpretation. In Haskell: `func x = let raw_denom = 1/x in putStrLn $ "1/" ++ show (floor raw_denom) ++ " >= " ++ show x ++ " >= 1/" ++ show (ceiling raw_denom)` – Thomas M. DuBuisson Apr 06 '13 at 06:43
My answer prints what he wrote after "I was thinking" in his question. – Barmar Apr 06 '13 at 06:45

algorithm to convert decimal to fraction expression

3 Answers3