Beyond turtle graphics. Donald T. Piele.
Beyond Turtle Graphics
When I run across an interesting computer program while browsing through the pages of a computer book or magazine, I often stop and wonder, "Yes, the program seems to work; it appears to be correct. But how can I write such a program myself?' Sometimes the author supplies hints on how the program works by identifying regions of the program where important things happen.
By studying other people's programs, I frequently pick up new programming strategies and techniques to tuck away for use at another time and place. The most important ideas are usually very simple and packaged in small bundles. They represent little kernels of code that handle some very big tasks.
Mathematicians create new structures in the same way. They approach problems by defining new objects, creating and proving small packages of relationships called lemmas, and then posing and proving new theorems by fitting the parts together. The primary reason that mathematics is considered a necessary component of formal education is that it teaches people to organize and attack problems in a structured way.
"Top Down' structured programming, which we hear so much about today in the context of computer programming, is not new at all to mathematicians. They have been doing it for centuries. Euclid's Elements, one of the greatest influences on the development of scientific thinking, is primarily known for its skillful selection of propositions and their arrangement into a logical order. Much of the material found in today's high school plane and solid geometry texts came from this work.
What is different today is that computers have dramatically expanded our options for teaching how to organize and solve problems in a structured way. We are beginning to see new languages and curriculum materials whose major function is to teach analytical reasoning skills through the use of structured programming exercises. One such language that has drawn considerable attention lately is Logo, which was developed under the direction of Seymour Papert at MIT.
Much has been written lately about the problem solving ability of Logo [3,4]. The emphasis in all of these writings is on teaching problem solving using Turtle graphics. There is no question about the effectiveness of Logo in this area. I have tried it, teachers have tried it, kids have tried it, and we all love it. But what is Logo like beyond Turtle graphics?
This month, I would like to examine a non-graphics problem using the Logo language. Armed with the Apple Logo reference manual and Harold Abelson's book, Apple Logo, I decided to tackle a problem involving the generation and display of factorials.
Small Factorials
The only place an exclamation point is used in mathematics is to indicate a factorial. For example, 4!, read as "factorial four,' is defined to be the product 4X3X2X1, which equals 24. A deck of 52 cards can be dealt out in 52! or 80,658,175,170,943,878,571,660,636,856,403,766, 975,289,505,440,883,277,824,000,000,000,000 ways to be exact. How do you write a program to generate factorials?
First examine the following Basic factorial program.
10 PRINT "SMALL FACTORIALS'
20 INPUT "ENTER A WHOLE NUMBER- ';N
30 FACTRIAL = 1
40 FOR I = 1 TO N
50 FACTRIAL = FACTRIAL
60 NEXT I
70 PRINT N;"!=";FACTRIAL
80 END
Type it in and run it for N = 12 and N=13.
SMALL FACTORIALS
ENTER A WHOLE NUMBER- 12
12!=479001600
ENTER A WHOLE NUMBER- 13
13!=6.2270208E+09
Notice that the above procedure has no provision for being precise beyond nine digits. This causes the switch to scientific notation between 12! and 13!. Try running the program for N=33 and N=34. On the Apple II you will set an overflow error for N=34 since 34! has more than 38 digits--the limit for real numbers in Applesoft.
Now let's take a look at the same problem solved in two different ways using Logo. The first program follows the same logic used in the Basic program. The second version is recursive. Two procedures need to be defined.
The two procedures in Listing 1 are written in Apple Logo. The LOOP procedure is equivalent to lines 30 to 60 in the Basic program. Type in both procedures and then type BEGIN. Everything about the Logo program including the nine-place precision and the termination between 33! and 34! is identical to the Applesoft Basic program.
There is a better way to solve this problem in Logo by taking advantage of its natural recursive structure. A recursive procedure is one that calls itself. Factorials are easy to define recursively. For example if we set FACTORIAL (N) = N!
then
FACTORIAL (N) = N X FACTORIAL (N-1)
and
FACTORIAL (1) = 1
completely define FACTORIAL (N). This procedure can be implemented in Logo as follows:
TO FACTORIAL :N
IF :N = 1 [OUTPUT 1 STOP]
OUTPUT :N * FACTORIAL :N - 1
END
Replace LOOP 1 in the BEGIN procedure with the line PRINT FACTORIAL :N. Now type BEGIN to use the recursive version.
Large Factorials
The built-in precision of Basic and Logo is not good enough to display all the digits in N! for large N. How can we correct this problem and generate large factorials with all their digits intact?
Let's begin by writing a Basic program that will print out N! for any whole number N up to 500. See Listing 2.
The 68 digits (shown earlier) that constitute 52!, took about 45 seconds to generate with this program. The algorithm is exactly what one would use if one had to do it by hand with paper and pencil--simply multiply I * (I-1)! for I = 1 to N. The loop between lines 70 and 110 takes care of the digit by digit multiplication, keeping track of the quotients, the carries, and the remainders. The array A%() holds the digits of the current value of the factorial. The least significant digit is held in A%(1) and the most significant digit is in A%(DIGIT). The procedure in line 120 makes sure that the value of the carry does not get out of hand. Finally, lines 145 to 170 print out the digits of the answer in proper order.
Logo Version
Instead of defining arrays, Logo uses words. Table 1 shows exactly what response you get to the corresponding commands in Logo in the immediate mode.
The digits of a large factorial can be stored together in proper order as a word. Each digit can be isolated with LAST BUTLAST; products can be formed with * and individual digits separated with QUOTIENT and REMAINDER. To solve the problem in Logo, break it up into the following five procedures; BEGIN, FACTORIAL, MULTIPLY, LONGHAND, and SOLUTION.
TO BEGIN
PRINT [LARGE FACTORIALS]
TYPE [ENTER A WHOLE NUMBER -]
MAKE "N FIRST READLIST
(TYPE :N [!=] FACTORIAL :N)
PRINT'
END
This procedure is the same one used in the limited version.
TO FACTORIAL :N
IF :N = 1 [OUTPUT 1 STOP]
OUTPUT MULTIPLY :N FACTORIAL :N - 1
END
This procedure is recursive and similar to the one used before. Now, however, the multiplication must be constructed--hence the procedure MULTIPLY.
TO MULTIPLY :N :B
MAKE "CARRY 0 MAKE "ANSWER'
OUTPUT LONGHAND :N :B
END
Each time we make a multiplication, we must start over with an empty answer and a zero for the carry. Now we are ready to perform the multiplication by LONGHAND.
TO LONGHAND :N :B
IF :B = " [OUTPUT SOLUTION STOP]
MAKE "TEMP :CARRY + :N * LAST :B
MAKE "CARRY QUOTIENT :TEMP 10
MAKE "DIGIT REMAINDER :TEMP 10
MAKE "ANSWER WORD :DIGIT :ANSWER
OUTPUT LONGHAND :N BUTLAST :B
END
The last step in each multiplication is to add on any carry that occurs in the multiplication of the most significant digit (the one to the extreme left). This leads us to the SOLUTION.
TO SOLUTION
IF :CARRY = 0 [OUTPUT :ANSWER STOP]
MAKE "ANSWER WORD :CARRY :ANSWER
OUTPUT :ANSWER
END
If we type in these procedures, then type BEGIN, and finally enter the whole number 52, it takes 2 minutes and 45 seconds to compute 52!. Try it!
Factorial Oddities
One of the reasons that I picked the multiple precision factorial problem for investigation was the intriguing designs that can be made with them. In Martin Gardner's book, Mathematical Magic Show [2], a chapter is devoted to factorial designs printed out in the shape of triangles, hexagons, and octagons. For example, 105! has 169 digits in the answer which can be displayed in triangular form.
Obviously, only certain factorials can be displayed this way. Which ones are they? If the number of digits in the factorial is a perfect square then it can be printed as a triangle. The factorial for 105 has 169 digits which is a perfect square (169 = 13*13). Other factorials whose digital count is a perfect square are listed in Table 2.
What changes are necessary to the Basic program to print out factorials in triangular form? Here is one way to figure it.
First, compute the place where a line feed is needed. It is necessary after printing a single digit and then after printing three more, five more, seven more and so on. This can be handled with a simple loop that counts up to 2*ROW--1 for each row.
Second, use the ROW number in tabbing over the correct number of places, HTAB 20--ROW. The following changes to the printout routine of the Basic program will do the trick.
148 I=0
150 FOR ROW = 1 TO N
160 HTAB 20 - ROW
170 FOR J=1 TO 2* ROW - 1
180 I=I+1
190 PRINT A%(D-I+1);
200 IF I=D THEN END
210 NEXT J
220 PRINT
230 NEXT ROW
Of course the 20 in HTAB 20 - ROW is designed to handle factorials up to 40 rows long. By the way, it took 3 minutes and 45 seconds to compute 105! in Basic.
Logo's Turn
There are no built-in formatting procedures in Logo. You must create your own. I broke the problem down into three procedures: PRINTOUT, HTAB, AND PRINTROW.
TO PRINTOUT :SOLUTION :ROW
IF :SOLUTION = " [PRINT " STOP]
HTAB 20 -:ROW
PRINTROW (2 * :ROW) - 1
PRINTOUT :SOLUTION :ROW + 1
Again, printing out the triangles requires tabbing over 20 -:ROW for each row and then printing (2 * :ROW)--1 digits from the solution. To do this we must know how to HTAB.
TO HTAB :X
IF :X = 0 [TYPE " STOP]
TYPE "
HTAB :X - 1
END
This procedure is equivalent to the Applesoft HTAB command. The third line (TYPE " ) must be
typed in as
TYPE "(control Q)( ).
This means that after the quote sign, type the Q with the control key down and then make one space with the space bar. The last procedure is PRINTROW.
TO PRINTROW :X
IF :X = 0 [PRINT " STOP]
IF :SOLUTION = " [PRINT " STOP]
TYPE FIRST :SOLUTION
MAKE "SOLUTION BUTFIRST :SOLUTION
PRINTROW :X - 1
END
This procedure is needed to printout out the digits in each row.
We are now ready to incorporate the PRINTOUT procedure into the previous procedures used for generating the factorials. To do this we need to change two lines in the BEGIN procedure.
Type in these procedures and then BEGIN again. If you want to see the printout of 105!, it will take 21 minutes.
Conclusion
One can expect, as a matter of course, that learning a new computer language will take some time. This was certainly true in my case, because I spent the better part of two days working through the Logo procedures to be able to compute and display large factorials. This was a little surprising to me since my experience with the Turtle graphics portion of Logo had been so easy. Even young children find the Logo Turtle graphics easy to use. Beyond Turtle graphics is a different story.
In the introduction to Abelson's book, he writes, "Logo's designers are guided by the vision of an educational tool with no threshold and no ceiling. We try to make it possible for even young children to control the computer in self-directed ways, even at their very first exposure to Logo. At the same time, we believe that Logo should be a general purpose programming system of considerable power and wealth of expression. In fact, we regard these two goals as complementary rather than conflicting, since it is the very lack of expressive power of primitive languages such as Basic that makes it difficult for beginners to write simple programs that do interesting things.'
I am just a beginner with the Logo language and clearly have much to learn yet, but, beyond Turtle graphics, I certainly cannot agree with Abelson's statement. This is the problem. People may assume, as I did, that since kids learn so quickly to work with Logo's Turtle that this ease will also hold for non-graphics problems. I have not found this to be true. Try it yourself with this or other non-graphics problems. Give it to your students to try.
The factorial problem is an example of only one out of five types that we typically place on the International Computer Solving Contest at the junior high level and above. The problems we create touch a wide range of computer problem solving skills which involve words, numbers, simulations, graphics, and puzzles. Teams of up to three students each have two hours to solve all five problems, using a computer language of their choice. On the basis of my experience with Logo thus far, I believe it would be very difficult to compete using Logo.
I want to conclude on a very positive note. I enjoyed working on this little problem solving exercise with Logo, and I intend to continue to solve other problems with Logo. I completely agree with the problem solving philosophy for which this language was developed and so eloquently expressed in Seymour Papert's book Mindstorms [3]. Finally, my mind is not made up. I only hope the experts will begin to show us how to use Logo beyond Turtle graphics.
References
1. Abelson, Harold. Apple Logo, Byte/McGraw-Hill, Peterborough, NH, 1982.
2. Gardner, Martin. Mathematical Magic Show, Alfred A. Knopf, New York, 1977.
3. Papert, Seymour. Mindstorms, Basic Books, Inc., Publishers, New York, 1980.
4. Watt, Molly. "What is Logo?' Creative Computing, Vol. 8, No. 10, October 1982, pp. 112-129.
5. Weinreb, William. "Problem Solving with Logo,' Byte, Vol. 7, No. 11, November 1982, pp. 118-134.
Table: Listing 1.
Table: Listing 2.
Table: