Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

enter image description here

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}$):

enter image description here

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

share|improve this question
    
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 at 22:09
    
@AlexBecker Thanks, that helped a lot! –  Thomas Apr 3 at 22:52

1 Answer 1

up vote 1 down vote accepted

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

share|improve this answer
    
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 at 22:51

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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