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 11Then we normalize the result by shifting carries from right to left, "in fine APL style".
6 12 11 6 13 1 7 3 1According 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 30In 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 0Again, 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!