Let’s Get Technical
by James Antonakos
Electronic Theories and Applications From A to Z
Let’s Get Technical
The Root of the Problem:
Performing Integer Square Roots
When I first began playing with microprocessors,
the initial eight-bit CPUs had limited eight- and
16-bit addition and subtraction capabilities, but
could not multiply or divide. I always had to write an eight-bit multiply subroutine when I needed one.
When 16-bit microprocessors came around, the
instruction sets were much more powerful. Sixteen- and
32-bit multiplication and division capabilities were now
available, and while this was an improvement, it was still
impossible to do anything beyond the basic four math
operations unless you wrote a ton of code or added a coprocessor. Even something as simple as the square root
operation was not available.
So, let’s make one. Let’s design a subroutine that will
calculate the integer square root of another integer.
Examine Table 1 for some integer square root examples.
In applications where the integer root of a value is
good enough (estimating distance in a video game, for
instance), we are able to take advantage of a simple
formula to perform the following calculation:
Square Root of N
Integer Square Root of N
In this formula, N is the input number and Est is the
estimated square root. This formula is an iterative formula. We begin with an initial guess for the first value of Est.
One trip through the formula adjusts Est to a new value
that is closer to the square root than the initial guess.
After several trips through the formula, the value of Est
will settle to the integer square root of the input number
N. This process is illustrated in Table 2.
Depending on the initial estimate, the number of iterations through the formula will vary before the estimate
becomes stable. In Table 2, all of the estimates fall well
within the 10-pass limit chosen for the table. In actual
operation, 10 passes may not be enough. We will investigate this feature when we have working code.
Table 1. Integer square root examples.
Note that the formula works just as well for
Est = 4
Est = 100
Est = 500
How do we turn the equation into working code? One
way is to write pseudo-code, a generic description of the
steps the program needs to perform that do not contain
any specific programming statements. The pseudo-code
for the square-root formula looks like this:
NUTS & VOLTS
Initialize loop counter to 10
Divide N by Estimate
Add Estimate to result
Estimate = result / 2
Decrement loop counter
Until counter equals 0
Table 2. Finding the integer square root of 100.
Now, the trick is to convert each statement into one
or more assembly-language or high-level-language statements. In C, we could use something like this: