An Integer Square Root Algorithm
71
Example 24
An Integer Square Root Algorithm
The C algorithm shown in Fig. 2.8 performs an integer square root of the input a
as shown in Table 2.1. Note from Table 2.1 that the difference between successive
squares, delta, is just the sequence of odd numbers. Also note that the while loop is
executed as long as square is less than or equal to a. Thus, the value of the square root,
delta/2 – 1, occurs in the row following the square value in Table 2.1.
Table 2.1
Illustrating the algorithm in Fig. 2.8
n square = n^2 delta delta/2-1
0 0
1 1 3
2 4 5 1
3 9 7 2
4 16 9 3
5 25 11 4
6 36 13 5
7 49 15 6
8 64 17 7
9 81 19 8
10 100 21 9
11 121 23 10
12 144 25 11
13 169 27 12
14 196 29 13
15 225 31 14
16 256 33 15
17 289
unsigned long sqrt(unsigned long a){
unsigned long square = 1;
unsigned long delta = 3;
while(square <= a){
square = square + delta;
delta = delta + 2;
}
return (delta/2 - 1);
}
Figure 2.8 Integer square root algorithm
评论10