A First Kenbak/Collatz Tutorial

[Anthony Kapolka]

I just used a Kenbak to introduce first year students to problem solving. 

To do this we wrote some simple code to generate a hailstone sequence. 

See https://www.geeksforgeeks.org/hailstone-numbers/

As long as you start with 26 or less you won't overflow 8 bits.

I'm sure this is obvious to most people here, but consider it a tutorial for people who haven't coded before.

Programming can be top down.

Here, top down means I can decompose the problem.

A good model of computing is IPO - Input / Processing / Output

Here I = get the initial number from the user
         O means show the current number

And for processing we need to
   Decide if the number is even or odd
   If odd, multiply by 3 and add 1
   If even, divide by 2

So: FIVE subtasks. (Six if you count looping to generate successive numbers).

Need input and output to test the others, so do them first.

Start all programs with first four registers set

000 Register A

000 Register B

000 Register X

004 Program Counter

Input described on p EX 11-4ff
Numbers entered by switches appear in location 377
So, halt program, let the user enter a value, then copy it from 377.

024 Load A from 376 (copies a zero into A)
376
034 Store A into 377 (copies that zero into 377)
377
000 Halt (now, get input)

Probably better to Load an immediate 0 rather that assume 376 is a zero.

Output – let’s output 377, via A register

024 Load A from 377 (copies input into A)
377
034 Store A into 200 (copies that input into 200)
200

000 Halt

Now stop and test. 

Great! Now let’s do some processing.
We can divide by 2 by shifting right.

011 Shift A right one place

So the whole program becomes…

000

000

000

004

024 Load A from 376 (copies a zero into A)
376
034 Store A into 377 (copies that zero into 377)
377
000 Halt (now, get input)
024 Load A from 377 (copies input into A)
377
011 Shift A Right one place (divides by 2)
034 Store A into 200 (copies that input into 200)
200
000 Halt

Again, stop and try it.

You can loop by changing the last halt (@16 octal) to

344 Unconditional Jump
013

Try entering 200 (the leftmost light only.)
You’ll need to hit stop to have it terminate.

Three tasks done!

We could shift left and then add A+1, but instead let’s just do 3A+1
Can’t operate only on one register, so let’s use B also.

034 Store A into B (B = 001)
001
004 Add B to A
001
004 Add B to A
001
003 Add 1 to A
001

Now A has 3A+1 (!!)
Put this new code in place of the Shift instruction:

000

000

000

004

024 Load A from 376 (copies a zero into A)
376
034 Store A into 377 (copies that zero into 377)
377
000 Halt (now, get input)
024 Load A from 377 (copies input into A)
377
034 Store A into B (B = 001)
001
004 Add B to A
001
004 Add B to A
001
003 Add 1 to A
001
034 Store A into 200 (copies that input into 200)
200
000 HALT
344 Unconditional Jump
013

By placing the jump after the halt execution will pause until you hit the start button.

Four Tasks Done!

Now, we need some code to decide which instruction block to do, based on whether the number is even or odd

Our number is in A register…
It’s odd if the rightmost (lowest) bit is 1

We can detect this by using the AND operation. And takes two operands and keeps only those bits that are set in both operands.

So ?? ??? ??1 AND 00 000 001 is 00 000 001
      ?? ??? ??0 AND 00 000 001 is 00 000 000

We’ll use another register, X
AND puts its results in the A register, so we will lose our number – be careful if looping!

We can save A in X

034 Store A into X (X = 002)
002
323 And A with Constant 1
001

Now A has either 0 (even) or 1 (odd)
We can Jump based on =0 to the code to shift – see page EX 10-3ff

044 Jump if A is 0 to ???
???   This is whatever address is appropriate

Otherwise continue (do 3A+1)

Complete Program
Now, let's assemble all the parts.  The first number is the memory location, the second its contents.

000 000 Register A

001 000 Register B

002 000 Register X

003 004 Program Counter

# get input
004 024 Load A from 376 (copies a zero into A)
005 376
006 034 Store A into 377 (copies that zero into 377)
007 377
010 000 Halt (now, get input)
011 024 Load A from 377 (copies input into A)
012 377

# check if even or odd
013 034 Store A into X (X = 002)
014 002
015 323 And A with Constant 1
016 001
017 044 Jump if A is 0 to
020 035 address of even code
021 024 Load A from X (restore A)
022 002

# if odd, code to compute 3A+1
023 034 Store A into B (B = 001)
024 001
025 004 Add B to A
026 001
027 004 Add B to A
030 001
031 003 Add 1 to A
032 001

# new code to jump over even case
033 344 Unconditional Jump to
034 040 address of output code

# if even, code to compute A/2
035 024 Load A from X (restore A)
036 002
037 011 Shift A Right one place (divides by 2)

# output code
040 034 Store A into 200 (for display)
041 200

# code to jump back to start and repeat
042 000 Halt (allows for single step – replace with 200 NOOP to skip)
043 344 Unconditional Jump
044 013

Of course, this code isn't being particularly clever with register use; I'm sure you can improve it.

[Tom Lake]

Have you tried 28 as an initial number? That seems to work.

[Kapolka, Anthony]

Yes you can start with 28-30, 32-38, and a lot of other numbers that won't go above 255, but as 27 is the first one that does - any number 26 or less is definitely safe.

--
You received this message because you are subscribed to a topic in the Google Groups "uKenbak-1" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/ukenbak-1/gvlHrcR8940/unsubscribe.
To unsubscribe from this group and all its topics, send an email to ukenbak-1+...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/ukenbak-1/c5f25569-3b1d-4fc4-ac97-c59cb7f791d4n%40googlegroups.com.