Understanding of the non-restoring square root algorithm

There is some mess in this pseudocode, but if we look to the article Modular array structure for non-restoring square root circuit by S. Samavi, A. Sadrabadi, A. Fanian which was used as the main idea for design, we can find the following pseudocode:

algorithm Non-restoring square root is input: 2n-bit operand X output: n-bit quotient Q, n-bit remainder R Step 1: R_0 = 0.x_1x_2; F_0 = 0.01; i = 1; Step 2: R_1 = R_0 - F_0; Step 3: If (R_i < 0) then (q_i ← 0; R_i ← R_i.x_{2i+1}x_{2i+2}; F_i ← 0.0...0q_1q_2...q_i11; R_{i+1} ← R_i + F_i;) Else (q_i ← 1; R_i ← R_i.x_{2i+1}x_{2i+2}; F_i ← 0.0...0q_1q_2...q_i01; R_{i+1} ← R_i - F_i;) Step 4: i ← i + 1; Step 5: If (i ≤ n) then (go to step 3) Else (Q = 0.q_1q_2q_3...q_n); End; 

The essential difference is that negative number is converted to the complement representation for output only. Intermediate negative value of $R_i$ is thought as minus sign and a positive value. That's why appending digits $x_{2i + 1}x_{2i + 2}$ to negative $R_i$ is equivalent to subtraction of $\overline{x_{2i + 1}x_{2i + 2}} \cdot 2^{-2i - 2}$ from $R_i$. In the way you understand the article you cite appending these digits is equivalent to addition of the same value, that doesn't seem to be correct.

Also it's a typo that the line 26 has $01$ at the end instead of $11$. However it is correct that for $n = 4$ there should $2$ leading zeroes. Try numbers with multiple $1$ digits in the square root to see that your "fix" doesn't work in general.

So the correct iterations of the algorithm should look like this:

$a = 73_{10} = 01001001_2$

$n = 8$

Step 1: initialization of $R$ and $F$ (line $2 \to 4$)

$R = 00000001$

$F = 00000001$

$R = R - F = 00000000$

Step 2: first iteration of the loop (line $15 \to 20$)

$i = n / 2 − 1 = 3$

$R \ge 0 \Rightarrow Y_{3} = 1$

$R = 00000000$ (shifting $R$ by two bits and appending $a_5$ and $a_4$)

$F = 0000 0101$

$R = R - F = 0000 0000 - 0000 0101 = -000 0101$

Step 3: second iteration of the loop (line $8 \to 13$)

$ i = 2 $

$ R < 0 \Rightarrow Y_2 = 0$

$ R = -0001 0110 $ (shifting $R$ by two bits and appending $a_3$ and $a_2$)

$ F = 0000 1011 $

$ R = R + F = -0001 0110 + 0000 1011 = -0000 1011$

Step 4: third iteration of the loop (line $8 \to 13$)

$ i = 1 $

$ R < 0 \Rightarrow Y_1 = 0 $

$ R = -0010 1101 $ (shifting $R$ by two bits and appending $a_1$ and $a_0$

$ F = 0001 0011 $

$ R = R + F = -0010 1101 + 0001 0011 = -0001 1010 $

Step 5: final remainder restoration (line $25 \to 28$)

$ R < 0 \Rightarrow Y_0 = 0 $

$ F = 0010 0011 $

$ R = R + F = -0001 1010 + 0010 0011 = 0000 1001 $

So $Y = 1000_2$ and $R = 1001_2$, that is exactly what you expect.