I think you can avoid the Newton-Raphson altogether, since cubic is solvable in radicals.
Here is the complete algorithm (working under constraints outlined in the problem), in Mathematica:
Clear[PositiveCubicRoot];
PositiveCubicRoot[p_, q_, r_] :=
Module[{po3 = p/3, a, b, det, abs, arg},
b = ( po3^3 - po3 q/2 + r/2);
a = (-po3^2 + q/3);
det = a^3 + b^2;
If[det >= 0,
det = Power[Sqrt[det] - b, 1/3];
-po3 - a/det + det
,
(* evaluate real part, imaginary parts cancel anyway *)
abs = Sqrt[-a^3];
arg = ArcCos[-b/abs];
abs = Power[abs, 1/3];
abs = (abs - a/abs);
arg = -po3 + abs*Cos[arg/3]
]
]
Then
In[222]:= PositiveCubicRoot[-2.52111798, -71.424692, -129.51520]
Out[222]= 10.499
However, if the Newton-Raphson method must be used, then a good initial guess is imperative. Binary division is a good method to isolate the root in the case at hand.
We start with an arbitrary point $x$, I chose $x=1$, and double it while the polynomial
at that point is negative. Then do binary division a certain number of times (the code below does it twice). Ultimately, polish it off with Newton-Raphson iterations:
In[283]:=
NewtonRaphsonStartingPoint[{p_, q_, r_}] := Module[{x1=0, x2=1,f1,f2,xm,fm},
f1 = r + x1 (q + (p + x1) x1);
While[(f2 = r + x2 (q + (p + x2) x2)) <= 0,
x1 = x2; f1 = f2; x2 = 2 x2];
Do[xm = (x1 + x2)/2; fm = r + xm (q + (p + xm) xm);
If[fm <= 0, f1 = fm; x1 = xm, f2 = fm; x2 = xm], {i, 2}];
(f2 x2 - f1 x1)/(f2 - f1)
];
NewtonRaphsonIterate[{p_, q_, r_}, x0_Real] :=
FixedPoint[
Function[x, x - (r + x (q + (p + x) x))/(q + (2 p + 3 x) x)], x0]
In[285]:=
NewtonRaphson[p_, q_, r_] :=
NewtonRaphsonIterate[{p, q, r}, NewtonRaphsonStartingPoint[{p, q, r}]]
In[286]:= NewtonRaphson[-2.52111798, -71.424692, -129.51520]
Out[286]= 10.499
$$\begin{align}
f(x) &= N - \sqrt\frac Nx\cdot\left\lfloor\sqrt{Nx}\right\rfloor + \sqrt{\frac Nx} - \left\lfloor\sqrt\frac Nx\right\rfloor \\
&\ge N - \sqrt\frac Nx\cdot\sqrt{Nx} + \sqrt\frac Nx - \sqrt\frac Nx \\
&= 0,
\end{align}$$
with equality holding if and only if $\sqrt{Nx}$ and $\sqrt{Nx^{-1}}$ are both integers.
The necessary and sufficient conditions on $x$ can be characterized in terms of in terms of the prime factorization of $N$. Let the prime factorization be $N = p_1^{n_1} p_2^{n_2} \cdots p_k^{n_k}$. Now $x$ must be rational, and it cannot contain any prime other than these $p_i$ as a factor in its reduced form, otherwise one of $Nx$ and $Nx^{-1}$ would not be an integer. So it is of the form $x = p_1^{m_1} p_2^{m_2} \cdots p_k^{m_k}$, where the $m_k$ are integers. Then $Nx = p_1^{n_1+m_1} p_2^{n_2+m_2} \cdots p_k^{n_k+m_k}$ is a square integer if and only if $m_i \equiv n_i \pmod 2$ and $m_i \ge -n_i$. Similarly, $Nx^{-1}$ is a square integer if and only if $m_i \equiv n_i \pmod 2$ and $m_i \le n_i$. That means $m_i \in \{-n_i, -n_i+2, \ldots, n_i-2, n_i\}$, and that's all there is to it.
For example, when $N=6$, we have $N = 2^1 3^1$, and there are four zeroes for $x$, namely $2^{-1}3^{-1} = \frac16$, $2^1 3^{-1} = \frac23$, $2^{-1}3^1 = \frac32$, and $2^1 3^1 = 6$.
Best Answer
What you describe is a reasonable approach.
Your first step is often called root isolation, and your second step is (in a sense) root polishing. You can Google these terms to learn more.
In your second step, the end-points of your interval bracket a root. It’s a good idea to use a polishing algorithm that keeps the root bracketed. The standard Newton-Raphson algorithm does not preserve bracketing, but it’s easy to adapt it so that it does. There’s a decent implementation in the Numerical Recipes book.