$29
Calculate Square Root without a Calculator Solution
Finding the Square Root of a Real Number
The square root of a real number can be calculated using an algorithm that resembles a long division algorithm. The following is an algorithm to nd the square root of 10.5625. Note that this algorithm can be used to nd square root of any real numbers.
The rst step is to separate a real number into groups of two digits starting at the decimal point in both directions. In case of 10.5625, we get three groups 10, 56, and 25. If a group does not have 2 digits, simply add 0 to the left if the group is on the left of the decimal point or add 0 to the right if the group is on the right of the decimal point. For example, if th real number is 123.456, in this case, get four groups, 01, 23, 45, and 60. For this algorithm, we have to maintain two values, the current result and the current remainder. These two values are initialized to 0.
To nd the square root of a real number, perform the following steps until the remainder becomes 0 again or until you satisfy with the precision of your result:
Pull the left-most unused group (of two digits) and put it to the right of the current remainder. The result is a new current remainder. For example, if the current remainder is 6 and the left-most unused group is 39, the new current remainder is 639. Note that mathematically, this step is equivalent to
current remainder = (current remainder 100) + the left-most unused group
Multiply the current result by 2 and again by 10 and put it aside. Let’s call this value temp.
Find the largest integer x (0 x 9) such that
(temp + x) x current remainder
Subtract the current remainder by (temp + x) x and the result is a new current remainder. In other words,
current remainder = current remainder ((temp + x) x)
Put the value x from step 3 to the right of the current result and this becomes a new current result. Mathematically, this step is equivalent to
current result = (current result 10) + x
6. Go back to step 1.
1
Let’s try to nd the square root of 10.5626 from the beginning for better understanding of the algorithm. First, separate 10.5625 into groups of two digits (starting from the decimal point in both direction), and initialize the current result and the current remainder to 0 as shown below:
current result
0
10 56 25
real number in
0
groups of two digits
curent remainder
The following show the the rst iteration of this algorithm:
current result (before the this iteration)
0*2*10=0
0
3
(5) current reulst (at the end of this iteration)
temp (2)
0
10
56 25
0
10
(1) curent remainder
(3)
9
(0+3)
* 3
=9<=10
1
(4)10−9=1
(0+4)
* 4
=1610
After the second iteration:
current result (before the this iteration)
3 2 (5) current reulst (at the end of this iteration)
3*2*10=60
temp (2)
60
10 56 25
10
9
1 56 (1) curent remainder
1 24
(60+2)*2=124<=156
32
(4) 156 − 124 = 32
(60+3)*3=189156
After the third iteration is shown below:
current result (before the this iteration)
32*2*10=640
3 2
5
(5) current reulst (at the end of this iteration)
temp (2)
60
10 56
25
0
10
9
1 56
1 24
32
25
(1) curent remainder
(3)
32
25
(4) 3225 − 3225 = 0
(640 + 5) * 5 = 3225 <= 3225
0
(640 + 6) * 6 = 3876 3225
2
Note that the third iteration is the last iteration since the current remainder becomes 0. Since the decimal point is in between 10 and 56, the square root of 10.5626 is 3.25.
The following shows the process of nding the square root of 2 (after 9 iterations) using the algorithm discussed in class:
0
1
4
1
4
2
1
3
5
6
02
0
0
02
(0+1)*1=1
01
1*2*10=20
01 00
(20+4)*4=96
96
14*2*10=280
04 00
(280+1)*1=281
02 81
141*2*10=2820
01 19 00
(2820 + 4) * 4 = 11296
01 12 96
1414 * 2 * 10 = 28280
06
04 00
(28280 + 2) * 2 = 56564
05
65 64
14142 * 2 * 10 = 282840
38 36 00
(282840 + 1) * 1 = 282841
28 28 41
141421 * 2 * 10 = 2828420
10 07 59 00
(2828420 + 3) * 3 = 8485269
08 48 52 69
1414213 * 2 * 10 = 28284260
01 59 06 31 00
(28284260 + 5) * 5 = 141421325
01 41 42 13 25
14142135 * 2 * 10 = 282842700
17 64 17 75 00
(282842700 + 6) * 6 = 1697056236
16 97 05 62 36
67 12 12 64
The above algorithm shows that the square root of two is approximately 1.41421356. Note that since the square root of 2 is an irrational number, the algorithm will not stop. Therefore, you have to stop when you satisfy with the precision of your result.
Finding the Square Root of a Positive Integer in Binary
As we discussed in class, any algorithms that work with decimal numbers, they should work with binary numbers. It is true in the case of nding the square root as well. Technically, it is simpler to nd a square root of a number in binary than in decimal. Since the di erent between decimal and binary is the base (10 vs 2). Any 10x in the algorithm become 2x. Note that multiply a number in binary by 2x is the same as shift the number left x times.
You need separate the number into groups of 2 bits and initialize the current result and the current remainder to 0. Do not forget that every bit is either 0 or 1. Thus, the algorithm to nd the square root of a positive integer in binary is as follows:
Pull the left-most unused group (of two bits) and put it to the right of the current remainder. The result is a new current remainder. For example, if the current remainder is 1 and the left-most unused group is 01, the new current remainder is 101. Note that mathematically, this step is equivalent to
current remainder = (current remainder 4) + the left-most unused group
3
Multiply the current result by 2 and again by 2 and put it aside. Let’s call this value temp.
Find the largest integer x (0 x 1) such that
(temp + x) x current remainder
Note that this step is much simpler in binary. Since a bit in binary is either 0 or 1. So, if x is 1, (temp + x) x is simply temp + x. So, you only need to compare temp + x and the current remainder.
Subtract the current remainder by (temp + x) x and the result is a new current remainder. In other words,
current remainder = current remainder ((temp + x) x)
Put the value x from step 3 to the right of the current result and this becomes a new current result. Mathematically, this step is equivalent to
current result = (current result 2) + x
6. Go back to step 1.
Recall that Q8.8 format of a oating-point number x is x 256 and rounded to the closest integer. Thus, you only need to calculate the square root of a positive integer number. The following is an example of nding the square root of 2.0 where 2.0 is represented in Q8.8 format (2:0 256 = 51210 = 00000001000000002).
0
0
0
0
1
0
1
1
0
1
0
1
0
00
00
00
10
00
00
00
00
0<<2=0
00
00
(0+0)*0=0
00
00
0<<2=0
00
00
(0+0)*0=0
00
00
0<<2=0
00
00
(0+0)*0=0
00
00
0<<2=0
00
10
(0+1)*1=1
00
01
1<<2=100
01
00
(100+0)*0=0
00
00
10 << 2 = 1000
01
00
00
(1000 + 1) * 1 = 1001
10
01
101 << 2 = 10100
01
11
00
(10100 + 1) * 1 = 10101
01
01
01
1011 << 2 = 101100
01
11
00
(101100 + 0) * 0 = 0
00
00
00
10110 << 2 = 1011000
01
11
00
00
(1011000 + 1) * 1 = 1011001
01
01
10
01
101101 << 2 = 10110100
01
01
11
00
(10110100 + 0) * 0 = 0
00
00
00
00
1011010 << 2 = 101101000
01
01
11
00
00
(101101000 + 1) * 1 = 101101000
01
01
10
10
00
10110101 << 2 = 1011010100
00
00
00
10
00
00
(1011010100 + 0) * 0 = 0
00
00
00
00
00
00
10
00
00
4
p
The result is 1011010102 = 36210 which is the Q8.8 format of 362=256:0 = 1:4140625 2. As we discussed in class, a square root of a Q8.8 format is a Q4.4 format. That is why the above algorithm has to continue for four more iteration to get Q4.8 format.
Note that the algorithm should stop as soon as the current remainder becomes 0. However, for simplicity, we can let the computer computes exactly 12 iterations every time without checking whether the remainder is already 0.
5
