Kitchen Sync

Two to the What?

Recently, a cousin from Lincolnwood, Illinois, came out to visit. Along with him, he brought a couple of “extra credit” problems given him by his eighth grade science teacher.

One of the problems was to calculate 2 to the 420th power. The problem came with the following restriction: “You can’t use a computer.” Since no commonly available computer can store a number this large with perfect accuracy (remember, floating point numbers are only approximations of a number), this restriction seemed unnecessary.

You have probably already guessed, though, that with some thought and a few tricks, you can solve this problem using a computer. It should also come as no surprise that we are going to show you how to do it on your ZX80/81.

It does seem to us, however, that any eighth grader who could figure out how to solve this problem on a computer is well on the way to becoming a clever problem-solver who can make good use of available tools, and, therefore, deserves the extra credit. Lincolnwood School District, take note.

To solve this problem on a ZX80/81 or on any computer, you first have to understand how to do it by hand.

Unless you are a child prodigy, you cannot handle a number as big as 2 to the 420th either. The best way to deal with things too big to handle all at once, of course, is to break them down into “bite-size” chunks. In this case, the most obvious method probably would be to treat each digit separately. You could take 2, multiply it by 2, take that answer and multiply it by 2 again, and so on, 419 times. When the numbers begin getting too large to multiply in your head, you would move from right to left, multiplying a digit by 2, adding in any carry from the previous digit, and carrying into the next, if necessary. Just like in school, right?

While the ZX80/81 cannot handle numbers as large as 2 to the 420th, it can handle numbers as big as 32767 (decimal). Rather than doing the calculations one digit at a time, as you would do by hand, it is a simple matter to have the ZX80/81 multiply four digits at a time. Listing 1 gives the program for calculating 2 to the 420th. This was written on the ZX80 4K ROM, but it works also on the ZX81 if you make this change:

180 PRINT A(I);"##";

Since the answer to our problem is 127 decimal digits long (How do we know? Trust us.), we can store it in an array of 32 integers. This is done in line 10. Lines 20-50 initialize our answer to 1 (2 to the zero-ith power). Lines 60 through 160 are the main loop of the program and multiply A by 2 420 times. C is the carry from one “digit grouping” to the next and is cleared in line 70. (There is no carry, of course, into the rightmost digit.)

Lines 80 and 90 set up a backwards FOR-NEXT loop going from 32 down to 1, covering each digit group from right to left. We could have numbered the digit groups in the other direction, but then we would have needed a reverse loop to print out the result, so it did not make much difference which way we went. Line 100 multiplies the current digit group by 2 and adds in the carry from the previous digit group. Line 110 clears the carry, since we do not as yet know whether there is to be a carry out of the current digit group. Line 120 skips over the carry processing if the current digit group is within range (0-9999). Lines 130 and 140 do the carry processing by bringing the digit group back within range and setting the carry into the next group to 1. You should satisfy yourself that this is correct.

Line 150 closes the loop at line 80 and proceeds to the next digit group. Line 160 closes the loop at line 60 and proceeds to the next doubling. Calculations are now finished, and lines 170 through 190 print out the result.

Note that the format of the output is rather sloppy. The reason for this is that some of the digit groups may be less than 1000, and in order for the result to be printed together, program lines would have to be added to print these groups with leading zeros. While this is not particularly difficult, it would tend to make the program more complicated. If you have sufficient RAM, the inspiration, and a compulsion for neatness, see if you can alter our program to “prettyprint.”

When run, the program grinds away for a little over four minutes before returning with the answer. Compared to pencil and paper, that is not bad. But consider this: on the first iteration of the main loop (lines 60-160) the variable A(32), which is originally 1, is multiplied by 2, giving 2. But A(1) through A(31), while being equal to 0, are still multiplied by 2. On the second iteration this is also true. In fact, most of the four minutes are spent multiplying 0 by 2!

This provides us with a good example off how careful planning can make a program run faster. If you think through a problem ahead of time, you can cut out the pointless work and free your ZX80/81 to do the real work of calculating or searching or whatever. Sure enough, there is a simple way to “optimize” our program to eliminate the wasted work of multiplying 0 by 2.

If you keep a pointer (call it “P”) to the most significant (leftmost) non-zero digit, and stop the right-to-left multiplication loop (lines 80-150) at that point, you avoid the unnecessary multiplications. Remember, though, to move this pointer to the left when you carry out of that digit (in this case, the digit to the left will now be non-zero).

If that is a bit tough to follow the first time through, add the lines in Listing 2 for 4K ROM or Listing 3 for 8K ROM. Then trace through the program using pencil and paper. You will see how the unnecessary work is avoided.

Line 55 initializes our new pointer to one significant digit group. This is because A(32), or rather, A(P), is the only digit group with anything in it. Line 80 has been changed to loop through only the significant digit groups. You should verify that this is correct.

Lines 143 through 147 have been added to the carry processing section. They will only be executed when there is a carry out of a digit group. Line 143 checks to see if this is a carry out of the currently most significant digit group (the one P points to). If not, this is simply a normal carry, and carry processing is done. Otherwise, lines 145 and 147 move the pointer one digit group to the left and set that digit group to 1 (the carry out of the previous group).

With this modification in place, the program takes just under three minutes, an improvement of over 35 percent.

It should be apparent that you can use this same technique to calculate other “big” numbers. If you really want to impress your friends, amaze yourself, and give your ZX80/81 a workout, try calculating that wonderful constant, pi, to a hundred places or so. You will have to solve a few problems along the way, but you have two months until the next issue of SYNC comes in the mail…right?

By the way, in case you did not have your ZX80/81 with you as you read this column (perish the thought!), the answer to our problem is (drum roll, please):

2, 707, 685, 248, 164, 858, 261, 307, 045, 101, 702, 230, 179, 137, 145, 581, 421, 695, 874, 189, 921, 465, 443, 966, 120, 903, 931, 272, 499, 975, 005, 961, 073, 806, 735, 733 604, 454, 495, 675, 614, 232, 576.

Listing 1: 2 to the 420th (4K ROM).

 10 DIM A(32)
 20 FOR I=1 TO 32
 30 LET A(I)=0
 40 NEXT I
 50 LET A(32)=1
 60 FOR N=1 TO 420
 70 LET C=0
 80 FOR I=1 TO 32
 90 LET I1=33-I
100 LET A(I1)=A(I1)*2+C
110 LET C=0
120 IF A(I1)<10000 THEN GOTO 150
130 LET A(I1)=A(I1)-10000
140 LET C=1
150 NEXT I
160 NEXT N
170 FOR I=1 TO 32
180 PRINT A(I),
190 NEXT I

Listing 2: Eliminating 0*2 (4K ROM).

 55 LET P=32
 80 FOR I=1 TO 32-P+1
143 IF NOT I1=P THEN GOTO 150
145 LET P=P-1
147 LET A(P)=1

Listing 3: Eliminating 0*2 (8K ROM).

 55 LET P=32
 80 FOR I=1 TO 32-P+1
143 IF I1<>P THEN GOTO 150
145 LET P=P-1
147 LET A(P)=1