TITLE: Basic Arithmetic, APL-Style, and Confident Problem Solvers
AUTHOR: Eugene Wallingford
DATE: June 19, 2012 3:04 PM
DESC:
-----
BODY:
After writing last week about
a cool array manipulation idiom,
motivated by APL, I ran across another reference to "APL style"
computation yesterday while catching up with weekend traffic on
the
Fundamentals of New Computing
mailing list. And it was cool, too.
Consider the sort of multi-digit addition problem that we
all spend a lot of time practicing as children:
365
+ 366
------
The technique requires converting two-digit sums, such as
6 + 5 = 11 in the rightmost column, into a units digit and
carrying the tens digit into the next column to the left.
The process is straightforward but creates problems for
many students. That's not too surprising, because there is
a lot going on in a small space.
David Leibs described a technique, which he says he learned
from something Kenneth Iverson wrote, that approaches the task
of carrying somewhat differently. It takes advantage of the
fact that a multi-digit number is a vector of digits times
another vector of powers.
First, we "spread the digits out" and add them, with no concern
for overflow:
3 6 5
+ 3 6 6
------------
6 12 11
Then we normalize the result by shifting carries from right to
left, "in fine APL style".
6 12 11
6 13 1
7 3 1
According to Leibs, Iverson believed that this two-step approach
was easier for people to get right. I don't know if he had any
empirical evidence for the claim, but I can imagine why it might
be true. The two-step approach separates into independent
operations the tasks of addition and carrying, which are
conflated in the conventional approach. Programmers call this
separation of concerns, and it makes software easier to
get right, too.
Multiplication can be handled in a conceptually similar way.
First, we compute an outer product by building a digit-by-digit
times table for the digits:
+---+---------+
| | 3 6 6|
+---+---------+
| 3 | 9 18 18|
| 6 | 18 36 36|
| 5 | 15 30 30|
+---+---------+
This is straightforward, simply an application of the basic facts
that students memorize when they first learn multiplication.
Then we sum the diagonals running southwest to northeast, again
with no concern for carrying:
(9) (18+18) (18+36+15) (36+30) (30)
9 36 69 66 30
In the traditional column-based approach, we do this implicitly
when we add staggered columns of digits, only we have to worry
about the carries at the same time -- and now the carry digit
may be something other than one!
Finally, we normalize the resulting vector right to left, just
as we did for addition:
9 36 69 66 30
9 36 69 69 0
9 36 75 9 0
9 43 5 9 0
13 3 5 9 0
1 3 3 5 9 0
Again, the three components of the solution are separated into
independent tasks, enabling the student to focus on one task at a
time, using for each a single, relatively straightforward operator.
(Does this approach remind some of you of
Cannon's algorithm
for matrix multiplication in a two-dimensional mesh architecture?)
Of course, Iverson's
APL
was designed around vector operations such as these, so it includes
operators that make implementing such algorithms as straightforward
as the calculate-by-hand technique. Three or four Greek symbols
and, voilá, you have a working program. If you are
Dave Ungar,
you are well on your way to a compiler!
I have a great fondness for alternative ways to do arithmetic.
One of the favorite things I ever got from my dad was a worn
copy of Lester Meyers's
High-Speed Math Self-Taught.
I don't know how many hours I spent studying that book, practicing
its techniques, and developing my own shortcuts. Many of these
techniques have the same feel as the vector-based approaches to
addition and multiplication: they seem to involve more steps, but
the steps are simpler and easier to get right.
A good example of this I remember learning from High-Speed Math
Self-Taught is a shortcut for finding 12.5% of a number: first
multiply by 100, then divide by 8. How can a multiplication and a
division be faster than a single multiplication? Well, multiplying
by 100 is trivial: just add two zeros to the number, or shift the
decimal point two places to the right. The division that remains
involves a single-digit divisor, which is much easier than
multiplying by a three-digit number in the conventional way. The
three-digit number even has its own decimal point, which complicates
matters further!
To this day, I use shortcuts that Meyers taught me whenever I'm
making updating the balance in my checkbook register, calculating
a tip in a restaurant, or doing any arithmetic that comes my way.
Many people avoid such problems, but I seek them out, because I
have fun playing with the numbers.
I am able to have fun in part because I don't have to worry too
much about getting a wrong answer. The alternative technique
allows me to work not only faster but also more accurately. Being
able to work quickly and accurately is a great source of confidence.
That's one reason I like the idea of teaching students alternative
techniques that separate concerns and thus offer hope for making
fewer mistakes. Confident students tend to learn and work faster,
and they tend to enjoy learning more than students who are
handcuffed by fear.
I don't know if anyone was tried teaching Iverson's APL-style
basic arithmetic to children to see if it helps them learn faster
or solve problems more accurately. Even if not, it is both a great
demonstration of separation of concerns and a solid example of how
thinking about a problem differently opens the door to a new kind
of solution. That's a useful thing for programmers to learn.
~~~~
Postscript. If anyone has a pointer to a paper or book in which
Iverson talks about this approach to arithmetic, I would love to
hear from you.
IMAGE: the cover of Meyers's High-Speed Math Self-Taught,
1960. Source:
OpenLibrary.org.
-----
