diophantine approximation - Finding irrational numbers in given interval

If $~\xi~$ is irrational number then it is known that the set $~\{ p \xi + q ~ | ~ p,q \in \mathbb{Z} \}~$ is dense in $~\mathbb{R}$. Thus given some reals $~a~$ and $~b~$ one can find integers $~p~$ and $~q~$ such that $~ a \leq p \xi + q < b~$. But how?

Being precise i have $~a,b,\xi > 0~$ and i'm searching for an algorithm to find a pair $~(p,q)~$ with $~p~$ positive and least possible, $~q~$ negative.

I don't expect anything much more efficient than brute force search but at least which bounds can we put on $~p~$ and $~q~$ to narrow the search space?

Answer

Let $[x]$ denote the largest integer not exceeding $x.$ Let $e \in R-Q.$

For $k\in N,$ define $d_k= e k-[e k]$ and define $k'$ as follows :

Let $l_k\in N$ where $l_k d_k<1<(1+l_k)d_k.$ Let $k'=-l_k k$ if $1-l_k d_k<(1+l_k)d_k-1.$ Otherwise let $k'=(1+l_k)k.$ $$\text {Observe that }\quad 0< d_{k'}

Let $k_1=1$ and let $k_{n+1}=k_n'.$ Now choose $a^*\in (a,b))-Z.$ Let $M$ be the least (or any) $n$ such that $d_{k_n}<\min (b-a^*,a^*-[a^*]).$ For brevity let $C=k_M$. $$\text {We have }\quad 0< C e-[C e]

Let $D\in N$ where $$(D-1)(C e-[C e])\leq a^*-[a^*]

The use of $a^*$ was to remove the need to treat the cases $a\in Z$ and $a\not \in Z$ separately.