Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Square Roots in Binary


Date: 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/   
    
Associated Topics:
High School Exponents
High School Number Theory

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/