How to take the square root of a number in a negative base? For example, in negadecimal (base -10): how to take the square root of $185_{-10}=25_{10}$?
Or in negabinary (base -2): the square root of $1100100_{-2}=36_{10}$?
Converting to another base, taking the square root and converting back to the negative base is not an option. I'm looking for an algorithm fully done in the negative base.
I take the square root of a binary number by dividing a number like $11001_2=25_{10}$ as follows:
$01|10|01$
And then conditionally subtracting $01$ from each segment from left to right, adding a $1$ to the answer and appending the answer to the $01$ subtraction.


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.

