2
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

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

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Malcolm Regan Dec 22 '14 at 22:32
  • $\begingroup$ See my other answer. It is less efficient, but more exhaustive. $\endgroup$ – Mike Pierce Dec 22 '14 at 22:44
0
$\begingroup$

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
$\endgroup$
  • $\begingroup$ Thank you. I appreciate the implementation suggestion. I thought that approach would be more cumbersome than popular opinion on this forum is suggesting. $\endgroup$ – Malcolm Regan Dec 22 '14 at 22:52

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.