Square Roots in BinaryDate: 10/03/2000 at 01:11:02 From: Greg Watkins Subject: Square root of binary numbers I am confused on taking a square root of a binary number. I hear that you have to split the radicand into groups of two, subtract a partial root, and if the resulting subtraction of the partial root from the most significant group of the radicand is positive, the new partial root is shifted twice with the next two bits from the radicand shifted into the least significant part. I just wanted to get you started so you know what I'm talking about. Please help! An example or clear explanation would be most helpful. Thank you, Greg Watkins Date: 10/03/2000 at 10:42:59 From: Doctor Rob Subject: Re: Square root of binary numbers Thanks for writing to Ask Dr. Math, Greg. The method you describe is the base-2 version of the base-10 method described on this web page from our Doctor Math Archives: Longhand Square Roots http://mathforum.org/dr.math/problems/tim3.30.98.html The main difference is that when that method says to multiply by twenty (twice the base), instead you want to multiply by four, or 100 in base 2. Example: Take the square root of 110010110 in base 2. . /---------------------- \/ 1 10 01 01 10.00 00 00 1 . /---------------------- \/ 1 10 01 01 10.00 00 00 1 ------ 100 + _ | 10 1 0 . /---------------------- \/ 1 10 01 01 10.00 00 00 1 ------ 100 + 0 | 10 | 0 --------- 1000 + _ |10 01 1 0 1 . /---------------------- \/ 1 10 01 01 10.00 00 00 1 ------ 100 + 0 | 10 | 0 --------- 1000 + 1 |10 01 |10 01 ---------- 10100 + _ | 01 1 0 1 0 . /---------------------- \/ 1 10 01 01 10.00 00 00 1 ------ 100 + 0 | 10 | 0 --------- 1000 + 1 |10 01 |10 01 ---------- 10100 + 0 | 01 | 0 ---------- 101000 + _ | 1 10 1 0 1 0 0. /---------------------- \/ 1 10 01 01 10.00 00 00 1 ------ 100 + 0 | 10 | 0 --------- 1000 + 1 |10 01 |10 01 ---------- 10100 + 0 | 01 | 0 ---------- 101000 + 0 | 1 10 | 0 ---------- 1010000 + _ | 1 10 00 1 0 1 0 0. 0 /---------------------- \/ 1 10 01 01 10.00 00 00 1 ------ 100 + 0 | 10 | 0 -------- 1000 + 1 |10 01 |10 01 ---------- 10100 + 0 | 01 | 0 ------------ 101000 + 0 | 1 10 | 0 -------------- 1010000 + 0 | 1 10 00 | 0 ---------------- 10100000 + _ | 1 10 00 00 1 0 1 0 0. 0 0 /---------------------- \/ 1 10 01 01 10.00 00 00 1 ------ 100 + 0 | 10 | 0 -------- 1000 + 1 |10 01 |10 01 ---------- 10100 + 0 | 01 | 0 ------------ 101000 + 0 | 1 10 | 0 -------------- 1010000 + 0 | 1 10 00 | 0 ---------------- 10100000 + 0 | 1 10 00 00 | 0 ---------------- 101000000 + _ |1 10 00 00 00 1 0 1 0 0. 0 0 1 /---------------------- \/ 1 10 01 01 10.00 00 00 1 ------ 100 + 0 | 10 | 0 -------- 1000 + 1 |10 01 |10 01 ---------- 10100 + 0 | 01 | 0 ------------ 101000 + 0 | 1 10 | 0 -------------- 1010000 + 0 | 1 10 00 | 0 ---------------- 10100000 + 0 | 1 10 00 00 | 0 ---------------- 101000000 + 1 |1 10 00 00 00 |1 01 00 00 01 ------------------ 1010000100 + _ | 11 11 11 00 and so on. The underlying principle is (10*Q+D)^10 = 100*Q^10 + D*(100*Q+D) or even better, (100*N+n) - (10*Q+D)^10 = (100*[N-Q^10]+n) - D*(100*Q+D) (Here *all* numerals are written in base 2.) - Doctor Rob, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2015 The Math Forum
http://mathforum.org/dr.math/