We have a number $f$, and we are looking for an integer $n$ such that $f^2 + 2f n = m$, where $m$ is an integer. This can be represented as two integer linear programs - program 1: $$\max{2nf - m} \\ f^2+2f n \leq m \\ 0\leq n \leq R$$ and program 2: $$\min{2nf - m} \\ f^2+2f n \geq m \\ 0\leq n \leq R$$
Integer linear programming with two variables can be solved efficiently, so this gives an efficient algorithm.
To know how many of digits of $f$ are necessary we will look at its convergents, until the denominator of one is more than $5 R$. Let's call that number $x$. Then we have $x = f + \varepsilon$ for $|\varepsilon| \leq \frac{1}{25 R^2}$, so for the real $n$ we have $2n x + x^2 = 2nf + 2n\varepsilon + f^2 + 2f\varepsilon + \varepsilon^2 = 2nf + f^2 + \varepsilon_2$ for $|\varepsilon_2| \leq \frac{2R+2}{25 R^2}$, but for other values of $m$ we have $2x m + x^2 = 2x n + x^2 + 2x (m-n)$ whose distance from an integer is at least $|\frac{1}{5R} - \varepsilon_2|$, and for $R > 4$, $\varepsilon_2$ is necessarily smaller.
As for the complexity, because the values in the continued fraction are bounded by $R$, we only need $O(\log R)$ digits. I'm not sure about the state of the art, but using a naive algorithm the complexity is $O(\log^2 R)$