how can I minimise (n * y) (mod x) for known x and y, and for a given range of n?

Question

How can I minimise (n.y) (mod x), for known x and y, and for a given range of n?

($x$ and $y$ are actually the components of a 2D vector for a line for which I'm trying to generate a set of bounding integer points)

So, for example, if x = 61, y = 17, and n must be in the range 0 < n < 12, then minimum value of the modulo operation is at n = 11, i.e. (11 * 17) (mod 61) = 4.

If we changed the range to 0 < n < 9, the minimum value is then at n = 4, i.e. (4 * 17) (mod 61) = 7.

I need to be able solve this for arbitrary values, but within a known range (around +/- 3000000).

This is a practical question so if there is no direct solution (or if a direct solution is very complicated) then a numerical method may be preferrable.

Answer 1

Consider the map $n\longmapsto ny/x$. You want to find a value of $n$ in a given range such that this is almost an integer. Such a point is encoded by an integral point of $\mathbb Z^2$ very close to the linear subspace generated by $(1,y/x)$. Closest points of this form are given by continued fraction approximations: Develop $x/y$ as a continued fraction and choose a convergent $a/b$ with $n=\lambda b$ in your range for small $\lambda$. This $n$ does the job.

If you want positive minimal values, then only every other convergent works. In your example, one gets convergents 1/4 and 2/7 and $4\cdot 17=68\equiv 7\pmod 61,\ 7\cdot 17\equiv -3\pmod 61$. Thus $n=7$ is a better solution but the smallest representant modulo $61$ of $7\cdot 17$ is negative.

Answer 2

What I'm going to say is somewhat similar to Roland's answer but more precise in the case when the range for $n$ is given in the form of upper bound, i.e., $0 < n < N$.

Notice that $ny\bmod x = ny - kx$ for some integer $k$. We want to minimize $ny-kx$ that, if we disregard for a moment the sign, can be formulated as minimizing $$\left|n\frac{y}{x} - k\right|$$ over integer $n$ in the given range and arbitrary integer $k$.

It is known that if some $n,k$ give better approximation (in the sense of the above absolute value) than any other $n',k'$ with $n' < n$, then $\frac{k}{n}$ with necessity represents a convergent to $\frac{y}{x}$.

Therefore, a first good candidate for the anticipated $n$ is the largest denominator of a convergent $\frac{k}{n}$ for $\frac{y}{x}$ that fits the given range (i.e., $n < N$).

For such $n$, if we have $n\frac{y}{x} - k > 0$ (equivalently, $\frac{k}{n}<\frac{y}{x}$), then it is indeed a solution.

However, if $n\frac{y}{x} - k < 0$ (equivalently, $\frac{k}{n}>\frac{y}{x}$), then the solution is given by largest allowed denominator of a semi-convergent located between the preceding and subsequent convergents of $\frac{k}{n}$. That is, if $\frac{k'}{n'}, \frac{k}{n}, \frac{k''}{n''}$ are consecutive convergents, then $\frac{k'}{n'} < \frac{k''}{n''} < \frac{y}{x}$ and $n' < N \leq n''$. Then one needs to find a semi-convergent between $\frac{k'}{n'}$ and $\frac{k''}{n''}$ with the largest denominator smaller than $N$.

Answer 3

Ok, I thought a bit about the problem, and here is another idea. It does not provide an answer, but might give a new idea. Maybe even the sketched algorithm turns out to work well in practice.

Assume we want to find some $n \in \mathbb{Z}$ satisfying $C \le n \le D$ (for some constants $C$ and $D$, which can be assumed to be integers as well) such that $n\cdot y \pmod{x}$ is minimal under this condition.

For that, first use the Extended Euclidean Algorithm to compute the GCD $d$ of $x$ and $y$, as well as integers $A, B$ with $d = A x + B y$. Then we can write $d' = A' x + B' y$ with $d', A', B'$ if, and only if, $d' = d t$ for some $t \in \mathbb{Z}$, and $A' = A t + s y/d$, $B' = B t - s x/d$ with $s \in \mathbb{Z}$.

Hence, we want to make $t \in \mathbb{N}_{\ge 0}$ as small as possible, while keeping $C \le B t - s x/d \le D$ for some $s \in \mathbb{Z}$. Such an $s$ exists if, and only if, the closed interval $[(B t - D) \frac{d}{x}, (B t - C) \frac{d}{x}]$ contains an integer, or equivalently, if $\lceil(B t - D) \frac{d}{x}\rceil \le (B t - C) \frac{d}{x}$.

Now $\lceil\frac{a}{b}\rceil = \frac{a + (-a \pmod{b})}{b}$, whence $\lceil(B t - D) \frac{d}{x}\rceil = \frac{(B t - D) d + (-(B t - D) d \pmod{x})}{x}$. This is $\le (B t - C) \frac{d}{x}$ if, and only if, $(D - B t) d \pmod{x} \le (D - C) d$.

Therefore, an equivalent problem is finding the smallest $t \ge 0$ such that $$D - B t \pmod{\tfrac{x}{d}} \le D - C.$$

Note that without loss of generality, we can assume that $0 \le B \le \frac{x}{d}$; in fact, in almost every case, we have $B < \frac{x}{d}$ (the only exception is $d = x$ and $B = 1$, $A = 0$, in which $n \cdot y \pmod{x}$ is zero for all $n$). Hence, we can assume that $B d < x$. Moreover, since $1 = A \frac{x}{d} + B \frac{y}{d}$, we see that $B$ and $\frac{x}{d}$ are coprime. In particular, $-B t \pmod{\frac{x}{d}}$, $t \in \mathbb{N}_{\ge 0}$ iterates over every integer the interval $[0, \frac{x}{d})$, including $0$ itself; therefore, we can always find a solution $t$ satisfying $0 \le t < \frac{x}{d}$, which is not surprising when considering the original problem.

One could now proceed as follows, which might lead to an algorithm which is fast in practice (in case $x > (D - C) d$): compute several solutions $t$ by choosing some random $T \le B - C$ and computing $t$ such that $D - B t \equiv T \pmod{\frac{x}{d}}$ (i.e. choose $t \equiv (-T + D) \frac{y}{d} \pmod{\frac{x}{d}}$, since $\frac{y}{d}$ is the modular inverse of $B$ modulo $\frac{x}{d}$) and take the minimum $t'$ over all such $t$. Hoping that at least one of these solutions is small, we are left only with a small interval $[0, t']$ to check for smaller solutions.

[Note that this is a similar problem to the one we started with: we want to find $T \in [0, D - C]$ such that $(-T + D) \frac{y}{d} \pmod{\frac{x}{d}}$ is minimal, instead of finding $n \in [C, D]$ such that $n \frac{y}{d} \pmod{\frac{x}{d}}$ is minimal.]

When we assume that $T \mapsto (-T + D) B^{-1} \pmod{\frac{x}{d}}$ is "random", we can assume that the $t$'s we obtain are randomly distributed in the interval $[0, \frac{x}{d})$, whence $t'$ can be expected to be small. Hence, this algorithm is only faster than just tying all values for $n$ if $t'$ is less than $D - C$, but this can be determined by a simple comparism.