Solved–Calculate Square Root without a Calculator –Solution

Description

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:

1. 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

2. Multiply the current result by 2 and again by 10 and put it aside. Let’s call this value temp.

2. Find the largest integer x (0 x 9) such that

(temp + x) x current remainder

4. 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)

5. 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.

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	=16>10

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

2. • 10

9

1 56 (1) curent remainder

2. 1 24

(60+2)*2=124<=156	32		(4) 156 − 124 = 32
(60+3)*3=189>156

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

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 10^x in the algorithm become 2^x. Note that multiply a number in binary by 2^x 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:

1. 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

2. Multiply the current result by 2 and again by 2 and put it aside. Let’s call this value temp.

2. 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.

4. 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)

5. 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 = 512₁₀ = 0000000100000000₂).

	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

p

The result is 101101010₂ = 362₁₀ 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