# Fractional part optimization algorithm

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

-
One approach is to look at the continued fraction expansion of $r$ and truncate it, which gives the best approximation of $r$ as a rational number $a/b$ with denominator at most $b$. Then $rb\approx a$. – Alex Becker Apr 3 '14 at 22:09
@AlexBecker Thanks, that helped a lot! – Thomas Apr 3 '14 at 22:52

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

-
Indeed, it works. I have to study the continued fraction to understand what property makes it so that whatever delta there is between the approximating rational and $r$, the distance between $rk$ and the nearest integer remains bounded. It's probably the "best approximation" part that I'm missing. Thanks! – Thomas Apr 3 '14 at 22:51