In my 3X+1 post, I needed to check if a value was odd or even. I did so by using “AND 1” which would test the least significant bit. This works, and is fast, but is limited to values 32767 or lower (15 bits).

Comments from William Astle, RogelioP and John offered corrections and updates to my code. I decided to benchmark a few different methods for detecting if a value was odd or even, and here is what I came up with.

0 REM 3x+1 Benchmarking

5 'GOTO 300

100 ' 0-32767 ONLY
110 TIMER=0
120 FOR A=1 TO 1000
130 IF X AND 1 THEN REM
140 NEXT:PRINT TIMER

200 ' ALL RANGES?
210 TIMER=0
220 FOR A=1 TO 1000
230 IF INT(X/2)=X/2 THEN REM
240 NEXT:PRINT TIMER

300 ' ROGELIO P
310 TIMER=0
320 FOR A=1 TO 1000
330 IF INT(X/2)*2=X THEN REM
340 NEXT:PRINT TIMER

400 ' WILLIAM ASTLE
405 T=0:H=0.5
410 TIMER=0
420 FOR A=1 TO 1000
430 T=X*H:IF T=INT(T) THEN REM
440 NEXT:PRINT TIMER

500 ' DIVIDE TEST
505 T=0:H=2
510 TIMER=0
520 FOR A=1 TO 1000
530 T=X/H:IF T=INT(T) THEN REM
540 NEXT:PRINT TIMER

When I run this program in Xroar on my Raspberry Pi 400, I get:

313
508
506
485
485

As expected, AND is the fastest, so use this if you know your values will be 32767 or lower.

Using INT(X/2)=X/2 was a fraction slower as INT(X/2)*2=X, which I guess makes sense since both do an INT and two math functions.

William’s suggestion of multiplying by .5 instead of dividing by two rang a bell. I believe he (or someone) pointed this out to me a few years ago when I was doing similar benchmarks. A big speed up comes just from putting the value in a variable, but I was surprised to see that dividing by a variable of 2 was the same speed as multiplying by a variable of .5.

What ideas do you have? Anything with math (“/2”) can be sped up by using a variable (“/H”), so there are some improvements just from that. Using HEX values (“&H2”) instead of decimal is also faster, as is removing extra spaces.

But are there better approaches we can use?

Thoughts appreciated.

For the past three weeks, I have found myself out-of-town for work. This week, I decided to bring my Raspberry Pi 400 along so I could play with it in the hotel room.

I soon found myself toying around with the XRoar CoCo emulator, and I knew just what I wanted to program…

Last night, YouTube showed me a video about “the most dangerous problem in mathematics.”

The idea is you start with a number. If it is odd, you multiply it by 3 and add 1. If it is even, you divide it by 2. Repeat until you get to the pattern 4, 2, 1, 4, 2, 1, 4, 2, 1.

Math says that, so far, every number ends up at that pattern. No one has figured out a formula that leads to any number that does not end at 4, 2, 1.

With that in mind, I thought it would be fun to write the 3X+1 problem in CoCo Color BASIC. It looks like this:

0 REM 3X+1
10 PRINT:INPUT "STARTING NUMBER";X
20 PRINT X;
30 IF X=1 THEN 10
40 IF X AND 1 THEN X=X*3+1:GOTO 20
50 X=X/2:GOTO 20 

I tried to avoid using any Extended Color BASIC features such as HEX numbers (&H1) to speed things up. I even skipped ELSE so it could run on a VIC-20 or other system without that command.

I use “X AND 1” to test for a number being odd. Any odd number has the first bit set. 1 (00000001) does, 2 does not (00000010), 3 does (00000011), and so on.

It does have one flaw… if any number is greater than 32767, it will crash with a ?FC ERROR. Apparently Color BASIC’s AND cannot handle any value greater than 7 bits (01111111 = 32767).

Do you know of a different way to test for even or odd values? I can think of two, one of which would be terribly inefficient and the other not as inefficient but much worse than using AND.

Give it a shot and see if you can find the largest sequence of numbers a CoCo can calculatae.

Or better yet, find a better way to do this in Color BASIC.

Enjoy!

See also: part 1, part 2, part 3, part 4, part 5, part 6, part 7 and more (coming “soon”).

NOTE: This one is gonna jump around a bit, referring to examples in the previous installment, so hang tight…

Some comments from the previous installment, where I shared some code that wasn’t speeding up like I thought it should when I replaced hard-coded values with variables. As the post when live, I read through it and noticed my mistake. I added a comment to see if anyone else could spot it:

0 REM arrowbench9.bas
5 V=&HF7:U=&H155:D=&H156:L=&H157:R=&H158
10 TIMER=0:FOR A=1 TO 1000
20 POKEU,V:POKED,V:POKEL,V:POKER,V
30 IF PEEK(U)=V THEN IF Y>.THEN Y=Y-1:GOTO90
40 IF PEEK(D)=V THEN IF Y<&HDF THEN Y=Y+1:GOTO90
50 IF PEEK(L)=V THEN IF X>.THEN X=X-1:GOTO90
60 IF PEEK(R)=V THEN IF X<&HFE THEN X=X+1:GOTO90
90 NEXT:PRINT TIMER

craig immediately chimed in with the issue:

In arrowbench9.bas it pokes $F7 instead of $FF ?

In test, shouldn’t line 10 should use same as arrowbench9.bas line 20 ?

Can you use ‘next’ instead of ‘goto90’ ?

– craig

Right off the bat, craig noticed my mistake. In like 20, it’s supposed to POKE those four keyboard column values to 255 (&HFF). But, when I substituted the variables, I did not make a variable for 255 — instead, I incorrectly used the V variable which was the &HF7 value the PEEK would change to when that key was being held down. Oops! Thus, I was never resetting it so it was, apparently, always acting as if the key was being held down, processing all the variable X/Y stuff every time.

A fix to the original arrowbench2.bas might look like this:

0 REM arrowbench10.bas
5 Z=&HFF:V=&HF7:U=&H155:D=&H156:L=&H157:R=&H158
10 TIMER=0:FOR A=1 TO 1000
20 POKEU,Z:POKED,Z:POKEL,Z:POKER,Z
30 IF PEEK(U)=V THEN IF Y>.THEN Y=Y-1
40 IF PEEK(D)=V THEN IF Y<&HDF THEN Y=Y+1
50 IF PEEK(L)=V THEN IF X>.THEN X=X-1
60 IF PEEK(R)=V THEN IF X<&HFE THEN X=X+1
90 NEXT:PRINT TIMER

Now the keyboard table is properly reset back to 255 before each scan. While the original arrowbench2.bas reported 2890, this version (using the properly variable to reset those locations) reports 2351 and is indeed faster. My bad.

As to the other comments, that was yet another typo, where I created variables then forgot to use them:

5 V=&HF7:U=&H155:D=&H156:L=&H157:R=&H158
10 POKE&H155,&HFF:POKE&H156,&HFF:POKE&H157,&HFF:POKE&H158,&HFF
20 PRINT HEX$(PEEK(U))" "HEX$(PEEK(D))" "HEX$(PEEK(L))" "HEX$(PEEK(R)),HEX$(PEEK(&H155))" "HEX$(PEEK(&H156))" "HEX$(PEEK(&H157))" "HEX$(PEEK(&H158))
30 GOTO 10

…should have used U/D/L/R and a new Z in line 10, just like the example before.

As to using “NEXT” instead of “GOTO 90”, this refers to trying to bypass additional checks if one key is satisfied:

0 REM arrowbench11.bas
5 Z=&HFF:V=&HF7:U=&H155:D=&H156:L=&H157:R=&H158
10 TIMER=0:FOR A=1 TO 1000
20 POKEU,Z:POKED,Z:POKEL,Z:POKER,Z
30 IF PEEK(U)=V THEN IF Y>.THEN Y=Y-1:GOTO90
40 IF PEEK(D)=V THEN IF Y<&HDF THEN Y=Y+1:GOTO90
50 IF PEEK(L)=V THEN IF X>.THEN X=X-1:GOTO90
60 IF PEEK(R)=V THEN IF X<&HFE THEN X=X+1:GOTO90
90 NEXT:PRINT TIMER

In this benchmark example, I did GOTO 90 to go to the “end of what we are timing” line. But if this was being used in a program, a NEXT would have been faster than scanning forward to find line 90 and then doing the NEXT. BUT, if I tried that here, when NEXT was done (1 to 1000), it would not return and would go to the next line — and if that was 40, 50 or 60, it would do the check then try a NEXT and error with a “?NF ERROR” (next without for).

But, the point is well made — NEXT with a check after it could even be faster than a GOTO (scanning lines) to a next. That would be a fun benchmark.

Faster, even.

craig also pointed out an interesting optimization… Rather than clear all four keyboard values, whether they need it or not, why not just clear the one(s) that changed?

Faster.. what about moving line 20 out of the loop and only poking the matching peeks?

IF PEEK(U)=V THEN POKEU,F:IF Y>.THEN Y=Y-1:GOTO90

F=&HFF

For diagonals, change to GOTO50 on line 30.
Line 60 needs no GOTO90

– craig

This is worthy of an updated benchmark. Let’s take arrowbench10.bas above (2351) and modify it like this:

0 REM arrowbench12.bas
5 Z=&HFF:V=&HF7:U=&H155:D=&H156:L=&H157:R=&H158
10 TIMER=0:FOR A=1 TO 1000
30 IF PEEK(U)=V THENPOKEU,Z:IF Y>.THEN Y=Y-1
40 IF PEEK(D)=V THENPOKED,Z:IF Y<&HDF THEN Y=Y+1
50 IF PEEK(L)=V THENPOKEL,Z:IF X>.THEN X=X-1
60 IF PEEK(R)=V THENPOKER,Z:IF X<&HFE THEN X=X+1
90 NEXT:PRINT TIMER

Now it only clears the value if it was changed. This produces a value of … 1603! We have a winner! Great improvement, craig!

Also, when I added the “GOTO 90” at the end of the example, to bypass the other checks (eliminating the possibility of diagonals), craig is suggesting the code could simply skip checking DOWN if we had an UP (GOTO 50 moves to the Left/Right check next) and, likewise, like 50 could GOTO 90 to skip over the Right check. Thus:

• If UP is pressed…
  • Check for LEFT. If LEFT is pressed…
    • Exit checks. We have an UP and a LEFT
  • else Check for RIGHT. If RIGHT is pressed…
    • Exit checks. We have an UP and RIGHT.
  • else Exit checks. We have UP.
• else check DOWN. If DOWN is pressed…
  • Check for LEFT. If LEFT is pressed…
    • Exit checks. We have DOWN and LEFT
  • else Check for RIGHT. If RIGHT is pressed…
    • Exit checks. We have DOWN and RIGHT.
  • else Exit checks. We have DOWN.

When I write it out that way, you can see that this type of logic (adding GOTO to skip steps) means that the program would be fastest checking for UP and LEFT. And slowest for checking for JUST down. This means a game would move at different speeds based on which direction is detected. While this is a great optimization, it may not be desirable since a game may wish consistent speed (i.e. always worst case) than having a speed that varies.

Big thanks to craig for spotting my typo, and providing these two additional optimizations. I really like the “only POKE if it changed” one. It would be fun to benchmark and see if “worst case” all four arrows were being held down, is this slower than just clearing them all at once.

IF ELSE SLOWER

One additional note about using IF… Once BASIC starts processing a line, it has to parse the entire line whether that code is executed or not. For example:

IF A=42 THEN DO THIS:DO THAT:DO THE OTHER:DO NOTHING:DO OVER

Even if A is not 42, BASIC still has to at least scan through all the tokens and such on the rest of the line to skip it. Also, since ELSE could be used on Extended Color BASIC, there could be an ELSE clause that still needs to be processed:

10 IF A=42 THEN DO THIS:DO THAT:DO THE OTHER:DO NOTHING:DO OVER ELSE ...

Because of this, IF/ELSE can actually be slower than doing something like:

10 IF A=42 THEN 30
20 DO OVER:GOTO 40
30 DO THIS:DO THAT:DO THE OTHER:DO NOTHING:GOTO 40
40 ...continue... 

This looks quite awful, but that’s how I had to program on my Commodore VIC-20 because it had no ELSE. And, it turns out, this can be quite a bit faster! Now line 10 checks for A to be 42, and if it is, it skips a line (which is fast) to get to 30 and hande it. If it is NOT 42, it quickly skips two lines instead to having to parse through a whole line of BASIC tokens.

I benchmarked something like this in an earlier article series, and was very impressed at the speedups that can be achieved just by making any IF line use a GOTO… though if it’s likely the line is true (A=42) more often than it’s not, it might not make sense. One size does not fit all.

And with that, I’ll end today’s installment without providing anything new, other than some handy speedups craig showed us.

We now have some quick ideas on using arrow keys to change X and Y coordinates. X and Y coordinates are used in games like Atari Adventure and Pac-Man to know which direction to send an enemy at the player. In the case of Pac-Man (see my earlier article series on that one), the ghosts target spots around (or on top of ) Pac-Man and decide which direction to turn based on which choice would be closer (using the wonderful Pythagorean theorem we learned about in school).

BUT, if our program was not using that, and just wanted a screen location to POKE a player character to, we could probably simplify this keyboard code a bit and use less variables.

To be continued…