Heron of Alexandria, who
first described an effective algorithm for finding square
roots.
(Image from here)
At a meeting of the Computer
Science and Telecommunications Board of the National Research
Council, we were discussing what it means to teach computational
thinking to everyone, and how that task might differ from teaching
mathematical or scientific or engineering thinking.
I had a small thought that it’s hard to lump together all the
various ways that one might think computationally. As an example,
consider the mundane problem of taking square roots, as taught in
our primary through college educational systems.
Sometime in elementary school, I learned the concept of square
roots, and was taught a method of guess and check to solve
these. This technique tended to work, perhaps because my
teachers were careful to pose problems that required taking the
square root of a perfect square. In fact, the better students
learned to iterate (informally) toward a solution rather than
blindly guessing, so if, say, the square of a guess was too high,
the next guess should be lower.
In about fifth grade, I learned a complicated algorithm that could
reliably compute square roots, even of very large or fractional
numbers, by decomposing the overall task into a sequence of small
guess-and-check problems that I was assured would work.
Actually, I’m still not sure I fully understand why this algorithm
worked, but it did, and I took pride in knowing how to perform it.
Sometime later, I learned (and much later taught, as an example of
recursion in MIT’s
6.001) the method of Heron of Alexandria, which formalizes the
intuition I had developed in my guess-and-check days. If we
are asked to take the square root of y, then the answer will
be x such that x2 = y. We make a
series of guesses for x, x0, x1,
x2, ... so that
xi+1 = average(xi,
y/xi)
As an example of Newton’s method, it’s even possible to prove that
this will converge to the right answer.
When I was in college and started to program seriously, I learned
that standard subroutine libraries did not in fact use any of these
methods in their implementation. Instead, they relied on the
limited precision of computer representations of floating point
numbers, calculated the rate of convergence of Newton’s method for
this problem, and unrolled the recursion to a fixed set of steps
that would guarantee convergence to the representable precision in
the machine. This approach may compute more of the xi
than is necessary, but saves all the overhead of testing for
convergence and iterating. More sophisticated versions may
even do a few tests that identify the range of y for which
different number of (unrolled) iterations is best, and adjust the
initial guess based on some simple computation from the size of y.
Now, all of these techniques represent some kind of systematic
thinking. The basic concept of square roots and finding a value that
satisfies some equation probably belongs to mathematical
thinking. If algorithms define computation, then the later
methods illustrate computational thinking, though Newton would
surely have thought of his method as mathematical, computation not
yet having acquired a distinct role in his day. The final one
is based more on numerical analysis and thus comes back to
mathematics on the one hand and to engineering principles of
optimization on the other.
Personally, I am not much of a taxonomist, so my interest is mainly
in fostering education where students learn to think logically and
systematically, to whatever field we attribute it. As this
little example illustrates, however, there is not one such way to
think about problems but an evolving range of them. And this, too,
is a lesson worth learning.
Back to Blog
