Calculating Fibonacci in Balanced Ternary

thomasthespacefox profile image Thomas Leathers ・3 min read


Balanced ternary is quite an obscure base number. Its also quite interesting, though that may be personal bias given i actually am chief developer for The SBTCVM Project, a project that develops balanced ternary virtual machines and related tools, and libraries. primarily in python.

And while I'm not about to explain the thousands of lines of python that are SBTCVM. Lets take a look at a practical example of a balanced ternary program written in SBTCVM assembly (often just called "tasm"). (for sake of simplicity, this is a simplified version of SBTCVM's Fibonacci demo, fib.tasm)

#non-important system configuration.

#set initial values of CPU registers 1 and 2.

#instruction that dumps the value of register 1 to the TTY
#add the values of register 1 and 2 and store sum into register 1
#store register 2 current value in scratch memory
#set register two and check for an integer overflow fault, if so leave loop
#copy register 1 to register 2
#read scratch memory location where reg 2 was stored.
#goto the "goto reference" "fibloopback"
#usual shutdown routine for VM

What is going on here?

Step by step:

set the two starting values into CPU registers 1 and 2 (1 is the first register, SBTCVM has no "register 0")


dump Register 1 to TTY (this is outputting the results)
the second vertical bar followed by the label, is what is called a "goto reference" in SBTCVM assembly, basically the assembler calculates the address that said instruction is located at in the resulting "trom".


add register 1 and register 2 and store sum in register 1 (using 9-trit integer arithmetic)

write register 2 to "scratch memory 1" scratch memory is basically just an IObus device that acts as scratch memory. while memory bus labels are defined in-source, the IObus labels are hard-coded.

this sets register 2 to the value that is returned into register 1 if an arithmetic operation "rolls over". this is always the opposing end of the 9-trit integer range, to allow for a predictable fault state.

this compares register 1 and 2 and if so, goes to the instruction in data.
sbtcvm's assembler sets this to the location of the "fibdone" label due to the "|>label" usage.

this copies register 1 to register 2

this reads that same scratch memory location from before, only into register 1 instead of register 2

Goto the address specified in data, (again, the assembler sets this automatically to the memory location of "fibloopback" due to the "|>label" usage.

null operation.

This stops the VM. triggering what is called a VM SYSHALT, SOFT STOP condition.

Lets look at the output.

TTY|REG1 DUMP:00000000+ 1
TTY|REG1 DUMP:00000000+ 1
TTY|REG1 DUMP:0000000+- 2
TTY|REG1 DUMP:0000000+0 3
TTY|REG1 DUMP:000000+-- 5
TTY|REG1 DUMP:000000+0- 8
TTY|REG1 DUMP:000000+++ 13
TTY|REG1 DUMP:00000+-+0 21
TTY|REG1 DUMP:00000++-+ 34
TTY|REG1 DUMP:0000+-00+ 55
TTY|REG1 DUMP:0000+0+0- 89
TTY|REG1 DUMP:000+--+00 144
TTY|REG1 DUMP:000+00-0- 233
TTY|REG1 DUMP:00+---00- 377
TTY|REG1 DUMP:00+0----+ 610
TTY|REG1 DUMP:00++0+--0 987
TTY|REG1 DUMP:0+-+--0++ 1597
TTY|REG1 DUMP:0++--0-0+ 2584
TTY|REG1 DUMP:+-0-+-0-- 4181
TTY|soft stop.
TTY|Press enter to exit.

As you can see, the output stops at 4181, as SBTCVM Mark 2 can't store a positive integer greater than 9841. but 9 trits has 19,683 combinations, why are these numbers different? well, it has to do with a fundamental property of balanced base numbers: They can store an equal number of values above zero as they can store below zero. This is why SBTCVM's full Fibonacci demo is able to calculate the negative equivalent just as easily, by just inverting the inputs.

comments and questions welcome.

Posted on by:

thomasthespacefox profile

Thomas Leathers


Hi, I'm Thomas, chief developer of the SBTCVM project, and all around artist and programmer. I do have more of an understanding of balanced ternary than most i would say.


Editor guide