Finding a ratio from a set of discrete values

Question

For $x = p/q$, where $x$ is a known value between $0.000$ and $1.000$ rounded to the thousandths place, $p$ is an integer value between $0$ and $127$, and $q$ is an integer value between $0$ and $255$: what is $p$ and $q$? Or rather, how does one find all the possible ratios of $p$ and $q$ within these constraints that equal $x$?

For example, in the case that $x = 0.523$.

(I know the following because of excel)

$p=56$ and $q=107$; $56/107 = 0.52336448598 = 0.523$

$p=57$ and $q=109$; $57/109 = 0.52293577982 = 0.523$

$p=58$ and $q=111$; $58/111 = 0.52252252252 = 0.523$

How do I find $p$ and $q$ knowing only $x$ and the constraints of the problem?

That's the best i can phrase the problem in order for it to be appropriate for a mathematics forum. However, I figured it might be helpful to provide the context even though the details may be considered a little removed from the focus of this forum:

I have two digital rheostats arranged as a voltage divider that need to be written to so that the desired voltage at $V$-OUT is provided. I'm trying to find a way to algorithmically arrive at the values to which $R_1$ and $R_2$ should be set.

   1.000V
     |   
     |                  .----- V-OUT
     |                 /    
    |||               /       
 R1 |||<-----,-------X
    |||      |            
            |||          
         R2 |||<-----,   
            |||      |    
                     |
                     |
                    GND

$V$-OUT is $x$, $R_1$ is $p$, and the total resistance $(R_1+R_2)$ is $q$.

Answer 1

Given $x$, a ratio rounded to the nearest $0.001$, we want to find positive integers $p,q$ such that

$x-0.0005 \le \dfrac{p}{q} \le x+0.0005$, i.e. $(x-0.0005)q \le p \le (x+0.0005)q$.

For each $q$, we need to check if there is an integer $p$ which lies between $(x-0.0005)q$ and $(x+0.0005)q$. This is an interval of width $0.001q < 1$, so there is at most one such integer $p$.

If $\left\lfloor (x-0.0005)q\right\rfloor = \left\lfloor (x+0.0005)q\right\rfloor$, then there is no such integer.

But if $\left\lfloor (x-0.0005)q\right\rfloor < \left\lfloor (x+0.0005)q\right\rfloor$, then $p = \left\lfloor (x+0.0005)q\right\rfloor$ works.

We can find all possible values of $(p,q)$ using the following pseudocode:

For q = 1,...,255 
{
    If floor[(x-0.0005)q] < floor[(x+0.0005)q] 
    {
        Set p = floor[(x+0.0005)q] 
        Display (p,q)
    }
}

This is faster than looping over all $2^{15}$ possible values of $p,q$, but even that can be done quickly.

Note that there is no a solution with $1 \le p \le 127$ and $1 \le q \le 255$ for the following values of $x$:

0.001, 0.002, 0.003, 0.334, 0.499, 0.501, 0.666, 0.993, 0.994, 0.995, 0.996, 0.997, 0.998, 0.999

Answer 2

Since $x$ has to be rounded to the thousandths place, it would be best to start with $x$ as the a rational number with denominator $1000$ and simplify from there until it fits in your constraints. For example, if $x = 0.432$, you're algorithm could proceed: $$ \frac{432}{1000} = \frac{2\times 2\times 2\times 2\times 3\times 3\times 3} {2\times 2\times 2\times 5\times 5\times 5} = \frac{2\times 3\times 3\times 3}{5\times 5\times 5} = \frac{54}{125} $$ so you would have $p = 54$ and $q = 125$. If the prime factorization doesn't cancel nicely, you will have to do some optimization because there will not be a $p$ and $q$ such that $\frac{p}{q}$ exactly equals $x$.

Answer 3

Since your constraints do not imply that many possibilities, you could just calculate them all and then find the best one. For your given value of x:

pBest = 0
qBest = 1
for p in [0..127]
  q = round(p/x)
  if (q >= 255 OR q < 0)
    continue
  if (abs(x - p/q) < abs(x - pBest/qBest))
    pBest = p
    qBest = q