I'm trying to solve the following system of equations for $p$ and $q$, given fixed integers $x$, $y$ and $c$:
$$r = {{c x + p} \over {c y + q}} \ , \, \, \, r \in \mathbb{Z}$$
where
$$\{x, y, p, q, c\} \in \mathbb{Z}$$
$$0 \leq y \lt x$$
$$0 \leq \{p, q\} \lt c$$
$$c = 2^b$$
i.e. this is a fixed point fraction $x / y$, shifted by $b$ bits, with fractional adjustment terms $p$ and $q$ on the numerator and denominator. I'm trying to solve for the values of $p$ and $q$ that make the denominator evenly divide the numerator, or I need to know when there is no solution.
There will always a solution for some integer values $p$ and $q$, just not necessarily within the range $\left[0, c\right)$.
Often there is more than one solution. I am much more interested in knowing when there are no solutions than when there are one or more solutions, so if there is no easy way to find or enumerate solutions, but there's a way to quickly (ideally in $\mathrm O(1)$) determine when there are no solutions, it would solve my problem.
I have a feeling this is not a "fullblown" Diophantine equation problem, and that there's some nice simple trick involving modulo arithmetic or remainders, but I haven't been able to find it.
No comments:
Post a Comment