Previously, I began to dissect my old VIC-20 game Sky-Ape-Er. It was made up of two BASIC programs:
INSTRUCTIONS – Display instructions, set up custom character set, then load and run the main game.
SKY-APE-ER – The main game.
VIC-20 custom fonts
The VIC-20 did not have a true graphics screen. Instead, it used font characters that could be dynamically changed. Each character on the 22×20 screen was 8×8. You could create custom 8×8 characters to represent anything you wanted.
I believe I used a program called Eight by Eight Create by Robert Spahitz from the January 1983 issue of Creative Computing (Vol 9, Number 1). See page 270 (or 272 of this PDF scan):
This also helps me confirm that I got my VIC-20 in 1982 since I initially did not have a Commodore Datasette tape deck for it and had no way to save programs until later. By the time this issue came out, I had the tape deck.
But I digress…
VIC-20 custom fonts on the CoCo
I have screen shots of what the custom characters looked like in the VIC-20 game, but thought it would be fun to take those DATA statements and display them on my CoCo. Using lines 100 to 125 from the INSTRUCTIONS program, I created this Color BASIC program:
0 REM skychars.bas
5 POKE 65495,0
10 CLS:XO=4:YO=2
15 DIM BM(7):FOR A=0 TO 7:BM(7-A)=(2^A):NEXT
20 FOR R=0 TO 7
25 READ V:IF V=-1 THEN 99
30 FOR C=0 TO 7
35 IF V AND BM(C) THEN SET(XO+C,YO+R,8) ELSE RESET(XO+C,YO+R)
40 NEXT
45 NEXT
50 XO=XO+10:IF XO>60 THEN XO=4:YO=YO+10
55 GOTO 20
99 GOTO 99
100 DATA223,223,223,0,253,253,253,0,0,0,0,0,1,3,3,7,0,60,126,219,129,165,165,129
105 DATA0,0,0,0,128,192,192,224,31,63,127,255,252,254,127,63,0,126,126,0,255,0,231,231
110 DATA248,252,254,255,63,127,254,252,15,7,8,30,31,31,31,31,231,219,60,255,126,126
115 DATA189,195,240,224,16,120,248,248,248,248,31,31,31,15,15,63,127,0,231,129,0,0,129
120 DATA129,129,0,248,248,248,240,240,252,254,0,12,12,24,47,8,15,82,36,48,48,24,244,16
125 DATA240,74,36,28,8,28,42,8,20,20,54,12,76,40,47,40,159,82,36
130 DATA -1
It now displays what those font characters look like:
VIC-20 Sky-Ape-Er font display on a CoCo.
These custom characters would replace “@ABCDEFGHIJKLMNOP”. The “@” symbol was the brick used to make the game playfield.
Letters A-L were used to make the ape, like this:
ABC
DEF
GHJ
JLK
Letters M-O were the player’s character, facing right, left and forward.
Letter P were the small apes that were running towards the player. They never turned back, so no additional characters we needed for them.
My program was written to just put those characters on the screen, which would look like this:
My VIC-20 Sky-Ape-Er game without the custom font.
But with the custom font in use, it looks like this:
In the next installment, I’ll walk through the actual SKY-APE-ER game code and see how it works.
Tonight, I saw this YouTube video from Robin at 8-Bit Show and Tell. He was responding to someone who noticed a bit of code in an old Commodore magazine that did:
IF Z>192 THEN IF Z<219 THEN Z=Z-128
…instead of the more common…
IF Z>192 AND Z<219 THEN Z=Z-128
He performed a benchmark very much like the ones I have been doing on the CoCo (I’m glad I’m not the only one doing this). I decided to try it on the CoCo and see what happened here.
I first tried the normal “IF AND THEN” way:
0 REM IFAND.BAS
5 DIM TE,TM,B,A,TT
10 FORA=0TO3:TIMER=0:TM=TIMER
20 FORB=0TO1000
30 IF Z>192 AND Z<219 THEN Z=Z-128
70 NEXT
80 TE=TIMER-TM:PRINT,TE
90 TT=TT+TE:NEXT:PRINTTT/A:END
This produced 875 on my Xroar emulator.
Then I tried the “odd” IF AND THEN way…
0 REM THENIF.BAS
5 DIM TE,TM,B,A,TT
10 FORA=0TO3:TIMER=0:TM=TIMER
20 FORB=0TO1000
30 IF Z>192 THEN IF Z<219 THEN Z=Z-128
70 NEXT
80 TE=TIMER-TM:PRINT,TE
90 TT=TT+TE:NEXT:PRINTTT/A:END
This produced 472! A significant time savings just by changing the way you compare multiple things.
Thinking this through, I have some theories, based on some very inefficient C code I found in a work project once.
“IF this AND that THEN” surely isn’t doing a logical AND for values, is it? It might be, since you can print a comparison like this:
PRINTing the result of a comparison in Color BASIC.
In Color BASIC, true is -1 and false is 0. So perhaps doing this:
IF A=1 AND B=2 THEN PRINT "BOTH ARE TRUE"
…is actually turning into…
IF -1 AND 0 THEN PRINT "BOTH ARE TRUE"
…with -1 or 0 being used based on the conditions. Let’s try:
Color BASIC must not be doing bitwise math for compares.
Oh my. Maybe it IS doing this, thus requiring the values to be saved and compared, making it slower just like C generating more code to do the same thing.
I know I could just look at the disassembly in Color BASIC Unravelled and know exactly what is going on, but it’s more fun to experiment. How can we test this?
Well, things that return true/false return -1 or 0. You can AND two numbers together and get mathematical results. Even a compare like:
IF A$="ALLEN" THEN
…will return a -1 if it is true, or a 0 if it is false:
Even string compares turn into -1 or 0.
It sure seems likely that BASIC is just taking the result of a compare (true or false, -1 or 0) and AND-ing or OR-ing those values. Thus, my theory is this:
Multiple AND/OR comparisons turn into multiple results of -1 or 0 (true or false) which are then mathematically processed:
IF A=1 AND B=2 AND C=3 THEN ...
…so all of it has to be processed. But, using this IF THEN IF approach:
IF A=1 THEN IF B=2 THEN IF C=3 THEN ...
…will be much faster since it does a compare, then if good, it does another compare, then if good, it does the final compare… rather than having to do three compares then do math on the three results of that compare then check that final result to know what to do.
What says you?
I suppose it gets much slower the more conditions you want to compare:
5 DIM TE,TM,B,A,TT
10 FORA=0TO3:TIMER=0:TM=TIMER
20 FORB=0TO1000
30 IF X=1 AND Y=1 AND Z=1 THEN Z=42
70 NEXT
80 TE=TIMER-TM:PRINT,TE
90 TT=TT+TE:NEXT:PRINTTT/A:END
763 for that one. Versus:
5 DIM TE,TM,B,A,TT
10 FORA=0TO3:TIMER=0:TM=TIMER
20 FORB=0TO1000
30 IF X=1 THEN IF Y=1 THEN IF Z=1 THEN Z=42
70 NEXT
80 TE=TIMER-TM:PRINT,TE
90 TT=TT+TE:NEXT:PRINTTT/A:END
335!
So obviously I have to do this:
5 DIM TE,TM,B,A,TT
10 FORA=0TO3:TIMER=0:TM=TIMER
20 FORB=0TO1000
30 IF G=1 AND H=1 AND I=1 AND J=1 AND K=1 AND L=1 AND M=1 AND N=1 AND O=1 AND P=1 AND Q=1 AND R=1 AND S=1 AND T=1 AND U=1 AND V=1 AND W=1 AND X=1 AND Y=1 AND Z=1 THEN Z=42
70 NEXT
80 TE=TIMER-TM:PRINT,TE
90 TT=TT+TE:NEXT:PRINTTT/A:END
If those 10 conditions are true, do something… Testing this produces: 4782
And doing it the weird way:
5 DIM TE,TM,B,A,TT
10 FORA=0TO3:TIMER=0:TM=TIMER
20 FORB=0TO1000
30 IF G=1 THEN IF H=1 THEN IF I=1 THEN IF J=1 THEN IF K=1 THEN IF L=1 THEN IF M=1 THEN IF N=1 THEN IF O=1 THEN IF P=1 THEN IF Q=1 THEN IF R=1 THEN IF S=1 THEN IF T=1 THEN IF U=1 THEN IF V=1 THEN IF W=1 THEN IF X=1 THEN IF Y=1 THEN IF Z=1 THEN Z=42
70 NEXT
80 TE=TIMER-TM:PRINT,TE
90 TT=TT+TE:NEXT:PRINTTT/A:END
…speeds up to 732!
Well I’ll be. It looks like, even though its longer code, it’s much faster. I never knew that. Or if I did, I forgot it long ago.
Thanks, Robin, for posting that video a few years ago. Very cool! Here’s his original video:
When I was working on my SirSound project, I had to create my own implementation of the Extended Color BASIC “PLAY” command. I did this by going through the Extended BASIC Unravelled book and looking at the 6809 assembly for the command.
…and while doing so, discovered an interesting thing about the PLAY parser and how it handled the notes.
The PLAY command operates by reading a command followed by an option modifying. For instance, “V10” is the command “V” for volume, and a modifier “10” for volume level 10. “T8” is command “T” for tempo and “8” for the speed.
When it comes to playing musical notes, PLAY understands the standard scale notes of C, D, E, F, G, A and B. When it parses a command letter, it then looks to see if a modifier is after it. The modifiers include “#” and “+” for sharp, and “-” for flat.
This allows you to play the full 12 note scale:
Using sharps: C C# D D# E F F# G G# A A# B (or C C+ D D+ E F F+ G G+ A A+ B)
Using flats: C D- D E- E F G- G A- A B- B
These notes correspond to the notes found on a piano keyboard:
Piano keyboard, one octave.
I don’t understand music theory, but I know enough to say the white keys are the natural notes (CDEFGAB) and the black keys are a half step in between and are either sharps of the note before it (C# D# F# G# A#) or flats of the notes after it (Db Eb Gb Ab Bb). There is no E# or Fb or B# or Cb on a keyboard.
But, the BASIC PLAY parser does not add any code to prevent you from playing them anyway :-)
PLAY “E# F” (E sharp and F natural) will play the same note.
PLAY “E F-” (E natural and F flat) will play the same note.
But you can’t PLAY “C-” (C flat) or “B#” (B sharp) because it knows to reject those modifiers from the notes at each end of the scale.
CoCo can play notes that are not on a piano keyboard :-)
To me, this seems like a bug, but I implemented in my PLAY PARSER code anyway, just in case anyone used it. But since I lack any music theory background, I am probably wrong, as I have been told there is a reason for this.
For for someone like me with limited music background, it seemed like an odd thing to stumble upon in the code. I even documented in my SirSound documentation:
NOTE —- N (optional) followed by a letter from “A” to “G” or a number from 1 to 12. When using letters, they can be optionally followed by “#” or “+” to make it as sharp, or “-” to make it flat. When using numbers, they must be separated by a “;” (semicolon).
C C# D D# E F F# G G# A A# B (sharps) 1 2 3 4 5 6 7 8 9 10 11 12 C D- D E- E F G- G A- A B- B (flats)
Due to how the original PLAY command was coded by Microsoft, it also allows sharps and flats that would normally not be allowed. For instance, E# is the same as F, and F- is the same a E. Since notes are numbered 1-12, the code did not allow C- or B#. This quirk is replicated in this implementation.
SirSound documentation.
Ah, the things that amuse those of us without the brainpower to understand them.
YouTube decided to show me a video by 8-Bit Show And Tell. It is a BASIC driving game called “10 PRINT RACER” for the Commodore PET. For those that don’t know, “10 PRINT” is a one line Commodore BASIC program that generates a maze by randomly printing slash and backslash PETASCII characters.
…but using the ASCII “/” and “\” characters just doesn’t have the same effect:
CoCo version of the famous Commodore “10 PRINT” program.
But I digress…
10 PRINT RACER
The game, 10 PRINT RACER, was based on this maze program. You drive a car through a passage in the middle of a random maze. The video demonstrates the game and then walks through the code, line by line.
I was impressed with his awareness of speeding up BASIC, such as using a FOR/NEXT loop with STEP 0 to create an infinite loop that is faster than using a GOTO. He also removes unnecessary spaces and combines lines together for faster execution. Heck, he even knows about using a period as a faster way to make zero!
My PET experience
I’ve actually written programs for the PET. My high school had some, and I wrote a banner printing program for my typing teacher. She’d already written PRINT statements for each large letter based on needlepoint patterns, but there wasn’t enough memory in the PET to load them at the same time.
I solved this problem by having a main program input the message to print, then POKEing it to screen memory along with a “which character are we printing” counter. If the character to print was not in the current program, it would load and run the one that contained it. Those programs would then PEEK that screen memory to see what character it was supposed to print next.
A klunky solution, but it worked. (And in case you wondered why I used screen memory… I did not have a PET memory map, so I didn’t know where I could store the message data. I knew I could find screen memory by printing something on the screen and then PEEKing through memory until I found it. Once I located where the screen was stored, I used that for temporary memory. Funny enough, I did the same thing years later for my *ALLRAM* BBS when I needed a safe spot to temporarily load and execute PCLEAR 0 code.)
But I digress… Again.
From Commodore PET to Radio Shack CoCo
Inspired by the video, I decided to port the game over to Color BASIC. This involved a few things:
Screen Size: The PET screen is 40×25, so I had to scale everything down to fit on the CoCo’s 32×16 screen.
PETASCII: The game uses two special characters which are not part of the standard ASCII that the CoCo has. I substituted with a forward slash (“/”) and a back slash (“\”). It doesn’t look as maze-like as the PET version, but it is the same general idea. There is also a PETASCII character that you print to clear the screen. I replaced that with CLS.
Input: Commodore uses GET instead of INKEY$. I changed “GET A$” to “A$=INKEY$”.
Memory Map: The game uses POKE and PEEK to put the racer on the screen, and check to see if it hit something. I had to change the PET memory location to be 1024, the start of the CoCo screen. I was surprised to hear him say the Commodore 64’s screen also starts at 1024.
Spaces: Commodore BASIC has the SPC() keyword which prints that many spaces. Color BASIC has TAB() but it moves to columns, so it couldn’t be used. I created an S$ of 32 spaces using STRING$() and then used MID$() to get just the number of them I needed. This is likely much slower than if I had SPC().
Controls: The PET has a numeric keyboard, so the PET version used 4 for left, and 6 for right. The CoCo has arrow keys, so I changed it to use the left and right arrow keys. It now looks for CHR$(8) for left and CHR$(9) for right. Parsing CHR$ is slower than the original which looked for “4” and “6”.
Random Differences: I thought I was going to have to change the random numbers. The Commodore version of RND would return a value from 0 to 1. You would then multiply the result by a number (X) which gave you a number from 0 to X. On the CoCo, doing RND(X) would return 1 to X. But, I realized RND(0) on the CoCo would do the same thing, so I ended up not changing it.
Key Repeat: The Commodore has key repeat and a small typeahead buffer. At the end of the PET code there was a POKE to clear out that buffer so it wouldn’t instantly restart the game if key presses were still in the buffer. I removed that POKE since the CoCo has no such buffer.
Here is what I came up with:
CoCo port of 8-Bit Show And Tell’s “10 PRINT RACER” BASIC game.
I tried to keep the code as close to the original as I could, so there are some more optimizations that we could do on the CoCo. For instance:
Instead of using “RND(0)*10” for a value of 0-9, it might be faster to do RND(10) and adjust the IF/THEN to look for 1-10 instead of 0-9. This would save the overhead of doing the multiplication.
If Extended BASIC can be used, then most constants can be changed to HEX values and they will be slightly faster. (Thought after seeing some code from Jim Gerrie recently, it may still be faster to parse some single digits as decimals over their HEX version. More on this in a future article.)
Line 30 and 40 could be combined using ELSE, saving time each time the value is less than 5. Currently, if X is 1, it processes line 40 and then goes to line 50 which checks X again. Using ELSE would at least omit that step in that condition.
The screen position variable (S) gets the car position (C) added to it each time it is POKEd or PEEKed. To save that math, the position of the car could be initialized as S+C and the two “+C”s in the code could be removed.
There is a special IF in line 70 that is used to initially draw the screen before letting the car drive on it. Once the screen is drawn, it still checks this IF every time through. Time could be saved by drawing the initial screen outside of the main loop and then not needing to check that again.
What else do you see that might help speed things up? Please leave your comments, or take this code and see what you can do with it.
PET emulator online
If you never got the pleasure of using one of these early Commodore Business Machines, I found a PET emulator that runs from a web browser:
Not prepared to let an MC-10 beat a CoCo, I wanted to try it myself on my test system, the Xroar emulator.
I did. And I got 10.75 seconds! The CoCo is slower than the MC-10?
But that’s still faster than our previous best attempt of 13.3 seconds by Xroar author Ciaran Anscomb. Maybe I can speed the CoCo up a bit. Someone commented that DISK BASIC was slightly slower due to hooking in to an interrupt (I think it uses that for a time delay when turning off the drive motor after disk access). Since the MC-10 doesn’t have DISK anyway, I thought I’d disable RS-DOS and try it again.
11.78 seconds without Disk BASIC. IT got even slower? That’s odd. I tried this last night on the Mac Xroar emulator and thought it was slightly faster.
We have seen variances between emulators and systems when it comes to timing, so at some point we need to find a better way to do this. I mean, the MC-10 can’t be faster, can it?
Speaking of the MC-10, first, you should be aware that JIm Gerrie is one of the most prolific programmers around, porting and writing software on what seems to be a daily basis. Just check out his YouTube channel sometime. He has an incredible version of the Rally-X arcade game, entirely in BASIC.
But I digress.
I want to point out that Jim normally wouldn’t have been able to run my scaling demo on an MC-10 since it does not include a TIMER function, nor does it support HEX numbers (as far as I know?). He is using MCX BASIC by Darren Atkinson. Darren is the designer behind the CoCoSDC floppy disk replacement project. MCX-BASIC adds things like TIMER and HEX to the MC-10, making it closer to Extended Color BASIC on the CoCo.
But I digress again.
Adam
In the previous article, Adam shared the results of his version, and has now posted his code:
1 DIM SW,SH,SM,S,TM,Z,W,H,P
2 DIM A,B,C,D,E,F,L$
3 SW=8:SH=5.33333334:SM=.1:S=.5
4 B=32:C=175:D=15:E=2:F=7
5 TM=TIMER
6 FORZ=1TO100
7 W=INT(SW*S):H=INT(SH*S)
8 P=D-INT(W/E)+(F-INT(H/E))*B
9 L$=STRING$(W,C)
10 CLS
11 FORA=1TO H:PRINT@P+A*B,L$:NEXT
12 S=S+SM
13 IF H<1 OR H>D THEN SM=-SM:S=S+(SM*E)
14 NEXT
15 PRINT:PRINT (TIMER-TM)/60;”SECONDS”
On my Xroar CoCo 2 test platform I get 17.93 seconds. Adam also sent in an interesting note which may explain some of the timing differences I am seeing reported:
This exercise also highlights the speed differences between a Coco2 and Coco3. I think the GIME chip is slower than the VDG in printing to the low-res screen. A Coco3 runs this code roughly 2 seconds slower!
Adam
Now that is an interesting observation. When I got my CoCo 3, my old machine went back in the box and I never had them both hooked up at the same time to do any comparisions.
I knew that the CoCo 3 40/80 column screens seemed slower. There are patches floating around that speed them up dramatically. Apparently it does some kind of MMU memory bank switch in and out for each character displayed. I did not realize there would be any difference in the 32 column VDG style screen. I’ll have to look into this and see if I can find out why.
Walter Zambotti
On the CoCo mailing list (if you use e-mail, and like the CoCo, you should sign up), Australian Walter Zambotti saw the original example and provided a tip:
Try changing the inner loop to remove all calculations like this
115 P2-P+32:H2=P*H+32:BK$=STRING$(W,175) 120 FOR A=P2 TO H2 STEP 32 130 PRINT @A,BK$ 140 NEXT A
I believe I chopped 7 seconds off the time.
Walter Zambotti via CoColist on March 13, 2020
It seems others picked up on this as well, as I have seen some speedy attempts that pre-calculate values (so the FOR/NEXT loop only has to increment by 32 to get to the next line for PRINT) and pre-render the string of blue blocks. (I was aware of strings being quite slow after my String Theory experiments, but some of the pre-calculated values I would not have thought of.)
Nice job, Walter!
Mission: Beat the MC-10
This leaves us with a problem. Jim Gerrie’s MC-10 version is still the fastest. Perhaps the 6800 in the MC-10 and it’s BASIC is just faster. Perhaps Jim’s just better at BASIC than we are. I’m willing to accept the second part, but my pride doesn’t want the first part to be true.
Can you make this faster than what Jim did? With the various attempts shared so far, perhaps bits and pieces of each of them could be combined to create something even faster?
Here is the original un-optimized code again for reference:
0 REM scale.bas
10 SW=32/4 ' SCALE WIDTH
20 SH=16/3 ' SCALE HEIGHT
30 SM=.1 ' SCALE INC/DEC
40 S=.5 ' SCALE FACTOR
70 TM=TIMER:FOR Z=1 TO 100
80 W=INT(SWS) 90 H=INT(SHS)
100 P=15-INT(W/2)+(7-INT(H/2))32 110 CLS 120 FOR A=1 TO H 130 PRINT@P+A32,STRING$(W,175)
140 NEXT A
150 S=S+SM
160 IF H<1 OR H>15 THEN SM=-SM:S=S+(SM*2)
170 NEXT Z
180 ' 60=NTSC 50=PAL
190 PRINT:PRINT (TIMER-TM)/60;"SECONDS"
If you don’t have access to a real CoCo or emulator, you could use one of these from a web browser:
Although there is a way to load code into them, I am not sure if there is a way to get the code back out. However, I have been typing my BASIC up in a text editor on my Mac. Xroar allows mounting a test file (with the extension of .bas or .asc) as a cassette tape, then doing a “CLOAD” to load it in as if it were a program saved to tape in ASCII format. This allows me to edit and make changes on my Mac, then load the results into Xroar for testing.
If you try Xroar Online, set the “Machine:” type to “Tandy CoCo (NTSC)” to match the timing of the emulated Amercian CoCo I am using (where TIMER is 60 tickts per second, versus the PAL version that is 50 per second). Then, save out the code as a text file and mount it using the “Tape:” insertoption. You can then type CLOAD in the emulator to load and RUN it.
Load ASCII BASIC as if it was a tape via Xroar Online.
In my Optimizing Color BASIC series, one of the things I learned was how much faster it was to use HEX values instead of decimal values. For example:
A=65535
A=&HFFFF
Even though the second statement is one character more to parse, it is still much faster since it’s easier for the interpreter to calculate base-16 values than base-10. This was even the case for zero:
A=0
A=&H0
Somewhere in the comments, CoCoSDC creator Darren Atkinson let me know about using just a period for zero. I wrote tested that in part 9.
Recently (March 28), Carlos Comacho tagged me in the Facebook CoCo group about something he found on a NEC PC-6001 Z-80 computer testing various ways to set something to zero. Here is the screenshot he shared:
NEC PC-6001 benchmarking.
Using a decimal 0 and HEX &H0 were tested, as well as using VAL(“”). Huh?
VAL entry from the CoCo 3 BASIC quick reference guide.
I am aware of using this to convert a STRING to a number, such as when using LINE INPUT:
10 LINE INPUT "ENTER YOUR AGE:";A$
20 A=VAL(A$)
30 IF A=42 THEN PRINT "ULTIMATE AGE!"
It also handles decimal values, such as A=VAL(“12.34”). And I guess I knew that if you passed it an empty string, it would return zero because pressing ENTER on a LINE INPUT prompt that then went into VAL would return 0…
VAL() with an empty string will return 0.
Let’s do nothing!
Of course I had to benchmark this and see what CoCo did with it! Here’s the current version of my BASIC benchmark test:
0 REM BENCH0.BAS
5 DIM TE,TM,B,A,TT
10 FORA=0TO3:TIMER=0:TM=TIMER
20 FORB=0TO1000
30 Z=0
70 NEXT
80 TE=TIMER-TM:PRINTA,TE
90 TT=TT+TE:NEXT:PRINTTT/A:END
Running this produces a value of 189. Next we try HEX &H0:
0 REM BENCHX0.BAS
5 DIM TE,TM,B,A,TT
10 FORA=0TO3:TIMER=0:TM=TIMER
20 FORB=0TO1000
30 Z=&H0
70 NEXT
80 TE=TIMER-TM:PRINTA,TE
90 TT=TT+TE:NEXT:PRINTTT/A:END
That shows 174. Now let’s do the one with the period:
0 REM BENCHDOT.BAS
5 DIM TE,TM,B,A,TT
10 FORA=0TO3:TIMER=0:TM=TIMER
20 FORB=0TO1000
30 Z=.
70 NEXT
80 TE=TIMER-TM:PRINTA,TE
90 TT=TT+TE:NEXT:PRINTTT/A:END
That one gives me 147 – the fastest so far! And lastly, the silly VAL(“”) empty quote thing:
0 REM BENCHVAL.BAS
5 DIM TE,TM,B,A,TT
10 FORA=0TO3:TIMER=0:TM=TIMER
20 FORB=0TO1000
30 Z=VAL("")
70 NEXT
80 TE=TIMER-TM:PRINTA,TE
90 TT=TT+TE:NEXT:PRINTTT/A:END
This one gives me 212, even slower than decimal 0.
It looks like, on Color BASIC at least, the VAL(“”) trick is not useful, but I appreciate Carlos letting me know about it.
Have you seen this on any other flavor of BASIC? Let me know in the comments.
In a previous article, I wrote a BASIC program that simulated pulling marbles out of a bag. I described my thought process, including how I initially thought I would have to randomize the virtual marbles in the virtual bag. I realized this would be unnecessary, but still offered a demonstration of a simple way to randomly shuffle an array of items, as one might do with a deck of playing cards:
NOTE: I had a bug on line 40 and was only counting from 0 to 24 (25 letters) instead of 0 to 25 (26 letters of the alphabet). Fixed here:
10 REM shuffle.bas
20 REM CREATE ALPHABET ARRAY
30 DIM A$(25)
40 FOR A=0 TO 25
50 A$(A)=CHR$(65+A)
60 NEXT
70 REM DISPLAY ARRAY
80 GOSUB 190
90 REM SWAP EACH ONE RANDOMLY
100 FOR A=0 TO 25
110 S=RND(26)-1
120 SV$=A$(S)
130 A$(S)=A$(A)
140 A$(A)=SV$
150 NEXT
160 REM DISPLAY ARRAY
170 GOSUB 200
180 END
190 REM DISPLAY ARRAY
200 FOR A=0 TO 25
210 PRINT A$(A);
220 NEXT
230 PRINT
240 RETURN
That would display the 26 letters of the alphabet, then shuffle them and display the results. My shuffle routine went through each position (0 to 25) and swapped it with another random position (0 to 25).
However, adding to the flaw in the simulation that article was about, there was another flaw in my shuffling examples.
In a comment, James Jones added:
Actually, to get a random shuffle with all permutations equally likely, you have to do something like this:
FOR i:= 1 to n-1 j:=i+INT(RND(n+1-i)) temp:=a(i)\a(i):=a(j)\a(j):=temp NEXT i
i.e. at each step you swap a(i) with a(j) where j is a randomly chosen number between i and n inclusive.
James Jones
His program logic uses ‘n’ as the number of elements we are shuffling, which is 26 for my example.
The for/next loop of ‘i’ will count from 1 to n-1, so 1 to 25 in this example.
‘j’ will be the randomly selected target element to swap with the element at ‘i’. It is chosen using the random number generator. I it looks like his rnd(26) would return 0-25, so the result of j for each count of 1 to n-1 would be
It then uses a temporary variable to swap the position of a(i) with a(j).
My original version randomly swapped each position with any of the 26 positions. James’ code swaps each position with only positions after it.
With apologies to James for down-porting his logic to Microsoft BASIC, here is my original example updated to take this approach. To keep it as close to my original example as possible, I’ll adjust my array to use 1-26 (instead of 0-25). Color BASIC arrays are base-0, but for this example we’ll just ignore the zero. I’ll try to bold the changes from the original.
10 REM jjshuffle.bas
20 REM CREATE ALPHABET ARRAY
25 N=26
30 DIM A$(N)
40 FOR A=1 TO N
50 A$(A)=CHR$(64+A)
60 NEXT
70 REM DISPLAY ARRAY
80 GOSUB 190
90 REM SWAP EACH ONE RANDOMLY
100 FOR I=1 TO N-1
110 J=I+INT(RND(N+1-I)-1)
120 TEMP$=A$(I)
130 A$(I)=A$(J)
140 A$(J)=TEMP$
150 NEXT
160 REM DISPLAY ARRAY
170 GOSUB 200
180 END
190 REM DISPLAY ARRAY
200 FOR A=1 TO N
210 PRINT A$(A);
220 NEXT
230 PRINT
240 RETURN
And to convert this back to my first example using base-0 arrays:
10 REM shuffle2.bas
20 REM CREATE ALPHABET ARRAY
30 DIM A$(25)
40 FOR A=0 TO 24
50 A$(A)=CHR$(65+A)
60 NEXT
70 REM DISPLAY ARRAY
80 GOSUB 190
90 REM SWAP EACH ONE RANDOMLY
100 FOR A=0 TO 25
110 S=A+RND(26-A)-1
115 PRINT A,S
120 SV$=A$(S)
130 A$(S)=A$(A)
140 A$(A)=SV$
150 NEXT
160 REM DISPLAY ARRAY
170 GOSUB 200
180 END
190 REM DISPLAY ARRAY
200 FOR A=0 TO 25
210 PRINT A$(A);
220 NEXT
230 PRINT
240 RETURN
Today I will present Art Flexser‘s solution to this marble puzzle, as well as a corrected version of mine.
First I will correct my version of the “pulling marbles out of a bag” puzzle recently presented by Steve Ostrom. I now understand the rules to be:
You have a bag full of the following marbles: 5 red, 4 blue, 3 white, and 3 black.
You have four marble trays, one for each color.
You begin by pulling a marble out of the bag and placing it in the appropriate tray.
Repeat until one of the trays has three of the marbles for that color.
Track which color made it to three first.
Do this 100,000 times (for our statistics).
At the end, there should be some number of times each color of marbles was completed before any other color, in that turn.
Losing my marbles
I rewrote my visual simulator to represent the bag of marbles (the top line of groups of four color blocks) and each tray (four more lines, one for each color).
As my simulation runs, marbles will be taken from the top row (the bag) and placed in the appropriate tray.
When a tray is full (it has three of the same color marble), the round stops, and the total “completed” count for that color is incremented.
Repeat for 100,000 iterations. The current iteration count is displayed in the top right corner of the screen.
During this process, the statistics for each tray are displayed. It looks like this:
Marble bag simulator, version 2.
Here is my commented and non-optimized Color BASIC program:
10 ' marble2.bas
20 '
30 ' INITIALIZE STATS
40 '
50 RT=0:BT=0:WT=0:KT=0
60 CLS
70 PRINT "MARBLE BAG:"
80 '
90 ' DO THIS 100,000 TIMES
100 '
110 FOR TC=1 TO 10000
120 PRINT@25,TC
130 '
140 ' DISPLAY MARBLES
150 ' 5 RED=191, 4 BLUE=175, 3 WHITE=207, 3 BLACK=128
160 '
170 PRINT@32,STRING$(5,191);STRING$(4,175);STRING$(3,207);STRING$(3,128)
180 '
190 ' RESET MARBLE TRAYS
200 '
210 RL=1132:BL=RL+32:WL=RL+64:KL=RL+96
220 PRINT @96, "RED TRAY :"
230 PRINT "BLUE TRAY :"
240 PRINT "WHITE TRAY:"
250 PRINT "BLACK TRAY:"
260 '
270 ' RESET MARBLE COUNTS
280 '
290 RC=0:BC=0:WC=0:KC=0
300 '
310 ' GRAB MARBLES
320 '
330 MC=0
340 '
350 ' RANDOM MARBLE LOCATTION
360 '
370 ML=1024+32+RND(15)-1
380 '
390 ' GRAB MARBLE
400 '
410 V=PEEK(ML)
420 '
430 ' IF MARBLE USED, TRY AGAIN
440 '
450 IF V=0 THEN 370
460 '
470 ' MARK MARBLE REMOVED
480 '
490 POKE ML,0
500 '
510 ' PUT MARBLE IN TRAY
520 '
530 IF V=191 THEN POKE RL+RC,V:RC=RC+1:GOTO 600
540 IF V=175 THEN POKE BL+BC,V:BC=BC+1:GOTO 600
550 IF V=207 THEN POKE WL+WC,V:WC=WC+1:GOTO 600
560 IF V=128 THEN POKE KL+KC,V:KC=KC+1:GOTO 600
570 '
580 ' CHECK FOR 3 IN A TRAY
590 '
600 IF RC=3 THEN RT=RT+1:GOTO 680
610 IF BC=3 THEN BT=BT+1:GOTO 680
620 IF WC=3 THEN WT=WT+1:GOTO 680
630 IF KC=3 THEN KT=KT+1:GOTO 680
640 '
650 ' NOT FULL YET, CONTINUE GRABBING MARBLES
660 '
670 MC=MC+1:IF MC<15 THEN 370
680 '
690 ' PRINT COUNT AND PERCENTAGE
700 '
710 PRINT@256,"RED :";RT,RT/TC
720 PRINT "BLUE :";BT,BT/TC
730 PRINT "WHITE:";WT,WT/TC
740 PRINT "BLACK:";KT,KT/TC
750 '
760 ' REPEAT
770 '
780 NEXT
790 '
800 ' REPORT RESULTS
810 '
820 PRINT "TIME:";TIMER/60
830 END
840 '
850 ' VARIABLES
860 '
870 ' TC = TOTAL COUNT (RUNS)
880 '
890 ' RL/BL/WL/KL = DEST. TRAY LOCATIONS
900 '
910 ' TOTAL TIMES EACH TRAY FILLED:
920 ' RT = RED TOTAL
930 ' BT = BLUE TOTAL
940 ' WT = WHITE TOTAL
950 ' KT = BLACK TOTAL
960 '
970 ' RC/BC/WC/KC = CURRENT TRAY COUNT
980 '
990 ' MC = MARBLES PULLED FROM BAG
1000 '
1010 ' ML = MARBLE LOCATION (PEEK)
1020 '
1030 ' V = VALUE OF MARBLE PEEKED
It’s going to take a long time for the CoCo to do 100,000 iterations, but luckily I heard from a guy who did it a faster way…
Art Flexser
ADOS creator Art Flexser wrote in with his take on this puzzle. (And I tried really hard not to fan-boy over getting an e-mail from him. His RS-DOS replacement is legendary.)
Hi, Al. I found Steve Ostrom’s marbles problem of interest, and thought it would make an interesting programming exercise for myself. (I haven’t written a program in ages.)
I have described my understanding of the problem in the program’s initial comments. I hope it corresponds to Steve’s intent and to your (revised) interpretation.
I wrote the program under QBASIC-64 so that numerical results would be obtainable much faster. (Downloadable for free from www.qb64.net). I had to change two lines (lines 92 and 140) for CoCo compatibility since the RND function is defined differently on the two platforms. See the comments for the necessary changes. The listing I’ve attached is the QBASIC version. The output is most readable in 80-column mode.
I did not obtain the same probabilities as Steve did. I got .514, .281, .102, and .102 (based on a million trials) for red, blue, white, and black. I have no idea why there is a discrepancy. Perhaps you or Steve (whose email address I don’t have) could send me a copy of his program so I could investigate. Or, maybe your own revised program will be ready soon, so we can see if your results agree with me, with Steve, or with neither.
The speed difference between the two platforms is pretty amazing. The program runs about 200,000 times faster under QBASIC-64 on my 3.4 GHz Windows 10 (64-bit) PC than under CoCo Basic. So, I set NP, (in line 95) the number of trials between results printouts, for a million under QBASIC and five for the CoCo (simulated by the Mocha java emulator) and got results about every 2 seconds either way.
Best, Art
Fantastic! Let’s take a look at what he submitted:
10 'A BAG CONTAINS 15 MARBLES, CONSISTING OF 5 RED, 4 BLUE, 3 WHITE AND 3 BLACK
20 'A TRIAL IS DEFINED AS DRAWING ONE MARBLE AT A TIME OUT OF THE BAG, UNTIL
30 'THREE MARBLES OF THE SAME COLOR HAVE BEEN DRAWN, NOT NECESSARILY IN A ROW.
40 'DRAWING IS DONE WITHOUT REPLACEMENT.
50 'THE PROGRAM REPRESENTS THE 4 COLORS BY THE DIGITS 1-4.
60 'WE WISH TO FIND THE PROBABILITIES THAT EACH OF THE 4 COLORS "WINS" A TRIAL BY
70 'SIMULATION OF A LARGE NUMBER OF TRIALS.
75 'THE MARBLES REMAINING IN THE BAG ARE REPRESENTED BY A STRING VARIABLE
80 M0$ = "111112222333444" 'INITIAL STATE OF THE BAG, WITH 15 MARBLES
90 CT(1) = 0: CT(2) = 0: CT(3) = 0: CT(4) = 0 'INITIALIZE WIN COUNTS FOR THE 4 COLORS
92 RANDOMIZE TIMER 'SEED RANDOM NUMBER GENERATOR USING TIMER VALUE
93 'FOR COCO, CHANGE ABOVE LINE TO X=RND(-TIMER) *
95 NP = 1000000
100 FOR I = 1 TO NP 'PRINT RESULTS AFTER A NUMBER NP OF TRIALS HAS OCCURRED
110 'INITIALIZE COUNTS OF HOW MANY MARBLES OF EACH COLOR HAVE BEEN DRAWN THIS TRIAL
120 R(1) = 0: R(2) = 0: R(3) = 0: R(4) = 0
130 MB$ = M0$: NM = LEN(MB$) 'NM = NUMBER OF MARBLES REMAINING IN BAG
135 'GRAB A RANDOM MARBLE FROM THE BAG
140 P = INT(RND * NM) + 1
145 'FOR COCO, CHANGE ABOVE LINE TO P=RND(NM) *
150 'P IS THE RANDOM POSITION NUMBER SELECTED WITHIN THE BAG CONTENTS STRING
160 CL$ = MID$(MB$, P, 1) 'CL$, THE COLOR OF THE SELECTED MARBLE, IS "1", "2", "3", OR "4"
170 C = VAL(CL$) 'CONVERT TO AN INTEGER FROM 1-4
180 R(C) = R(C) + 1 'R(C) IS HOW MANY MARBLES OF THIS COLOR HAVE BEEN DRAWN SO FAR
190 'IF WE HAVE 3 MARBLES DRAWN OF THIS COLOR, INCREMENT WINS COUNTER FOR THIS COLOR
200 'AND BEGIN A NEW TRIAL
210 IF R(C) = 3 THEN CT(C) = CT(C) + 1: GOTO 260
220 'ADJUST BAG'S CONTENT TO REFLECT THE CHOSEN MARBLE'S REMOVAL
230 MB$ = LEFT$(MB$, P - 1) + RIGHT$(MB$, NM - P)
240 NM = NM - 1
250 GOTO 140 'CONTINUE TRIAL, DRAW ANOTHER MARBLE RANDOMLY
260 NEXT I
270 'CALCULATE PROBABILITIES AND PRINT RESULTS SO FAR
280 TT = CT(1) + CT(2) + CT(3) + CT(4) 'TOTAL NUMBER OF TRIALS SO FAR
290 PR(1) = CT(1) / TT: PR(2) = CT(2) / TT: PR(3) = CT(3) / TT: PR(4) = CT(4) / TT
295 PRINT " RED BLUE WHITE BLACK TOTAL TRIALS"
300 PRINT CT(1); CT(2); CT(3); CT(4); " "; TT; " FREQUENCIES"
310 PRINT PR(1); PR(2); PR(3); PR(4); " PROBABILITIES": PRINT
320 GOTO 100
His approach uses a string containing characters representing each of the four marble types. I copied it in QB64 to try it out. I was immediately impressed that, even though it looks like an old-school DOS text program, it allowed me to resize the window so I could see the entire program at once:
QB64 with Art Flexser’s marble puzzle code.
With a press of F5, the program is compiled into an executable, and then ran:
Art Flexser’s marble puzzle code in operation.
It was blasting through a million iterations every few seconds, and was instantly showing results: Red at 51%, blue at 28%, white at 10% and black at 10%.
While this was running, I decided to see if it would run in PC-BASIC as well:
Art Flexser’s marble program running under PC-BASIC.
I let it run for awhile, but it didn’t print anything. It seems PC-BASIC is much slower than QB64, which is likely because QB64 is some kind of compiler that turns the BASIC into an executable. When I worked for Radio Shack (1988-1991 or so), I remember benchmarking a CoCo 3 BASIC against some Tandy 1000 BASICs and the CoCo was faster than everything but the 286 in turbo mode. Maybe that is the type of machine PC-BASIC is trying to simulate ;-)
And, of course, since his code supports it, I wanted to see it running on a (virtual) CoCo. I made the three changes his comments suggest (for how RND works, and reducing the number of iterations to 5 per cycle instead of a million):
Art Flexser’s marble simulation code on a virtual CoCo.
Per his note, the CoCo version is updated every 5 times through, while the QB64 version is doing a million.
After a bit, we see the pattern develop:
Art Flexser’s marble simulator has produced results.
Red is at 51%, blue at 26%, white at 11% and black at 10%. Even with far fewer iterations (5 versus a million each time through), it is already very close to the QB64 version that reported red at 51%, blue 28%, white 10% and black 10%.
Meanwhile, an hour later, my CoCo version completed 100,000 iterations:
Marble bag simulator, version 2 after 100000 iterations.
My final results were red at 50%, blue at 29%, white at 10% and black 10%. This is very close to Art’s 51%/28%/10%/10% results, but it does not match the results from Steve’s simulation:
I ran 100,000 iterations (took most of the night) and here are the rounded percentages I found. Red = 42.5%, blue = 27.5%, white and black are both 15.0%.
Steve Ostrom
Is this just a difference in the patterns of the psuedo random number generator? I’ll share my results on Facebook and see what Steve says.
NOTE: The time value displayed at the end is meaningless. I forgot to take into consideration that the TIMER value rolls over at 65535 (16-bits). At a tick every 60th of a second (on an American NTSC CoCo using the 60Hz screen interrupt), that’s about 18 minutes. This took well longer than that, so it rolled over several times. I’ll have to add a bit more code so it can properly estimate the total time taken.
If you want to play with BASIC on a modern computer, here are two options I have found.
PC-BASIC
PC-BASIC from http://robhagemans.github.io/pcbasic/
PC-BASIC is an implementation of the old GW-BASIC that came with MS-DOS. It allows you to enter commands directly (PRINT “HELLO WORLD”) just like the old days, and also write full programs with line numbers. You can load and save them just like you’d expect. This one should be familiar to those who have used Microsoft BASIC on other systems.
I found PC-BASIC awhile ago when I was working on my SirSound project. I was trying to find out how Microsoft supported multi-voice music on their BASICs that supported it. I have since used it for various quick-and-dirty experiments, even in my day job (most recently, to draw out a user interface for an embedded device I am working on).
QB64
QB64 from https://www.qb64.org/portal/
Special thanks to Art Flexser for letting me know about this one.
This is an implementation of QuickBasic from the MS-DOS days. It allows writing a more modern version of BASIC, and compiling it down to an executable.
