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

Improve this question
$\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
    Commented Jan 23, 2014 at 16:20
  • $\begingroup$ Sorry, forgot to say that I have floating point numbers. $\endgroup$
    – rocksportrocker
    Commented Jan 23, 2014 at 17:04
  • $\begingroup$ $n=2$ is sufficient to do this. $\endgroup$
    – Sungjin Kim
    Commented 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
    Commented 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
    Commented Jan 24, 2014 at 7:27

0

Reset to default

You must log in to answer this question.