7
$\begingroup$

Given a decimal number, which is positive but can be less than or greater than one, how to find out its best approximation by a ratio of two integers in a given range? For example, given a number a = 0.647437, I would like to find the ratio b/c that is closest to a, where b and c are integers in the common range 1 ~ 20. What can be one of the most concise ways to do this?

$\endgroup$
6
  • $\begingroup$ Look up Rationalize[]. $\endgroup$ Dec 9 '16 at 22:30
  • 3
    $\begingroup$ In[288]:= Select[Convergents[ContinuedFraction[0.647437]], Numerator[#] <= 20 && Denominator[#] <= 20 &][[-1]] Out[288]= 11/17 $\endgroup$ Dec 9 '16 at 22:40
  • $\begingroup$ @J. M.♦ I think it is not what I am looking for. I do not care much about the absolute precision of the result, but the best approximation out of the range I designate. For the 0.647437 number, I do not need 90/139, but 11/17 if the range is 1~20 or 2/3 if the range is 1~5. $\endgroup$
    – nanjun
    Dec 9 '16 at 22:40
  • 1
    $\begingroup$ perhaps f[r_, n_] := Divide@@Sort[Map[{Abs[Divide@@ #-r],#}&, Union[Flatten[Outer[List, Range[n], Range[n]],1]]]][[1,2]] where f[0.647437, 20] gives 11/7 and f[0.647437, 5] gives 2/3. Perhaps there is some way to search over all possible mathematica functions less than or equal to that length and which produce the same result to find the "most concise way" to do this. That would be an interesting tool to have. $\endgroup$
    – Bill
    Dec 9 '16 at 23:09
  • 1
    $\begingroup$ have you tried working with the second argument to Rationalize? $\endgroup$
    – george2079
    Dec 10 '16 at 0:18
7
$\begingroup$

Here is a brute-force version of bobby's answer:

Table[First[MinimalBy[FareySequence[k], Abs[0.647437 - #] &]], {k, {5, 20, 1000}}]
{2/3, 11/17, 101/156}
$\endgroup$
3
  • $\begingroup$ Yours at least reduces the fraction and interestingly uses the Farey sequence. +1 $\endgroup$
    – bobbym
    Dec 9 '16 at 23:34
  • $\begingroup$ It helps that all the fractions in the Farey sequence are already in lowest terms... $\endgroup$ Dec 9 '16 at 23:40
  • $\begingroup$ Damn you no!!! No brute force!!! Use ContinuedFraction, select an appropriate number of terms, then apply FromContinuedFraction $\endgroup$ Dec 10 '16 at 6:52
5
$\begingroup$

Try this

Minimize[{Abs[.647437 - a/b], 6 > a > 0, 6 > b > 0}, {a, b}, Integers]

({0.0192297, {a -> 2, b -> 3}})

Minimize[{Abs[.647437 - a/b], 21 > a > 0, 21 > b > 0}, {a, b}, Integers]

({0.000378176, {a -> 11, b -> 17}})

Minimize[{Abs[.647437 - a/b], 1001 > a > 0, 1001 > b > 0}, {a, b}, Integers]

(*{1.10256*10^-6, {a -> 404, b -> 624}}*)

$\endgroup$
2
  • 1
    $\begingroup$ Of course, you can do Divide @@ NArgMin[{Abs[.647437 b - a], 1001 > a > 0, 1001 > b > 0}, {a, b}, Integers] if all you want is the fraction itself. (Note the reformulation such that division is avoided in the objective function.) $\endgroup$ Dec 9 '16 at 23:38
  • $\begingroup$ @J. M. Very cunning +1, thanks. $\endgroup$
    – bobbym
    Dec 9 '16 at 23:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.