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$
  • $\begingroup$ Look up Rationalize[]. $\endgroup$ – J. M. is away 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$ – Daniel Lichtblau 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$
  • $\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$ – J. M. is away 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$ – J. Antonio Perez 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$
  • 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$ – J. M. is away 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.