Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I was investigating a question on the Electrical Engineering Stack Exchange site, available here:

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:


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?

share|cite|improve this question
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.