What methods exist to divide two numbers that do not require comparison? I am particularly interested in the case where $n$ and $d$ are integers, and we want to find $q$ such that $n=qd+r$.
I have found a number of methods that do use comparisons, such as:
Division by repeated subtraction
Subtract $d$ from $n$ until $n<0$, which clearly uses a comparison.Egyption Division
We try to guess the quotients binary decomposition by multiplying $d$ by powers of 2 and comparing if they are bigger or less than $n$.
The methods I have found that do satisfy my the no-comparison rule are:
Goldschmidt Division which uses the following recurrence relation to approximate division
$a_{i+1} = a_i * r_i \quad a_0 = n \\ b_{i+1} = b_i * r_i \quad b_0 = d \\ r_{i+1} = 2 - b_i \quad r_0 \in (0, 1)$Newton-Raphson Division which also uses a recurrence relation to compute
$q = x_k$ where $k ≥ \left \lceil \log_2(log_{17} (n + 1)) \right \rceil$ and
$x_{i+1} = 2x_i - dx_i^2$ with $x_0 \in (0, 1)$
What other division methods are there that don't rely on comparisons? and Are there any such methods that do not use approximation like the two above?
Another question asks about similar methods that don't "guess" $q$, but the answers there don't fit my criteria of minimal comparisons. Also, please correct me if I made any mistakes in describing the methods above.
