loading...

Calculating Fibonacci in Balanced Ternary

thomasthespacefox profile image Thomas Leathers ・3 min read

Overview

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.
TTYlinedraw|on
TTYmode|54

#set initial values of CPU registers 1 and 2.
setreg1|00000000+
setreg2|00000000+

#instruction that dumps the value of register 1 to the TTY
dumpreg1|000000000|fibloopback
#add the values of register 1 and 2 and store sum into register 1
add
#store register 2 current value in scratch memory
IOwrite2|>mem1
#set register two and check for an integer overflow fault, if so leave loop
setreg2|---------
gotodataif|>fibdone
#copy register 1 to register 2
copy1to2
#read scratch memory location where reg 2 was stored.
IOread1|>mem1
#goto the "goto reference" "fibloopback"
gotodata|>fibloopback
#usual shutdown routine for VM
null|000000000|fibdone
stop

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")

setreg1|00000000+
setreg2|00000000+

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".

dumpreg1|000000000|fibloopback

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

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.
IOwrite2|>mem1

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.
setreg2|---------

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.
gotodataif|>fibdone

this copies register 1 to register 2
copy1to2

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

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

null operation.
null|000000000|fibdone

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

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

@thomasthespacefox

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.

Discussion

pic
Editor guide