# Finding a ratio from a set of discrete values

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$.

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

• Thank you. This is very helpful insight into this problem for me. – Malcolm Regan Dec 22 '14 at 22:52

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$.

• I do understand the easily simplify-able cases. What do you mean by optimization and would it help me in the case where x=0.523 (as 523/1000 cannot be simplified)? I am not really interested in getting p/q to exactly equal x. but finding a p/q that when rounded to the thousandths place equals x. – Malcolm Regan Dec 22 '14 at 22:32
• See my other answer. It is less efficient, but more exhaustive. – Mike Pierce Dec 22 '14 at 22:44

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

• Thank you. I appreciate the implementation suggestion. I thought that approach would be more cumbersome than popular opinion on this forum is suggesting. – Malcolm Regan Dec 22 '14 at 22:52