√ by Tim Paterson
Square roots have a number of possible
applications in microcontroller systems ...
My particular application — as
we discuss here — is in filtering
input data used to calibrate
the odometer in a road rally computer.
After computing a best-fit line using a
linear regression on a set of data
points, square roots are needed to
compute the distance of each data
point from the line. If a data point is
too far off the line, it is discarded on
the assumption of human error and the
line is recalculated.
Square Root on a PIC in the
November ‘06 issue of Nuts & Volts
( www.nutsvolts.com) demonstrated
a simple algorithm for computing
square roots. While the implementation was very compact, the algorithm
has a significant performance issue — it
gets extremely slow as the argument to
the square root function gets large.
This is because the algorithm sequentially computes each square starting
at 1 until it finds the one closest to
the argument.
Let’s look at an alternative method
of computing square roots. It has the
advantage of taking nearly constant
time, regardless of argument — about
150 microseconds for a 32-bit input on
a 20 MHz PIC18. This makes it practical
to compute square roots in a robot
control loop running 100 times per
second, for example. Code size is
38 SERVO 01.2008
about 35% larger, but still well under
200 bytes.
√ Algorithm
This algorithm for computing
square roots determines one result bit
at a time, in a manner very similar to
binary long division. In
fact, it is so similar
that a review of long
division — decimal and
binary — will be helpful to set the stage.
Figure 1 shows a
sample long division
problem. The basic
steps for each digit
are:
6
79
897)62518
6279
-5382
8698
-8073
625Figure 1.
Decimal long
division
example.
• Make a guess of the digit.
• Multiply the trial digit by the divisor.
• Try to subtract that product from the
current remainder.
– If the product is larger than the
remainder, make a new guess with
a smaller digit.
– If the subtraction produces a
result larger than the divisor, make
a new guess with a larger digit.
In the case of Figure 1, the guess
for the first digit (estimated from 62÷ 8)
initially turned out to be too large. The
first trial digit and product are crossed
out and a new set was tried.
The description for binary long
division is the same, but the only two
choices for the trial digit are 0 and 1.
This makes it very easy to make the right
guess, and also very easy to compute
the trial * divisor
product that is to
be subtracted from
the remainder.
Figure 2 shows
a sample binary
division problem.
1101
1001)1111001
-1001
1100
-1001
0110
-0000
1101
-1001
100By definition
of square root, if
the divisor equals
the quotient, then
we have the
square root of the
dividend. The algorithm for square root
takes the form of binary division where
the divisor is continually changed to
match the quotient.
Figure 2. Binary
long division
example.
The square root of an N-bit
number has N/2 bits; in our example,
we’ll be taking the four-bit square root
of an eight-bit number. From our
binary division viewpoint, we’ll be
looking for the square root of the
dividend. We start with a divisor at the
midpoint of the possible result range: a
1 followed by N/2 – one zero; in our
case, a 1 followed by three zeros.
