3
$\begingroup$

Given two nonzero real numbers $x$ and $y$ such that $y/x$ is irrational, a real number $z$ to be approximated, and a tolerance $\epsilon$, give me an algorithm that will provide coprime integers $a$ and $b$ such that $|ax + by - z| < \epsilon$.

Note that if the restriction that $a$ and $b$ be coprime is lifted, the problem becomes very simple. One possible algorithm is:

  • Find $a_1$ and $b_1$ such that $0 < a_1 x + b_1 y < \epsilon$ using the extended Euclidean algorithm.
  • Let $\displaystyle a = a_1 \left[ \frac{z}{a_1 x + b_1 y} \right]$ and $\displaystyle b = b_1 \left[ \frac{z}{a_1 x + b_1 y} \right],\,$ where $[\,\cdot\,]$ is the nearest integer function.

However, the integers $a$ and $b$ provided by this algorithm are usually not coprime. I'm looking for an algorithm that produces the same kind of approximation but guarantees that $a$ and $b$ are coprime.

  • 2
    I accepted an answer to this at Math Overflow: http://mathoverflow.net/questions/70035/searching-for-an-inhomogeneous-diophantine-approximation-algorithm2011-07-12

0 Answers 0