Ternary computing for the browser!
by Edmund Griffiths, June 2017
Unlike Setun, which was designed to be usable for practical purposes, Setunka is consciously minimalist: features such as memory paging, an index register, a ‘multiply’ instruction, floating point support, etc., have been ruthlessly dropped. The result is a very simple virtual machine that hopefully allows users to learn the principles of base three computing without having to absorb a large mass of details. It should work with any browser, but has been optimized for devices with smaller screens.
The name Setunka [Сетунька] may be interpreted either as meaning ‘little Setun’ or as referring to the river Setunka, which is a tributary of the Setun (after which the Setun computer was named). It is pronounced with the stress on the first syllable: SE-tun-ka. If you do not know Russian but would still like to pronounce the name accurately, the way a speaker of Spanish would pronounce Sétuñca is a reasonable approximation.
I would be very grateful if you could email me in the event that you discover any bugs.
Trits, trytes, and balanced nonary
Setunka, like Setun, employs the balanced ternary system. Each ternary digit, or trit, can take one of the three values +1, 0, and -1—abbreviated for convenience to +, 0, and -. This allows negative numbers to be stored naturally, and does away with the distinction between signed and unsigned values. Trits are grouped into six-trit words (trytes), each of which can store a number in the range from decimal -364 to 364.
A more human-readable representation of balanced ternary is provided by balanced nonary (base nine), in which each digit represents two trits and can take a value between -4 and 4. To avoid confusion, the minus sign is written above each negative digit rather than to the left of it: so the number five would be written 14̄ (one nine, and minus four ones). Balanced nonary plays the same role in programming a ternary computer as hexadecimal or octal does on a binary machine, and learning to read it fluently is similarly important.
Setunka’s memory consists of eighty-one trytes numbered from 4̄4̄ to 44 nonary (-40 to 40 decimal), for a total of decimal 486 trits. (This compares to Setun’s decimal 1,458 trits—three times as much—divided into decimal 162 nine-trit words, plus drum storage.) Memory contents are displayed on the scrollable listing near the top of the Setunka page: on each line, we have (from left to right)
• the address, in ternary;
• the value stored at that address, in ternary;
• the address, in nonary;
• the value, in nonary;
• the interpretation, if any, in disassembler mnemonics;
• the character value, if any.
The contents of the registers are displayed just underneath the storage listing. They are:
• the six-trit accumulator or A register;
• the four-trit instruction pointer or I register;
• the one-trit condition flag or C register;
• the one-trit overflow flag or V register.
The condition flag is set to +, 0, or - depending on the sign of the number in the accumulator, and is updated each time an instruction is executed that does or could change the accumulator’s contents. It can also be set to equal the overflow flag, allowing conditional branching based on overflow; or it can be manually set to zero to allow for an unconditional jump in circumstances where you cannot prove what the sign of the accumulator will be.
If an ‘add’ or ‘add immediate’ operation produces a result that is less than decimal -364 or greater than decimal 364, only the six least significant trits are stored in the accumulator: but the overflow flag is set to + if the result was too high or to - if it was too low. Note that the logical shift instruction does not set the overflow flag.
Use the rounded buttons to set the values of each trit in the current tryte (pointed to by the I register, and marked with a cursor on the left of the scrollable disassembly listing). The < and > buttons move backwards and forwards within memory, each by one tryte. The button marked Back to @4̄4̄ returns you to the first tryte in memory, which is normally where you will want execution to begin.
Clicking Step causes the machine to execute the instruction to which the I register currently points and then halt with I pointing to the next instruction. Alternatively, you can click Run to run your program straight through at the rate of forty-five instructions per second (one hundredth of the speed at which Setun operated) until either a ‘halt’ instruction is reached or you click Stop. (Simply reaching tryte 44 will not cause execution to halt—the instruction pointer will just loop around to the beginning.)
Saving and loading
If you click Save, the contents of memory will be copied to the ‘Program tape’: the ‘tape’ can then be copied and pasted into a text editor, an email, etc. Clicking Load reads a program from ‘tape’ into memory.
Note that the Clear button clears the memory, output, and registers, but not the tape. It is a good idea to get into the habit of saving your programs onto tape before you try to run them, and then (if you want to edit the program or run it again) clicking Clear, Load, Save in that order. You will then always have a ‘clean’ copy on the tape. Remember that the tape is a copy of the whole contents of memory—so you should save before you run the program, not after, if you want variables etc. to be saved in their initial rather than their final state.
A few sample programs are provided to get you started: click Sample programs to show or hide a list of them, from which you can click on individual programs to mount them on the ‘tape reader’.
Programming by toggling trits one by one may seem offputting; but each instruction only takes a few clicks to enter, and the instruction set has been quite carefully designed to be simple and memorable in both ternary and nonary notation. It consists of eighteen instructions, listed below.
Users may be surprised by the absence of ‘subtract’ and unconditional ‘goto’, but they can both be easily synthesized using existing instructions. You will often know what the state of the condition flag has to be at a particular point in your program, so that you can use a conditional branch instruction as a ‘goto’; and, if not, you can set C equal to zero and then branch on zero. As for subtraction, balanced ternary accords negative numbers equal status with positive numbers. It is always just as easy to add (or add immediate) a negative constant as to subtract a positive one. If you want to subtract a variable from the accumulator you can make use of the fact that x - y = -(-x + y), so that you can subtract the number stored at address a from the accumulator by negating, adding, and negating:
2̄aa AD @aa
Instructions with operand in memory
++tttt 4nn B+ branch if condition flag positive
+0tttt 3nn B0 branch if condition flag zero
+-tttt 2nn B- branch if condition flag negative
0+tttt 1nn T∨ tritwise OR with accumulator
0-tttt 1̄nn T∧ tritwise AND with accumulator
-+tttt 2̄nn AD add to accumulator
-0tttt 3̄nn LD load accumulator
--tttt 4̄nn ST store accumulator
Instructions with immediate operand (4̄ to 4)
00+-tt 02n TS shift (positive left/negative right)
00-+tt 02̄n AI add immediate to accumulator
00-0tt 03̄n LI load accumulator immediate
Instructions with no operand
00++++ 044 W9 write as nonary number
00+++0 043 W3 write as ternary number
00+++- 042 WR write as character
00+00+ 031 CV set condition flag = overflow
00+000 030 C0 set condition flag zero
0000+- 002 T¬ negate accumulator
000000 000 HT halt
The machine’s character set currently consists of Unicode characters 000 to 444 nonary (zero to three hundred and sixty-four decimal); negative character codes are unused. This is probably not, however, the most generally useful six-trit character set that could be devised, and at some point in the future I may improve it. Support for the seven-bit ASCII standard is guaranteed in any future revision—but the current character mappings for codes outside that range are explicitly not guaranteed.
Truth table for tritwise OR
- 0 +
- - 0 +
0 0 0 +
+ + + +
Truth table for tritwise AND
- 0 +
- - - -
0 - 0 0
+ - 0 +
A I C V
To load each sample program, click its title to mount it on the tape reader and then click Load.
Counting in nonary
A very simple program that prints the numbers from decimal minus ten to decimal plus ten in balanced nonary.
Prints a string (stored as a zero-terminated array of character codes). This program illustrates character output and also the use of self-modifying code for array access.
Prompts the user for values of a and b and then prints a AND b, a OR b, and a shifted by the least significant two trits of b. Also illustrates console input: to enter a number when prompted, use the trit buttons then click > followed by Run.
Prints Fibonacci numbers in nonary until it reaches a value that is too large to fit into six trits, then halts. Illustrates testing for arithmetic overflow.
Sieve of Eratosthenes
Finds and prints the first few prime numbers.