↑ Writing ↑


Permutations on a
TI-58 Programmable Calculator

TI-58 Programmable Calculator and PC-100 Thermal Printer


Download, Set Up, and Run the Program

Memory Registers

Program Listing



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:



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.

[Emulator window]
(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.


[Sinclair Scientific calculator]

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 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:

Book's list of results Algorithm's list of results
abc abc
acb acb
bac bac
bca bca
cab cba
cba cab

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:

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": "T1RY IT6" and "T6RY IT1". 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:

or, separately:

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:

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:


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:

TI PC-100 character codes

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:


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



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

Total # of permutations printed. (Incremented here after printing a string permutation.)
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().
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().
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.
Temporary storage: antilog (R6) = 10R6; used to mask out second swap character in A. (Computed here.)
Index in A of first character to be swapped?
Index in A of second character to be swapped?
The length (1≤N≤10) of the string being permuted. This is a setup parameter which must be set prior to running the program.
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:
TI PC-100 character codes

Program Listing

000 29 CP Clear the T register (CP's function in a program).
001 43 RCL 06  
002 06 06  
003 22 INV  
004 77 GE B if (R6 ≥ 0) then
005 12 B  
006 42 STO 05  
007 05 05  
008 76 LBL A Beginning of loop through end of loop? The value of R5 is in the display register on entering the loop and on each subsequent iteration.
009 11 A  
010 32 X/T R5->T
011 43 RCL 06  
012 06 06  
013 67 EQ A' if (R6 != R5) then
014 16 A'  
015 22 INV R4 = antilog(R6) = 10R6
016 28 LOG  
017 42 STO 04  
018 04 04  
019 73 RC* 08  
020 08 08  
021 55 /  
022 32 X/T Exchange *R8 (X) and R5 (T).
023 22 INV R3 = antilog(R5) = 10R5
024 28 LOG  
025 42 STO 03  
026 03 03  
027 55 /  
028 01 1  
029 00 0  
030 95 =  
031 22 INV  
032 59 INT  
033 65 *  
034 01 1  
035 00 0  
036 95 =  
037 59 INT  
038 42 STO 02  
039 02 02  
040 94 +/-  
041 42 STO 01  
042 01 01  
043 32 X/T R1->T
044 55 /  
045 43 RCL 04  
046 04 04  
047 55 /  
048 01 1  
049 00 0  
050 95 =  
051 22 INV  
052 59 INT  
053 65 *  
054 01 1  
055 00 0  
056 95 =  
057 59 INT  
058 44 SUM 01  
059 01 01  
060 22 INV  
061 44 SUM 02  
062 02 02  
063 43 RCL 01  
064 01 01  
065 65 *  
066 43 RCL 03  
067 03 03  
068 95 =  
069 74 SM* 08  
070 08 08  
071 43 RCL 02  
072 02 02  
073 65 *  
074 43 RCL 04  
075 04 04  
076 95 =  
077 74 SM* 08  
078 08 08  
079 43 RCL 06  
080 06 06 endif (R6 != R5)
081 76 LBL A' (from 015) Begin encoding new stack frame (using R6?).
082 16 A'  
083 55 /  
084 01 1  
085 00 0  
086 00 0  
087 85 +  
088 43 RCL 05  
089 05 05  
090 55 /  
091 01 1  
092 00 0  
093 85 +  
094 73 RC* 08  
095 08 08  
096 59 INT  
097 95 =  
098 72 ST* 08 Push the new frame onto the stack
099 08 08  
100 69 OP 28 Increment SP (R8)
101 28 28  
102 72 ST* 08  
103 08 08  
104 69 OP 36 Decrement R6
105 36 36  
106 81 RST endif (recursive call to permutation function)
Print String - prints the current permutation string. The printer can print a 20-character-wide line using the printer codes loaded into the four 5-character registers spanning the line. Since the program only prints out strings up to 10 characters in length, the program only uses the center two registers, #2 and #3, leaving the far left and right registers, #1 and #4, blank. The permutation string of 10 characters or less is thus printed right-justified in the central 10-character span of the line.
107 76 LBL B (from 004)
108 12 B  
109 73 RC* 08 Retrieve the character indices for the current permutation string.
110 08 08  
111 55 / Shift the rightmost 5 indices (with leading zeroes if N<5) to the right of the decimal point and store the result in R1. For example, if the current indices for a 7-character string were 1234567, then 0.34567 would be stored in R1.
112 05 5  
113 22 INV  
114 28 LOG  
115 95 =  
116 42 STO 01  
117 01 01  
118 59 INT Take the next 5 indices to the left, shift them (with leading zeroes if N<10) to the right of the decimal point, and store the result in R2. For example, if the current indices for a 7-character string were 1234567, then 0.00012 would be stored in R2.
119 22 INV  
120 44 SUM 01  
121 01 01  
122 55 /  
123 05 5  
124 22 INV  
125 28 LOG  
126 95 =  
127 42 STO 02  
128 02 02  
129 69 OP 00 Clear printer's alphanumeric registers for entire line.
130 00 00  
131 43 RCL 07 Full length N of string. If N>5, then load the leftmost N-5 characters into printer register #2, the remaining 5 characters into register #3, and then print the string. If N≤5, then load the characters into printer register #3 and print the string.
132 07 07  
133 32 X/T Exchange X and T.
134 05 5  
135 77 GE B' if (R7 > 5) then
136 17 B'  
137 71 SBR D call AssembleWord(R2)
138 14 D  
139 69 OP 02 Load printer's alphanumeric register #2 (characters 6-10) with the leftmost N-5 characters, right-justified.
140 02 02 endif (R7 > 5)
141 76 LBL B'  
142 17 B'  
143 43 RCL 01  
144 01 01  
145 42 STO 02  
146 02 02  
147 71 SBR D call AssembleWord(R2)
148 14 D  
149 69 OP 03 Load printer's alphanumeric register #3 (characters 11-15) with the rightmost 5 characters (or fewer if N<5), right-justified.
150 03 03  
151 69 OP 05 Print the alphanumeric registers (20 characters)
152 05 05  
153 69 OP 20 Increment R0 (total # of permutations printed)
154 20 20  
155 76 LBL C  
156 13 C  
157 43 RCL 08  
158 08 08  
159 32 X/T Exchange X and T.
160 09 9  
161 77 GE E All permutations generated (SP≤9)? Exit the program.
162 15 E  
163 69 OP 38 Not done. Decrement SP (R8)
164 38 38  
165 73 RC* 08 Pop last stack frame (encoded in value): "<character indices>.<variables>".
166 08 08  
167 22 INV Begin extracting variables from encoded stack frame.
168 59 INT  
169 65 *  
170 01 1  
171 00 0  
172 95 =  
173 42 STO 06  
174 06 06  
175 59 INT  
176 42 STO 05  
177 05 05  
178 22 INV  
179 44 SUM 06  
180 06 06  
181 01 1  
182 00 0  
183 49 PRD 06  
184 06 06  
185 29 CP Clear the T register (CP's function in a program).
186 69 OP 35 Decrement R5
187 35 35  
188 43 RCL 05  
189 05 05  
190 77 GE A End of loop
191 11 A  
192 61 GTO C  
193 13 C  
proc AssembleWord (R2) - assembles and returns the printer codes for 5 characters. The indices for the 5 characters are passed in through memory register R2 in the following format: "0.nnnnn", where each digit is an index (minus 20) into memory registers 20-29 (which contain the corresponding character codes). AssembleWord() returns the 5 two-digit characters codes in the display register as a single 10-digit number number that can be deposited into the desired alphanumeric register of the printer.
194 76 LBL D proc AssembleWord(R2)
195 14 D  
196 25 CLR  
197 42 STO 03 Set the character code accumulator (R3) to 0.
198 03 03  
199 05 5  
200 42 STO 05 R5 = 5 (always pack assemble 5 characters)
201 05 05  
202 76 LBL D' loop for R5 = 5 to 1
203 19 D'  
204 01 1  
205 00 0  
206 00 0  
207 49 PRD 03 Shift the character code accumulator (R3) two digits to the left (multiply by 100) so the next character code can be added.
208 03 03  
209 01 1  
210 00 0  
211 49 PRD 02 Expose the next character index in R2 (multiply by 10); e.g., 0.31416 * 10 = 3.1416, thus bringing out the index, 3, of the first character.
212 02 02  
213 02 2  
214 00 0  
215 44 SUM 02 R2 = R2 + 20
216 02 02  
Recall Printer Code - recalls the current character's printer code indirectly via R2. R2 contains a value, "2n.nnn", where the digit to the left of the decimal point is the current character's index into registers 20-29 and the digits to the right of the decimal point are characters still to be processed. A real TI-58 calculator only uses the integer portion of a memory register's contents when performing an indirect address through the register. However, the TI58C EMULATOR rounds the register's contents up or down to the nearest integer. For example, if R2 is 24.567, then "RC* 02" on a real TI-58 will retrieve the contents of R24, while the TI58C EMULATOR will round 24.567 up to 25 and retrieve the contents of R25. Until this is corrected, a temporary fix is to replace the following two program locations, "RC* 02", with "RCL 02 INT STO 04 RC* 04". (The emulator allows the program to grow larger than 240 locations.)
217 73 RC* 02 Retrieve the character code from memory register 20+index; e.g., if R2 contains 3.1416, get the character code from memory register 23.
218 02 02  
219 44 SUM 03 Insert the two-digit character code in the two least-significant digits of the accumulator (R3).
220 03 03  
221 43 RCL 02  
222 02 02  
223 59 INT  
224 22 INV  
225 44 SUM 02 R2 = R2 - int (R2) (Remove the just-processed index from R2; e.g. 3.1416 becomes 0.1416.)
226 02 02  
227 97 DSZ 05 D' end loop (for R5 = 5 to 1)
228 05 05  
229 19 D'  
230 43 RCL 03 Return the fully-assembled 5-character print codes in the display register (X).
231 03 03  
232 92 RTN endproc ;
End of Program - prints out the total number of permutations generated and stops the program.
233 76 LBL E  
234 15 E  
235 98 ADV  
236 43 RCL 00 Total number of permutations generated.
237 00 00  
238 99 PRT  
239 91 R/S Stop!

Alex Measday  /  E-mail