Lesson 2-3: If-then Statements in Computer Programs (Day 23)

Today I subbed in a high school special ed English and history class. (Recall that this entire week of subbing is likely to be special ed!) The only class that's not with an aide or co-teaching is academic enrichment/study skills, and so as usual there is no "A Day in the Life."

I'm hoping to find someone who needs help with math in the academic enrichment class. But the only such student is working on identifying functions, which is of course easy. Thus my help isn't needed.

The other classes are all juniors. There is one U.S. History class and two English classes. Many of the juniors in history are also enrolled in one of English classes. And indeed, the aide warns me that the toughest class is the history class, if only because the misbehaving students are split up in English but all together in history. So let's look at the history class in slightly more detail.

The students begin with a Warm-Up where they must define and use the Word of the Day -- in this case, boycott, in a sentence. Then the main activity is to answer 35 questions from the actual citizenship test taken by immigrants. They must write down their guesses almost like a quiz, and then make corrections after we reveal the answers. Here are some of the questions:

21. The House of Representatives has how many voting members? (Answer: 435)
27. In what month do we vote for President? (Answer: November)
28. What is the name of the President of the United States now? (Answer: Donald Trump)
31. If both the President and Vice President can no longer serve, who becomes President? (Answer: Speaker of the House)
33. Who signs bills to become laws? (Answer: President)
34. Who vetoes bills? (Answer: President)

I motivate the students by pointing out a common complaint made by "traditionalists" (or their counterparts in history class) -- many Americans these days couldn't pass the citizenship test! So let's prove them wrong by showing them that we do indeed know this stuff.

There are two behavior problems today (one phones, one food). The aide tells me it's fortunate that we don't have to kick anyone out (sending them to the special ed math classroom across the corridor).

Unfortunately, we run out of time before giving the correct answers. It doesn't help that first, today is Monday, which at this high school means that it's a late day with shorter classes. It also doesn't help that this is the period when the Pledge of Allegiance and announcements are given.

Lesson 2-3 of the U of Chicago text is called "If-then Statements in Computer Programs." It does not appear in the modern Third Edition of the U of Chicago text, and we can see why when we look a little at what I wrote last year on the subject:

Lesson 2-3 of the U of Chicago text discusses computer programs written in BASIC. We must remind ourselves that this book was written over 20 years ago, back when BASIC was a popular language. But now, BASIC has been derided as "spaghetti code" and isn't as widely used anymore.

And so the Third Edition avoids this issue by leaving out this lesson entirely. Two years ago, I changed the lesson to use TI-BASIC, the language of the TI graphing calculator, instead. But today I have do access to something that runs BASIC programs -- the emulator of my old 1980's computer:

http://www.haplessgenius.com/mocha/

Whereas human languages such as English are illogical, computer languages are supposed to be logical.

So for today, I'll post the old TI-BASIC worksheets from last year. But I'm actually going to write about BASIC itself using the emulator.

Let's start by writing the four BASIC programs used in the U of Chicago text. All four of these programs run on the emulator:

Program #1: Number of Diagonals in Polygon

10 PRINT "COMPUTE NUMBER OF DIAGONALS IN POLYGON"
20 PRINT "ENTER THE NUMBER OF SIDES"
30 INPUT N
40 IF N>=3 THEN PRINT "THE NUMBER OF DIAGONALS IS "; N*(N-3)/2
50 END

Program #2: Inventory of Electro-Robots

10 PRINT "INVENTORY OF ELECTRO-ROBOTS"
15 PRINT "ENTER THE NUMBER OF ELECTRO-ROBOTS"
20 INPUT N
25 PRINT "PROFIT EQUALS";5*N-1500
30 IF N<300 THEN PRINT "ORDER MORE ELECTRO-ROBOTS."
35 END

Program #3: Area of Circle

10 INPUT R
20 LET A=3.14159*R*R
30 IF R>0 THEN PRINT R,A
40 END

Program #4: Diagonals in Many Polygons

10 PRINT "NUMBER OF DIAGONALS IN POLYGONS"
20 FOR N=3 TO 20
30 PRINT "THE NUMBER OF SIDES IS";N
40 PRINT "THE NUMBER OF DIAGONALS IS";N*(N-3)/2
50 NEXT N
60 END

All of these programs work on the emulator. Actually, my computer doesn't require the last line of the program to be END -- we could omit each of those final lines. Also, my computer doesn't require line 20 of Program #3 to begin with LET -- just 20 A=3.14159*R*R is sufficient. Don't forget to type in NEW to erase the old program before entering the new one.

Now let's write some programs of our own. Earlier when we were reading Ogilvy, there was mention of a GCD algorithm. Let's try to write it in BASIC.

The main problem here is that BASIC doesn't do long division with quotient and remainder -- instead it only does decimal division (or "floating-point division"). Remainders, as we see above, are critical to the algorithm. But it's possible -- though not easy -- to use floating-point division for remainders.

Let's go back to the example above -- the GCD of 30 and 108. We need the remainder of 108/30, but if we ask BASIC to find 108/30, it calculates it as 3.6. We need to convert 3.6 into a remainder.

The key function is the INT function. INT represents the ceiling function in mathematics (as in the greatest-integer function). So INT(3.6)=3. Well, this gives us the quotient, but we need the remainder.

Hmmm, the part that relates to the remainder is the fraction part. We can find this by subtracting the integer part from the original number: 3.6-INT(3.6)=.6. This fractional part is 18/30, so we must multiply it back by 30 to obtain the remainder -- 18.

Theoretically, this should work. The problem is that all this division produces rounding errors -- and such rounding can lead to incorrect answers. For example, let's go back to Program #3 that calculates the area of a circle. If we try entering a radius of 4 or 5, there is a rounding error that becomes obvious after trying a radius of 1, 2, or 3 first:

r     Area (as given by emulator)
1    3.14159
2    12.56636
3    28.27431
4    50.2654401
5    78.5397501

That "01" at the end of the areas for 4 and 5 stick out like a sore thumb. And no, the "01" has nothing to do with using pi to more accuracy, since it would be 50.2654825 instead (and besides, we never gave the program those extra digits of pi).

The reason for the inaccuracy is that computers work in binary, not decimal. The decimal 3.14159 actually means 3+14159/100000, but fractions with a denominator of 100000 (or anything other than a power of two) can't be expressed exactly in binary. The difference between 3.14159 and whatever binary fraction the computer uses is small enough not to appear when multiplying by 4 or 9, but when we multiply by 16 or 25 it appears. This problem never occurs if we only use binary fractions such as .5, .125, and so on.

And this is just multiplication -- in division, we're even more likely to have rounding errors. We know that fractions like 1/3 trip us up in both decimal and binary. Here, we must multiply .6 by 30 to obtain our remainder 18, but .6 isn't a binary fraction. Therefore, we'll obtain something like 17.9999999 or 18.0000001 instead of 18 as the remainder. This will trip up the algorithm -- it's supposed to stop when the remainder is zero, but it'll never reach zero if we have 17.9999999 or 18.0000001.

Using INT will work if we have 18.0000001, but INT(17.9999999)=17 instead of the desired 18. To solve this problem, we implement 4/5 rounding by adding .5 to the number before taking INT. This works, since both INT(18.4999999) and INT(18.5000001) are equal to 18.

Here is our GCD program, written in BASIC:

10 PRINT "INPUT TWO NUMBERS"
20 INPUT A,B
30 IF B=0 THEN PRINT "THE GCD IS";A: END
40 Q=A/B
50 R=INT((Q-INT(Q))*B+.5)
60 A=B
70 B=R
80 GOTO 30

You may notice a few things about how this program is written:

• The program doesn't end with END. In fact, END appears at the end of line 30, because we really want the program to end after printing the GCF rather than proceed to line 40.
• LET is omitted, as my computer allows.
• INPUT A,B allows us to enter both numbers using a comma.
• The strange part is that the IF statement (which is the subject of Lesson 2-3) appears near the start of the program. Actually, most GCD programs are written this way, in order to safeguard against the user entering 0 as one of the numbers. The program ends before reaching line 40 and thus avoids division by zero.
• After the division, if the remainder R=0, then the final answer is in B. But the values in B and R have moved to A and B before we reach the GOTO and IF statements. Therefore B is the value that we test for zero, and A contains the final answer.

Notice that in TI-BASIC, we have a fPart function that gives us the fractional part directly without needing int. To avoid rounding error, we use the round function -- 0 here means no decimal places (nearest integer):

PROGRAM:GCD
:Disp "2 NUMBERS"
:Input A
:Input B
:While B
:round(fPart(A/B)B,0)->R
:B->A
:R->B
:End
:A

[2019 update: Yes, I just wrote about Round last week after that special ed math class. This is the real reason why the Round function exists -- to round variables, not constants like round(17.9999999,0).]

In this program, both Goto and If are avoided because we used a While loop instead. The While loop does the testing -- the loop is executed while B is true (nonzero) and stops when it is false (0). Here the word End ends the While loop, not the program.

In other languages, such as C++, there is a % operator that gives us remainder directly. Here is how we'd write the gcd function:

int gcd(int a, int b) {return b ? gcd(b, a%b) : a;}

Here we replaced "if" with the ternary operator ?: -- it means "If b is true (nonzero), then recursively call gcd on b and a%b (the remainder), else the answer is a."

OK, let's get back to BASIC. It's a shame that I didn't stumble onto the emulator back when I was writing about music over the summer on the Pappas music pages. Now that I have the emulator, I can't help but try to play microtonal music using the SOUND command in BASIC.

In an earlier post, we discovered that the most important number when making music using SOUND on the computer is 261. As it turns out, SOUND is based on EDL, or equal divisions of length, where the length of the string is the number of steps it takes to get to 261, the "bridge." For example, Sound 61 is 200 steps away from the bridge, while Sound 161 is 100 steps away from the bridge. Thus the interval between Sounds 61 and 161 is 200/100 or 2/1, which is an octave. (To make it easier to understand, the word "Sound" refers to the actual number used in the SOUND command, while "Degree" refers to the number of steps from away from Bridge 261.)

[2019 Update: Obviously, in past years I used today's BASIC post as an excuse to go back to Mocha music written in BASIC.]

10 INPUT "EDO";N
20 DIM R(N), D(N)
30 FOR S=0 TO N
40 R(S)=2^(S/N)
50 NEXT S
60 M=N
70 FOR L=12 TO 260 STEP 2
80 PRINT "TESTING EDL";L
90 E=0
100 FOR S=0 TO N
110 D=L/R(S)
120 E=E+ABS(D-INT(D+.5))
130 NEXT S
140 IF E>=M THEN 190
150 FOR S=0 TO N
160 D(S)=INT(L/R(S)+.5)
170 NEXT S
180 M=E
190 NEXT L
200 CLS
210 PRINT "PLAYING SCALE"
220 FOR S=0 TO N
230 PRINT "DEGREE";D(S);"SOUND";261-D(S)
240 SOUND 261-D(S),4
250 NEXT S
261 END

(Note: Line 40 requires an up-arrow where you see the ^ caret.)

Here's how the program works -- the user inputs the desired EDO in line 10. Lines 30-50 set up the correct ratios for your EDO -- so if you choose 12EDO, then the ratios are 2^(0/12), 2^(1/12), 2^(2/12), all the way up to 2^(12/12).

Lines 70-190 set up a loop to test every EDL, from the shortest (12EDL) to the longest (260EDL). It calculates the error E between the correct ratio and closest possible degree available (notice how INT(D+.5) is used to round D to the nearest degree). The IF statement in line 140 is used to see whether E is less than the minimum error M encountered so far. If E>=M, then we skip to line 190 and check the next EDL. If E<M, then we have a new "best EDL so far," and lines 150-170 set up a loop to replace the list of "degrees of the best EDL so far" with the new list.

Afterwards, the final loop from lines 220-250 actually play the best scale on the computer. (Don't forget to click the "Sound" box in order to hear the sound!) I decided to make the length 4 because just as the magic number for pitch is 261, the magic number for duration is 32 (whole note). As today's the start of the second quaver, let's make it play quavers, so 32/8 = 4. The final END line isn't needed, but I include it just as an excuse to honor Bridge 261 with a line 261.

Here are the best possible scales the computer found for some EDO's:

5EDO: use 256EDL (Degrees 256, 223, 194, 169, 147, 128 -- Sounds 5, 38, 67, 92, 114, 133)
7EDO: use 156EDL (Degrees 156, 141, 128, 116, 105, 95, 86, 78)
10EDO: use 256EDL (add Degrees 239, 208, 181, 158, 137 in between 5EDO)
12EDO: use 232EDL (Degrees 232, 219, 207, 195, 184, 174, 164, 155, 146, 138, 130, 123, 116)
16EDO: use 214EDL (Degrees 214, 205, 196, 188, 180, 172, 165, 158, 151, 145, 139, 133, 127, 122, 117, 112, 107)

I actually recommend not going past 12EDO, since the error E rises sharply. If you must try a higher EDO, then use 16EDO as it has the least error. Other multiples of 4 (20EDO, 24EDO, 28EDO) have lower errors for their size, while 22EDO and 31EDO (mentioned in earlier posts) also have lower errors for their size. Beyond 31EDO, all scales are about equally bad (with the odd EDO's marginally better than the even EDO's).

It's interesting that 232EDL is the best for 12EDO, since the EDL link I mentioned in an earlier post recommended 120EDL and 196EDL (among others) to make a 12EDO scale.

But to me, making EDO scales is such a waste. The computer uses EDL's, which are based on exact divisions of length, so we should be playing sounds in just intonation, not EDO's.

[2019 Update: OK, let's cut out the end of this old music post, since I started babbling on about Kite's colors, which have since changed. See previous music posts for more info on the colors.]