1
$\begingroup$

I was investigating a question on the Electrical Engineering Stack Exchange site, available here: https://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?

  • 0
    @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.2012-04-05

0 Answers 0