The Brick Wall In Your Computer

I REALLY HATE THIS DAMN MACHINE
I REALLY WISH THEY’D SELL IT.
IT NEVER DOES WHAT I WANT
BUT ONLY WHAT I TELL IT!!

Graffiti written on
university computer

Actually that poem is a bit optimistic. Even when you tell your computer to do something, it may instead do something else. It knows nothing about the decimal numbers we use in BASIC, but instead uses a clever program that gives the illusion that it does. Unfortunately, this program has certain limitations, and can give the wrong answers to some programs. This is not a bug, it’s a problem that must occur in every BASIC in every computer. If the BASIC interpreter were well written, we’d rarely, if ever, run into these limits. Also, note that they’re different for different model computers. wherever they are, they’re like a brick wall that your program can’t smash through. The only way to get to the other side is to find a clever way around the obstacle. This month we’ll find the wall and do some exercises that will allow us tto think about it.

Enter the following program and try to measure the amount of time it takes to run. (A good measurement would require a stop watch, but don’t get all that fanatical!)

1 FOR J=1 TO 10 STEP 1
2 NEXT J

Those with some knowledge of BASIC will realize that the STEP 1 part is unnecessary, but include it anyway for continuity with what will come later.

When the program is done, type PRINT J then ENTER. You may be surprised at the result, but it gives some insight as to how FOR/NEXT loop works.

Next, type in the following program. Please pay careful attention to the number of zeroes.

1 FOR J= 10000000 TO 10000010 STEP 1
2 NEXT J

RUN the program. Note that making J larger does not make the program run slower. type PRINT J and ENTER to see a result that is not too surprising anymore.

Next type in:

1 FOR J = 10000000000 TO 10000000000
    10 STEP 1
2 NEXT J

RUN the program and time it. If you get impatient, hit BREAK and then type PRINT J and ENTER to see how far J has gone. No matter how long you wait before hitting BREAK, the result will be the same. You’ve just run into the brick wall!!

Is J to big? Just in case it’s not, let’s change something else first. Type in :

1 FOR J = 10000000000 TO 10000000010 STEP 2
2 NEXT J

This seems to run fine. Perhaps the problem isn’t with J!

Let’s try something completely different. You don’t need a fantastic background mathematics to know that:

The 3’s simply cancel each other out. let’s do this in a program:

1 LET A=1
2 LET B=A
3 LET B=B/3
4 LET B=3*B
5 IF A=B THEN PRINT "EQUAL"
6 IF A is more or less than B THEN
  PRINT "NOT EQUAL"

Walking through the program, we see that we see that we set A=B=1 in line 1 and 2. In line 3 B becomes 1/3. In line 4, B becomes 1 again. Therefore, from lines 5 and 6, we’d think that the result should be “EQUAL”. Don’t make any bets! Try the program out and see for yourself!

It shouldn’t what order we do the multiply and divide so let’s swap lines 3 and 4 as follows:

3 LET B=3*B
4 LET B=B/3

First, check to see that the changed program should do the same thing and RUN it. Why does the answer come out diferent? We’ve just run into a brick wall again, and though it’s the same wall we hit before!

Why does this happen? If I included an explanation here, this article would become a bit cumbersome, but I promise to continue with it next time. In the meantime, think about the problem. Change the programs around. note any “sudden” changes when the numbers you use are powers of two, or almost powers of two! It’s good to understand this problem, because it can crop up in many other (not to obvious) ways, and understanding it can save you many hours of head scratching when your “perfect” program just won’t work.

Wes Brzozowski
SINCUS, March 1984