Permutations on a
TI-58 Programmable Calculator

TI-58 Programmable Calculator and PC-100 Thermal Printer

Introduction

Download, Set Up, and Run the Program

Memory Registers

Program Listing

Introduction

In 1977 or 1978, I wrote a program for the Texas Instruments TI-58 calculator and PC-100 printer that generated all the permutations of a string up to 10 characters in length. For example, given the string, "ABCDEF", the program would generate all 720 permutations of the string, beginning with "ABCDEF" and ending with the string reversed:

ABCDEF
ABCDFE
ABCEDF
ABCEFD
  .
  .
  .
FEDCBA

      720

A unique aspect of the program—a calculator program, mind you—was that it implemented a recursive permutation algorithm, complete with a call stack of memory registers to hold the local variables of the deeply nested function calls.

I thought of writing an article about the program and submitting it to Byte magazine. At the time, Byte published articles on diverse hardware and software computing subjects, both low-level and high-level, so an article on a recursive calculator program would not have been out of the question. I'm pretty sure I wrote the beginnings of an article and I remember typing up one page at work after hours on our IBM Selectric typewriter (yes!). On the other hand, my memory could be playing tricks on me.

In the early 2000s, I created a web page for the original program, laboriously typing in the code listing from an old PC-100 roll of printer paper. In April 2016, I came across Pierre Houbert's TI58C EMULATOR for Windows (and Linux under Wine) and wondered if I could get my program working in it. The first time I ran the TI58C EMULATOR, I was stunned. The emulator is a beautiful work of art, both visually and in terms of the programming effort that has gone into it. You're presented with a seemingly full-size picture of the calculator, working buttons, printer output, and optional displays of the currently loaded program(s) and memory registers. (There are also sound effects, which I didn't notice right away because I usually work with my speakers off.)

Here's a picture of the emulator window (click the image to see it full-size). I ran my permutation program on my "TRY IT" example (see Setting Up and Running the Program), let it print out some permutations, stopped the program, and reloaded the program and memory registers. In other words, the image shows the program and memory registers prior to running the program, not in the actual in-progress state you would have seen when the program was stopped.

(Click to enlarge)

The TI58C EMULATOR doesn't simply emulate the TI-58C calculator, it also adds new capabilities: 990 program steps, 1000 memory registers, and a whole slew of new and useful 2nd Op operations. (And even more features, as I'm continually discovering!)

Getting back to my permutation program ... The only documentation I had for the program was that old PC-100 code listing. I had no information on how to set up the calculator before running the program. So I went to work and reverse-engineered the program, figuring out how it works and what the memory registers are used for. In the process, I was able to move/eliminate some replicated/redundant code. This freed up some program storage, allowing me to replace branches to absolute locations with branches to labels.

Background

An unrelated story, but interesting I hope! We used slide rules in high school, but when I began college in Fall 1974 as an astronomy major, I wanted/needed a scientific calculator. From studying various calculator history webpages, it appears that the common choice at the time (August or September 1974) was between the Hewlett-Packard HP-35 ($395) and the new Texas Instruments SR-50 ($170). Both would have seemed exorbitantly expensive, so I opted for the cheaper Sinclair Scientific, a tiny, odd, scientific calculator which displayed numbers in 5+2-digit scientific notation. The calculator was introduced in 1974 and its price must have dropped immediately from the original $140; I'm pretty sure I got mine for about $70, or at least less than $100. The Sinclair Scientific was not really practical, but I somehow managed to use it in my Physics Lab class; I dropped out of college a year later and the calculator went into a desk drawer. Now, here is what is interesting: Ken Shirrif's webpage, "Reversing Sinclair's amazing 1974 calculator hack - half the ROM of the HP-35", gives a fascinating account of how Sinclair's engineer, Nigel Searle, programmed the TI 320-step, 4-arithmetic-function calculator chip to compute scientific functions, more or often less accurately! The webpage also includes a web emulator for the calculator with a side-by-side display of the calculator and the 320-step program. When you click on a key, you can see the program run, with each step dynamically highlighted as it is executed.

I learned to program on a Texas Instruments SR-56 programmable calculator, with 100 program steps and 10 memory registers. More precisely, it was the first actual computer to which I had access and on which I could run programs. I was simultaneously gaining reading knowledge of BASIC, ALGOL 60, FORTRAN, and Intel's 8080 microprocessor architecture and assembly language—among other computing topics. (I learned ALGOL and FORTRAN from Daniel McCracken's slim books on those two languages; at some point, I also purchased and read his magnum opus, A Simplified Guide to Structured COBOL Programming.) In the late summer or early fall of 1977, a good friend of my brother's and mine, Bob Stone, took us to his office in the Sounding Rockets department at NASA's Goddard Space Flight Center, showed us a box of $200 militarized 8080 chips, and let me try out a BASIC program I had written on his Intel 8080 development system. (His group flew 8080-based experiments on high-altitude weather balloons, sounding rockets being out-of-fashion at the time despite the name of their department.) Bob saved my BASIC program on a paper tape, which I still have!

When the TI-58 came out in 1977, I "graduated" from the SR-56 to the TI-58's 240 program steps and 30 memory registers. In retrospect, I should have plunked down the extra money for a TI-59 with its ability to save and load programs to and from magnetic cards. The TI-58 would lose everything when you turned it off and reentering a lengthy program every time you turned the calculator on was not a fun task. Pierre Houbert had/has the later TI-58C which retained its program(s) and memory registers between calculator sessions.

Some time after purchasing the TI-58, I bought the PC-100 printer. I'm not sure exactly when I wrote the permutation program, in 1977 or 1978. I do know I used it in early 1978, generating the 720 permutations of "GYORGY" for my computer science teaching assistant (whom I had previously gotten to know when we took a physics class together in 1974) and the 720 permutations of "JEANNE" as a Mother's Day gift for my mom (it was the thought that counted, I hope!). This might lead me to believe that I wrote the program in 1978. However, I got an MEK6800D2 Evaluation Kit in December 1977 (see "Farmer Brown on a 6800") and I took a beginning computer science course in Spring 1978, so it seems as if the calculator would have taken a back seat to the 6800 microcomputer and to my FORTRAN class . Perhaps not, though.

The Algorithm

I reverse-engineered enough of the calculator program to figure out what registers to set in order to run the program, but not enough to figure out the exact permutation algorithm. My attempts to do the latter were why I appear overly concerned above on the question of whether I wrote the program in 1977 or in 1978. In the fall of 1977, I applied for readmission to the University of Maryland, I was accepted, and I signed up to take the beginning computer science course, CMSC 100, in Spring 1978. In January, before the course started, I bought the CMSC 100 textbook and the CMSC 420 textbook, my beloved Horowitz and Sahni's Fundamentals of Data Structures (forgive the missing possessive, but I've always referred to the book as if "Horowitz and Sahni" were a single entity).

Now, if I'd written the program in 1978, I might have used Horowitz's and Sahni's permutation algorithm found in Chapter 1 (in the book's SPARKS language):

    procedure PERM(A,k,n)
        if k = n then [print (A); return]
        B <- A
        for i <- k to n do
            call INTERCHANGE(A,k,i)
            call PERM(A,k + 1,n)
            A <- B
        end
    end PERM

(Here's a C program, perm.c, that implements H&S's algorithm.) I proceeded on this assumption when trying to reverse-engineer the program. You'll notice that I use variable names A, i, k, and N in the memory register descriptions and the code listing comments. In fact, the calculator program saves the local variables A, i, and k on the stack when making a recursive call, as it should. N's value is fixed on the very first call to PERM() in H&S's algorithm, so it's a global variable, R7, in my calculator program. We'll ignore B for now.

I also figured I'd changed the algorithm so that i and k count down to zero instead of up to N. However, no matter how I tweaked the loop counting in the C program's PERM() function and the character subscripting in the INTERCHANGE() function, I couldn't match the output of the calculator program. Finally, it had escaped my notice before, but H&S's algorithm doesn't generate the permutations in what I consider to be the "correct" order! For example, the permutations of "abc" listed in the book are different than what H&S's own algorithm actually generates:

In English, H&S's algorithm defines the permutations of a set of N characters as each character followed by the permutations of the remaining N-1 characters. In their second example, the permutations of "abcd" consist of:

• 'a' followed by the permutations of "bcd",
• 'b' followed by the permutations of "acd",
• 'c' followed by the permutations of "bad" (not "abd"), and
• 'd' followed by the permutations of "bca" (not "abc").

My preference (and the way my calculator program works) is that the initial sequence of the remaining characters be in the same order as the characters' appearance in the original permutation string, "abcd" in this case. H&S, however, simply swap the first character, 'a', of the original string and the new initial character to get the initial sequence of remaining characters. For example, swapping 'a' and 'c' in "abcd" gives 'c' followed by the permutations of "bad" instead of the desired "abd".

I don't remember magically fixing Horowitz's and Sahni's permutation algorithm to generate the permutations in the "right" order (and I wouldn't know where to begin to fix it now), so I think it is evident that I did not use H&S's algorithm. But where did I get my algorithm? I guess I'll keep trying to reverse-engineer it. (I later implemented a TI-58 program using a genuinely iterative permutation algorithm without a stack, much faster than the recursive algorithm, and I don't remember where I found that algorithm either.)

Note that the program generates all the permutations of a string and does not prune any duplicates. For example, the 6-character string "TRY IT" has two Ts, which the program treats as essentially different characters. Consequently, it will generate two instances of "TRY IT": "T₁RY IT₆" and "T₆RY IT₁". In fact, the program will print out 720 permutations of "TRY IT" (the expected number for a 6-character string), half of which (360) are duplicates because of the two Ts.

Download, Set Up, and Run the Program

Emulator Files

NOTE that all the files below (".t58", ".hlp", ".lst", and ".wri") are ASCII files with Windows-style carriage-return/line-feed line endings; the TI58C EMULATOR won't load the files correctly if they have Unix-style line-feed endings.

Files for Pierre Houbert's TI58C EMULATOR:

• permutations.zip - everything and more in a ZIP archive, including a README.txt file.

or, separately:

• permutations.t58
• permutations.hlp - emulator help file.
• permutations_01.wri - predefined contents for memory registers 0-24.

Simply load "permutations.t58", clicking the "with datas" checkbox so the emulator will automatically load the ".wri" file. The memory registers are preloaded for the "TRY IT" example described below. After loading the program and memory registers in one operation, go ahead and run (R/S) the program!

Houbert's emulator can also load the program in Guillaume Tello's ".lst" file format:

• permutations.lst

The Real Calculator

First of all, attach the calculator to the printer, plug the printer in, and turn on the calculator and printer.

Next, configure the calculator for 240 programming locations and 30 memory registers:

3 2nd Op 17

After entering the keystrokes above, an actual TI-58 calculator would display "239.29" (locations 0-239 and registers 0-29). (Pierre Houbert's TI58C EMULATOR has 990 programming locations and 1000 memory registers, so "989.999" is displayed no matter how you configure it.)

Press LRN, key in the entire program without mistakes (!), and press LRN again to exit program entry mode.

Memory Registers

Clear all of the memory registers:

2nd CMs

It's already zero, but initialize the permutation count (R0) to zero:

CLR STO 00

Initialize R6 to one less than the length of the permutation string and R7 to exactly the length of the string. (In short, R7 is the length of the string and R6 is one less.) For example, if your string is "TRY IT" (6 characters), you would enter the following:

5 STO 06
6 STO 07

Initialize the stack pointer (R8) to point to the top of the stack. The stack starts with memory register 9, so set R8 to 9:

9 STO 08

Store the character indices (1-9 and 0) on the top of the stack (R9). This value is an integer between 1 and 10 digits in length (depending on the length of the permutation string), "nnnnnnnnnn". An index determines which memory register (20-29) holds that character's printing code.

To simplify the program, index 0 and memory register 20 have special meanings. If the string being permuted is less than 10 characters in length, index 0 always represents a space character and memory register 20 must contain the printer code (00) for the space character. (Consider a 3-character string with indices 123; the program has to pack characters in groups of 5 for loading into the alphanumeric printer registers, so it treats 123 as a 5-digit number with leading zeroes, 00123. Those zeroes will automatically insert the blank character code (00), retrieved from memory register 20, in the left two positions of the printer register.)

If the string is exactly 10 characters in length, you can use indices 0-9 and memory registers 20-29 any way you please. (Because the groups of 5 are fully populated—no implicit leading zeroes—there's no necessity to reserve index 0. Come to think of it, I guess this is also true for strings of length 5 ...)

For example, "TRY IT" has 4 different characters plus the space. Indices 1 (memory register 21) through 4 (memory register 24) reference the printer character codes for T, R, Y, and I, respectively. (I chose indices 1-4 for simplicity, but they're arbitrary as long as you enter the printer codes in the correct memory registers 20-29.) Key in the following six indices for "TRY IT" (0 is the space between the words):

123041 STO 09

Printer Character Codes

Lookup and store the printer codes corresponding to the indices in the permutation string. The PC-100 alphanumeric character codes (decimal numbers, not octal!) from Guillaume Tello's Texas Instruments TI 58C/TI 59 page:

In the "TRY IT" example above, memory register 20 is always zero and memory registers 21-24 hold the printer character codes for T, R, Y, and I, respectively (ignore the parenthesized comments):

CLR STO 20 (blank)
37 STO 21 (T)
35 STO 22 (R)
45 STO 23 (Y)
24 STO 24 (I)

Run the Program

The program is now ready to run, so:

R/S

The printer should start printing out the permutations at irregular intervals:

TRY IT
TRY TI
TRYI T
TRYIT
TRYT I
TRYTI
TR YIT
TR YTI
  .
  .
  .
TI YRT

      720

Generating and printing the 720 permutations for a 6-character string (such as "TRY IT") using an actual TI-58 calculator and PC-100 printer took six hours, if I remember correctly. Using Pierre Houbert's TI58C EMULATOR, the program completes in a speedy 15 minutes on my desktop and a blazingly fast 4½ minutes on my laptop—nice!

Memory Registers

Register(s)	Usage
0	Total # of permutations printed. (Incremented here after printing a string permutation.)
1	Temporary storage: Value when added to A that converts the first swap character to the second. (Calculated previously and used here.) When printing a string permutation, the fractional part of this register contains the indices of the 5 rightmost characters in the string. (Leading zeroes are inserted in the fraction if the length of the string is less than 5.) The register's value is calculated here and used in subroutine AssembleWord().
2	Temporary storage: Value when added to A that converts the second swap character to the first. (Calculated previously and used here.) When printing a string permutation, the fractional part of this register contains the indices of the characters preceding the 5 rightmost characters in the string. (Leading zeroes are inserted in the fraction if the length of the string is less than 10 characters.) The register's value is calculated here and used in subroutine AssembleWord().
3	Temporary storage: antilog (R5) = 10R5; used to mask out first swap character in A. (Computed here.) Used by AssembleWord() to construct the 5-character (10-digit) character-code string to be loaded into the printer's alphanumeric registers.
4	Temporary storage: antilog (R6) = 10R6; used to mask out second swap character in A. (Computed here.)
5	Index in A of first character to be swapped?
6	Index in A of second character to be swapped?
7	The length (1≤N≤10) of the string being permuted. This is a setup parameter which must be set prior to running the program.
8	Stack pointer (SP). *R8 points to the memory register containing the current call "frame". Pushing a call frame on the stack increments R8 and popping a frame decrements R8.
09 - 19	The call stack, beginning with register 9 and growing upwards (possibly to register 19). One call frame is stored per memory register and is encoded as a number, "nnnnnnnnnn.ik", where the ten integer digits (1-9 and 0) are the current configuration of the permutation indices and the two fractional digits are the values of local variables i and k, respectively. The very first call frame, in register 9, is a setup parameter which must be set prior to running the program; you only need to specify the indices for the initial permutation string, "nnnnnnnnnn" (or fewer digits for a shorter string).
20 - 29	Print codes, one letter per memory register. Registers 20-29 contain the two-digit character codes for the characters corresponding to indices 0, 1, 2, ..., 9 in the permutation string. The PC-100 alphanumeric character codes (decimal numbers, not octal!) from Guillaume Tello's Texas Instruments TI 58C/TI 59 page:

Program Listing