0
$\begingroup$

suppose I have a finite set of real numbers ${r_1, \ldots r_n \in \mathbf{R} }$ and a single real number $x \in \mathbf{R}$. Is there a fast algorithm for finding integer numbers ${i_1, \ldots i_n \in \mathbf{Z}}$ such that

$ \left| i_1 r_1 + \ldots + i_n r_n - x \right| < \epsilon $

For a given $\epsilon > 0$ ? I know that $i_1 r_1 + \ldots + i_n r_n = 0$ iff $i_j = 0 \,\forall j$.

$\endgroup$
6
  • $\begingroup$ What kind of real numbers are you talking about? If you mean rationals, then you could multiply by the common denominator then apply Bézout's identity. On the other hand, general real numbers are inherently hard to handle in algorithms. If you have floating point numbers in some computer in mind, then you should make that explicit as well. $\endgroup$
    – MvG
    Jan 23, 2014 at 16:20
  • $\begingroup$ Sorry, forgot to say that I have floating point numbers. $\endgroup$ Jan 23, 2014 at 17:04
  • $\begingroup$ $n=2$ is sufficient to do this. $\endgroup$ Jan 24, 2014 at 0:23
  • $\begingroup$ i707107: That's clearly not always true if there are irrational numbers involved. eg it's not true if $ x $ is rational and the ratio of $ r _{1} $ to $ r _{2} $ is irrational. $\endgroup$
    – mc0e
    Jan 24, 2014 at 7:20
  • $\begingroup$ Floating point numbers are inherently rational, but it becomes important to ask if the answers are constrained by what can be represented (eg number of digits), or if approximate answers are acceptable to some level of accuracy. $\endgroup$
    – mc0e
    Jan 24, 2014 at 7:27

0

Your Answer

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