Decimal To Fraction of limited digits

[SLH]

Lets say i want to turn a decimal number into a fractional number.
But the limit is that the combined number of digits of the numerator and denominator is restricted to some constant.

How can i work out what the most accurate representation of the decimal is, staying within the digit limits?

[techgnome]

not sure you can.... can you elaborate a little more? Specifically the WHY??
It doesn't make sense.

(btw - there's a dec to frac method in the code bank that I posted sometime back... it'll convert the decimal to a fraction, but as for the number of digits, don't know).

-tg

[SLH]

One possible method i thought might work with a bit of alteration was to take an increasing number of significent figures into account from the decimal, then reduce each resulting fraction, checking the length and stopping when it gets too long.

e.g. decimal 0.123456789...., limit of 3 digits
0.1 -> 1/10 = 3 digits
0.12 -> 12/100 -> 3/25 = 3 digits
0.123 -> 123/1000 = 7 digits
> 3 digits so return '3/25'

Trouble with that is that if you continued you'd see that sometimes continuing results in a fraction with the same number of digits, but more accuracy. If you could prove that adding more digits never reduced the number of digits of the fraction (only ever equaled the fraction from one fewer decimal places) then this wouldn't be a problem.
e.g.

0.1234 -> 1234/10000 -> 617/5000 = also, 7 digits.

For the why, no reason. I don't need it, just wondered if an algorithm was possible. I suppose an application could be something like a graphical calculator or some other app where digits/screen space is at a premium, but really i can't think of a good application.

Really i just thought it might be an interesting problem to try and solve.

[techgnome]

ah... ok.... so since we're only dealing with theoreticals... I'm not sure there's a way to limit the digits AND get accuracy... you're sacrificing one for the other... take 1/10 for instance... if the limit was 2... you're going to get /10 .... which doesn't mean much... or 1/1 .... which isn't even close to 0.1 ..... and that's just thinking in simplistic terms... and I only see the disparity geting worse from there.

-tg

[SLH]

In that case it should say 1/9 which is as close as it can get with only 2 digits.

Perhaps it is impossible to do, unless someone else can think of another approach.

[jemidiah]

Well, an algorithm is possible--brute force would work, it would just be excruciatingly slow. As for a fast method, I feel like a linear or quadratic time algorithm based on Dynamic Programming exists, but I'd have to think for a good long time about it.

[techgnome]

I was with you right up until "quadratic"... then the mind went to mush...

-tg

[Logophobic]

In that case it should say 1/9 which is as close as it can get with only 2 digits.

Actually, 1/8 is closer. * Edit: I realize now that you were refering to the 1/10 that techgnome suggested
With 3 digits: 9/73
With 4 digits: 10/81 (this is best with less than 13 digits)

brute force would work, it would just be excruciatingly slow

That depends on how many digits you want to use. Looping the numerator from 1 to 9,999,999 takes only a fraction of a second and is sufficient to find the most accurate ratio with less than 15 digits.

[Spoo]

One possible "why" might be to in the case of TBill prices, which
are quoted in 1/32s. However, this should be considerably easier
than OP's scenario, since in this case, it is known beforehand what
level of granularity is allowed .. ie, 1/32.

Spoo

[jemidiah]

Thinking about it more, this problem is equivalent to solving integer linear programming in a special case:

Minimize, for (positive, for simplicity) integers a and b, given a decimal number constant x/y, the cost function (a/b)-(x/y) with 0=<a*b<10^n-1, b>0, and the cost function nonnegative.

Minimizing this cost function is equivalent to minimizing ay-bx, since

(a/b)*by-(x/y)*by = ay-xb, b and d assumed > 0.


I feel like this method would become quite powerful with repeated applications. With some clever reapplications, you may well be able to reduce full-on integer linear programming to it in polynomial time. But, this is all guesswork .

[Logophobic]

Unfortunately, that doesn't work due to the variable scaling of the cost function.

x = 123456789
y = 1000000000
x/y = 0.123456789


a = 1356669
b = 10989019
a/b = 0.1234567890000008189994029494
|a/b - x/y| = 8.189994029494E-16
|a*y - b*x| = 9

a= 9496673
b= 76923052
a/b = 0.123456788999999635999882064
|a/b - x/y| = 3.64000117936E-16
|a*y - b*x| = 28

Clearly, the second case has a lower cost, even though the scaled cost is greater. This is because the scale factor of the second is nearly 7 times greater than that of the first.

[jemidiah]

Doh, yup. Not the way to go, then. The bounds on a*b are also off. I got to thinking about trying prime factor combinations of the numerator and denominator. It might offer a speed boost over brute force, at least.