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.

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.

share|improve this question
    
I would suggest a search for "inhomogeneous diophantine approximation." –  Gerry Myerson Jul 10 '11 at 11:12
    
See also Shreevatsa's answer to question 46100. –  Gerry Myerson Jul 11 '11 at 3:08
1  
I accepted an answer to this at Math Overflow: mathoverflow.net/questions/70035/… –  Keenan Pepper Jul 12 '11 at 17:44

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.