DEV Community

Thomas Leathers
Thomas Leathers

Posted on

Calculating Fibonacci in Balanced Ternary

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 
Enter fullscreen mode Exit fullscreen mode

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. 
Enter fullscreen mode Exit fullscreen mode

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.

Top comments (0)