# Recurrence relation for the digits of the integer square root in binary

I was investigating a question on the Electrical Engineering Stack Exchange site, available here: http://electronics.stackexchange.com/questions/29311/calculating-the-square-root-of-8-bit-binary-number

In short, the OP is interested in the possibility of constructing a digitial circuit which implements the integer square root function using only combinatorial logic. Doing this by hand using the pen-and paper tool for logic minimization, the Karnaugh map, would require 4 (one for each output digit) 3-dimensional maps of size 4x4x8; not really a viable option. Using an automated logic-minimization algorithm like Quine-McCluskey, however, and the problem might be tractable.

With the idea of entering the equations into such a program, I was looking at the patterns of digits for each of the output values in the binary integer square root. With input value on the left and output on the right it goes like:

0b0:0b0
0b1:0b1
0b10:0b1
0b11:0b1
0b100:0b10
0b101:0b10
0b110:0b10
0b111:0b10
0b1000:0b10
0b1001:0b11
0b1010:0b11
0b1011:0b11
0b1100:0b11
0b1101:0b11
0b1110:0b11
0b1111:0b11
etc..


I noticed the 'on/off' pattern of 1 and 0 digits in the integer square root appear to follow certain recurrence relations; for example the least significant digit's recurrence appears to be $R_{n+1} = R_n + 2$ for $R_0 = 1$.

Is there a method to formally 'prove' that the sequence of digits in the binary integer square root do follow such a pattern for all inputs?

-
Oh, it looks like you're saying that (starting at $0$) you get one integer $x$ such that its integer square root (which mathematicians would call $\lfloor \sqrt{x}\rfloor$) is even, then three where it is odd, then five even, etc. This is obvious from the fact that $(n+1)^2 - n^2 = 2n+1$. – Robert Israel Apr 5 '12 at 20:14
Similarly, the $k$'th binary digit from the right changes when $\sqrt{x} = m 2^{k-1}$ for some integer $m$, i.e. when $x = m^2 2^{2k-2}$. So you get $2^{2k-2}$ zeros, then $3 \times 2^{2k-2}$ ones, then $5 \times 2^{2k-2}$ zeros, etc. – Robert Israel Apr 5 '12 at 20:28
@RobertIsrael Oh sure, I see it now, thanks! Since there are only 16 possible values for the integer square root of a number between 0 and 255, there are $2n + 1$ values between the $n + 1$-th digit and the $n$th digit where the least significant digit doesn't change. – Bitrex Apr 5 '12 at 21:37