Consider two irreducible fractions:
$r_1 = \frac{p_1}{q_1}$
$r_2 = \frac{p_2}{q_2}$
with $r_1 \ge 0$ and $r_2 \ge 0$.
How the modulo $\%$ is defined over rational numbers (I think that is $r_3$ such that $r_1 = r_2 \times n + r_3$ with $n$ a positive integer but I am not sure of that), and how to compute the numerator $p_3$ and the denominator $q_3$ from $p_1, q_1, p_2, q_2$ and using only the following operations on integers: $+, -, \times, /, \%, \text{gcd}(), \text{lcm}()$ ?
Answer
If you don't impose any condition on $n$ then clearly
$$r_3 = r_1 - n r_2$$
is a solution as $n$ goes over all the integers. If you want the one that minimizes $r_3$ then choose
$$ n = \left\lfloor \frac{r_1}{r_2}\right\rfloor$$
If you want the smallest $r_3$ in magnitude then round the ratio instead of flooring it, i.e
$$ n = \left\lfloor \frac{r_1}{r_2} + \frac{1}{2}\right\rfloor$$
If you program in C/C++ and similar programming language, the code would be
n = (p1 * q2)/(p2*q1); // Using floor
n = (p1 * q2 + ((p2*q1) >> 1)/(p2*q1); // Using rounding
No comments:
Post a Comment