The standard positive base $b$ square root algorithm is:
- Split the input digits into groups of two (such that the decimal point is one of the split points).
- Initialize $\mathit{remainder}$ to $0$ and $\mathit{output}$ to $0$.
- Append the next digit group to the end of $\mathit{remainder}$.
- Find the largest digit $d$ such that $(2 \cdot b \cdot \mathit{output} + d) \cdot d \le \mathit{remainder}$.
- Subtract $(2 \cdot b \cdot \mathit{output} + d) \cdot d$ from $\mathit{remainder}$.
- Append $d$ to $\mathit{output}$.
- While more digits are desired, repeat from step 3.
The reason this fails in a negative base is that step 4 is really looking for the first digit of the real-number solution to
$$\begin{align*}
(b \cdot \mathit{output} + x)^2 &= b^{2n} \cdot \mathit{input} \\
\iff (2 \cdot b \cdot \mathit{output} + x) \cdot x &= b^{2n} \cdot \mathit{input} - (b \cdot \mathit{output})^2,
\end{align*}$$
where $\mathit{remainder}$ is maintained as the integer part of the right side. A negative base presents four difficulties:
- Because we’re outputting one digit at a time, on any given iteration, output may be of either sign, which means that $(2 \cdot b \cdot \mathit{output} + x) \cdot x$ may be either increasing or decreasing in $x$.
- The first digit of $x$ may now be greater than $x$. The set of numbers starting with a digit $d$ is no longer $[d.000000\cdots, d.999999\cdots) = [d, d + 1)$, but rather $[d.909090\cdots, d.090909\cdots) = \left[d + \frac{b}{1 - b}, d + \frac{1}{1 - b}\right)$.
- For the same reason, we might sometimes need more than two input digits to produce one output digit: $\sqrt{02.9921_{-10}} = 1.09_{-10}$ starts with $1$, but $\sqrt{02.81_{-10}} = 2.9_{-10}$ starts with $2$.
- Without taking into account whether we’re outputting a digit of positive or negative place value, it’s easy to inadvertently produce the negative square root instead of the positive square root.
One strategy for addressing these difficulties involves building $\mathit{remainder}$ from the digits of $\mathit{input} \cdot (1 - b)$ instead of $\mathit{input}$. The points at which the first digit of $x$ changes are described by $x = d + \frac{1}{1 - b}$:
$$\left(2 \cdot b \cdot \mathit{output} + d + \frac{1}{1 - b}\right) \cdot \left(d + \frac{1}{1 - b}\right) = b^{2n} \cdot \mathit{input} - (b \cdot \mathit{output})^2 \\
\begin{multline}
\iff (2 \cdot b \cdot \mathit{output} + d) \cdot d \cdot (1 - b) + 2 \cdot b \cdot \mathit{output} + 2 \cdot d + \frac{1}{1 - b} \\
= b^{2n} \cdot \mathit{input} \cdot (1 - b) - (b \cdot \mathit{output})^2 \cdot (1 - b).
\end{multline}$$
The pre-decimal part of the right side also changes here (since the right side equals an integer plus $\frac{1}{1 - b}$), so maintaining that pre-decimal part as $\mathit{remainder}$ guarantees sufficient precision to pin down the first digit of $x$ correctly.
Taking this all into account, we can update the algorithm for negative base $b$ as follows:
- Multiply the input by $1 - b$.
- Split the resulting digits into groups of two (such that the decimal point is one of the split points).
- Initialize $\mathit{remainder}$ to $0$ and $\mathit{output}$ to $0$.
- Append the next digit group to the end of $\mathit{remainder}$.
- If $\mathit{output} = 0$ and we’re outputting a digit of negative place value, set $d = 0$.
- Otherwise if $\mathit{output} \le 0$, find the smallest digit $d$ such that $$(2 \cdot b \cdot \mathit{output} + d) \cdot d \cdot (1 - b) + 2 \cdot b \cdot \mathit{output} + 2 \cdot d \ge \mathit{remainder}.$$
- Otherwise, find the smallest digit d such that $$(2 \cdot b \cdot \mathit{output} + d) \cdot d \cdot (1 - b) + 2 \cdot b \cdot \mathit{output} + 2 \cdot d < \mathit{remainder}.$$
- Subtract $(2 \cdot b \cdot \mathit{output} + d) \cdot d \cdot (1 - b)$ from $\mathit{remainder}$.
- Append $d$ to $\mathit{output}$.
- While more digits are desired, repeat from step 4.
