Mind that there is no need for estimates and backtracking when doing it in binary! Since the term q for solving the remainder r for any step as in the binomial

Mind that there is no need for estimates and backtracking when doing it in binary! Since the term q for solving the remainder r for any step as in the binomial r = x2 - 4p2 - q(4p + q) is either 1 or 0 in a base-2 system, evaluating the "fit" becomes merely a matter of testing a boolean value. (Therefor we can go for a straight-forward algorithm. No need for interpolations, here.)