I have two positive integers $x$ and $y$.
I need to calculate $\frac{100x}{x+y}$ and $\frac{100y}{x+y}$, which sum up to $100$ of course.
However, I can only perform integer division.
And since the results still need to sum up to $100$, I calculate one of them, and then calculate the other via "$1000$ minus the previous".
I'd like to know which one to choose such that the outcome will be as accurate as possible.
One problem that arises is how to even define accurate here (i.e., how to measure the accuracy of the outcome).
So let's define the accuracy as $p(x,y)=|\frac{x}{y}-\frac{x'}{y'}|$, where $x'$ and $y'$ are the two outcomes.
The smaller $p(x,y)$ is, the more accurate is the result of my computation.
So my question is, how exactly should I choose between these two options:
- Calculate $x'=\left\lfloor\frac{100x}{x+y}\right\rfloor$ and then $y'=100-x'$
- Calculate $y'=\left\lfloor\frac{100y}{x+y}\right\rfloor$ and then $x'=100-y'$
My initial though is to always choose the larger value first (i.e., calculate $a=\left\lfloor\frac{100\max(x,y)}{x+y}\right\rfloor$ and then $b=100-a$), because "less information" will be lost.
Couldn't find any counterexamples of that, so does anyone here happen to know a formal proof?
Thank you.
If I understand everything correctly, the conjecture is false. Sometimes the smaller value is better.
Example case: x = 1, y=2.
If we do the division with the larger value, y, then we get
$$y' = \lfloor \frac {200} 3 \rfloor = 66, x' = 100-y' = 34$$
The true ratio is $\frac 1 2,$ so our error is $|\frac 1 2 - \frac {34} {66} | = \frac 1 {66}.$
Compare with doing the division with the smaller value, $x,$ so we get
$$x' = \lfloor \frac {100} 3 \rfloor = 33, y' = 100-x' = 67$$
which gives an error of $|\frac 1 2 - \frac{33}{67}| = \frac 1 {134}.$ Smaller than doing the larger division!
If you graph the error function with fixed $x$ or $y$ and a particular method, it's really quite chaotic. For example, if $y=10$ then computing $y'$ is better for $x \in \{2, 4 \}$ while $x'$ is better for $x \in \{1, 3, 5,6,7,8,9 \}.$