I was trying, out of curiosity, to find an efficient algorithm for the problem below which peaked my interest:
Let $r$ be a real number. Find an integer $k > 0$ such that $kr$ is "near" an integer. That is, for any $\epsilon > 0$, find $k$ such that $0 \leq \mathrm{frac}(kr) < \epsilon$, where $\mathrm{frac}(x)$ is the "mod 1" fractional part function, e.g. $\mathrm{frac}(2.3) = 0.3$.
This is the algorithm I came up with after a lot of thought:
- Assume $r$ is irrational (if $r$ is rational, the optimal solution is trivially the denominator) and $0 < r < 1$ since the integer part does not matter as it does not change the fractional part under multiplication by $k \in \mathbb{Z}$.
Then by a bisection argument:
$$r = \sum_{i = 1}^\infty \frac{a_i}{2^i} ~ ~ ~ \text{with} ~ a_i \in \{ -1, 1 \}$$
Now truncate this series to some term $m$, then $\lvert r - r_m \rvert < 2^{-m}$ and write:
$$r_m = \sum_{i = 1}^m \frac{a_i}{2^i} = \frac{1}{2^m} \sum_{i = 1}^m a^i 2^{m - i}$$
So $r_m = \frac{a}{2^m}$ with $a = \sum_{i = 1}^m a^i 2^{m - i}$. Note $\gcd{(a, 2^m)} = 1$ as the sum always contains a final $\pm 1$ term.
Then we can find a solution to the original problem with $r_m$ rational, by letting:
$$\mathrm{frac}(k r_m) = 2^{-m} ~ ~ \text{for some} ~ k \in \mathbb{Z}$$
$$k r_m + l = 2^{-m} + l ~ ~ \text{for some} ~ l \in \mathbb{Z}$$
$$k \frac{a}{2^m} + l = 2^{-m} + l$$
$$k a + 2^m l = 1 + 2^m l$$
$$k a \equiv 1 \pmod{2^m} ~ ~ \implies ~ ~ k \equiv a^{-1} \pmod{2^m}$$
Such that $k r_m$ is distance equal to $2^{-m}$ from an integer where $k$ is the modular inverse of $a$ in $2^m$.
So then I did some error analysis, and worked out that:
$\lvert r - r_m \rvert < 2^{-m}$ as seen earlier
$\left \lvert k r_m - l \right \rvert = 2^{-m}$ for some integer $l$
Therefore $\lvert k r - k r_m \rvert < k 2^{-m}$ and it follows that:
$$0 < \left \vert k r - l \right \rvert < \frac{k + 1}{2^m} = \epsilon$$
But then I kind of run into some sort of uncertainty principle, where for "most" $a$ and $m$, the modular inverse $k$ of $a$ in $2^m$ is fairly large, on the order of $2^m$, in such a way that the algorithm doesn't increase significantly in accuracy as $m \to \infty$. Basically for any $m$, the distribution of modular inverses in $2^m$ seems fairly arbitrary, so that low $\epsilon$ is very hard to achieve efficiently. For instance, this is a plot of the $\epsilon$ achievable for any $r$ in $2^8$:
Where the $x$-axis indicates the best approximation of $r = (2a + 1) \cdot 2^{-m}$ (only odd numerators are admissible).
And this is the plot for $m = 10$ (i.e. in $2^{10}$):
To combat this I thought of perturbing the approximation of $r_m$ with a small term $\frac{c}{2^m}$ (with $c$ even of course), in hopes of making $(a + c)^{-1} \mod{2^m}$ small. Unfortunately this decreases the accuracy (increases the error $\epsilon$) by a factor of $c$, so it's quickly not worth it on average, since $a$ is almost always not "close enough" to an element with a sufficiently small modular inverse to offset the loss of accuracy.
In other words, this algorithm seems to have exponential complexity for "almost all" inputs $r$, as for any $\epsilon > 0$, on average the lowest suitable $m$ appears to be $O\left(\epsilon^{-1}\right)$. Since the algorithm takes inverses in $2^m$, it would seem to be very inefficient. Needless to say, picking a different base does not help either.
So my question: is there a way this algorithm can be salvaged somehow, and if not, is there a known efficient algorithm that solves the problem, or is it known to be hard? Some keywords relating to this specific problem would be welcome too as I found no info about this on the internet (hard without prior references).
The continued fraction expansion method mentioned in comments should work. You can get it by the following algorithm:
$$b_0 = r $$ $$a_0 = \lfloor r \rfloor$$
$$b_1 = \frac{1}{r-a_0}$$ $$a_1 = \left \lfloor b_1 \right\rfloor$$
$$ \vdots$$
$$b_n = \frac{1}{b_{n-1} - a_{n-1}} $$ $$a_n = \left \lfloor b_n \right\rfloor$$
These are continued fraction expansion coefficients. You get a good rational approximation by truncating the expansion. Every other one of these is less than $r$ and every other bigger than $r$ so in your case, since you want the fractional part of $kr$ to be small, you should choose $k$ to be the denominator of the approximating rational number that is bigger than r:
$$r < \frac{s}{k} \Rightarrow rk < s.$$
EDIT: Sorry, my algorithm wasn't quite right, fixed it, for example if $r = \sqrt 2$: $$b_0 = \sqrt 2 = 1.414213562$$ $$a_0 = 1$$
$$b_1 = \frac{1}{1.414213562 -1} = 2.414213562$$ $$a_1 = 2$$
$$b_2 = \frac{1}{2.414213562 -2} = 2.414213562$$ $$a_2 = 2$$
So we have the truncation
$$[1 \space 2 \space 2] =1+ \frac{1}{ 2+ \frac{1}{2} } = \frac{7}{5} = 1.4$$
Now as you can see this is close to $\sqrt 2$.
Square roots are actually a special case where the expansion becomes periodic and actually $\sqrt 2 = [1 \space 2 \space 2\space 2\space 2 \dots]$, but this works for any number $r$.