10
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Let me point you towards the proof of Thue's theorem in elementary number theory, where a variant of this problem comes up. $\endgroup$ Jun 30, 2010 at 6:11

3 Answers 3

8
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Roland, isn't it simply the Euclidean algo? $\endgroup$ Jun 14, 2010 at 15:11
  • $\begingroup$ I am not sure. Continued fraction expansions and the Euclidean algorithm are of course very close but I do not quite see how to apply the Euclidean algorithm for effectively solving this problem. $\endgroup$ Jun 14, 2010 at 15:16
  • $\begingroup$ Hmm, it's indeed not obvious... $\endgroup$ Jun 14, 2010 at 15:27
  • $\begingroup$ Wadim: The Extended Euclidean Algorithm produces a sequence of equations $d_m = a_m x + b_m y$, where the $d_m$ are strictly decreasing until reaching the GCD of $x$ and $y$. If I recall correctly, the quotients $-\frac{b_m}{a_m}$ are the covergents of the continued fraction expansion of $\frac{x}{y}$. Hence, if $-\frac{b_m}{a_m} > 0$, one can choose $n = \lambda |a_m|$ for a small $\lambda$, as suggested by Roland. $\endgroup$
    – felix
    Jun 23, 2010 at 0:13
4
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.