Ternary Data Types for C ProgrammersVersion 1.0, Dec 29, 2015
Part of
the Ternary Manifesto
© Copyright 2015, distributed under the Creative Commons Attribution 4.0 International license. Disclaimer: This is preliminary work, the author takes no responsibility for errors in this work but would appreciate being informed of such errors. Acknowledgement: This work was partially supported by Jinn Labs. |
The files libter9.h and libter27.h, along with their associated object files allow programmers to work with binary-coded ternary (BCT) integers. Here is an example that computes the Fibonacci sequence using 27-trit ternary integers:
#include "libter27.h"
#include "libter27io.h"
main () {
uter27_t i = UTER27_C_0;
uter27_t j = UTER27_C_1;
for (;;) {
uter27_t k = uter27_add( i, j );
putdec_uter27( i, stdout ); putchar( '\n' );
i = j;
j = k;
}
}
In BCT, each trit (ternary digit) is represented by two bits, just as binary-coded decimal uses 4 bits per digit.
As a general convention, names given in upper case refer to entities created by #define statements in the header file. So, for example, UTER27_C_0 is a defined alias for the constant zero given as a 27-trit unsigned ternary number.
As a general convention, names given in lower case refer to entities created in C. Thus, uter27_add() is a function that adds two 27-trit unsigned ternary numbers.
As a general convention, following the lead of stdint.h, all type names are of the form SterNN_t where S may be either u for unsigned or b for balanced ternary and where NN indicates the size of the associated variable in trits (ternary digits) either 9 or 27 in the basic ternary package. Larger and smaller sizes may be provided in later upgrades.
Aside from output functions, function names are always prefixed with the type of their return value. Unless explicitly stated, arguments to functions will be of the same type, so uter27_add() is a function that adds two 27-trit unsigned ternary arguments and returns the sum in the same form.
Output functions are always prefixed with put, in the style of the C <stdio> routines. As with fputc() and fputs(), the second argument to these routines specifies the output file. Future releases will support input functions similarly, with the prefix get.
Each of the header files libter9.h and libter27.h has a counterpart, libter9io.h and libter27io.h that offers input-output support for the corresponding data types. Input-output is separated from other functions because there are many cases where input-output is not needed. Including the input-output header file will automatically include the basic header file if it has not already been included.
Throughout the implementation, comments containing the string BUG: indicate known deficiencies or questions about the code. The most pervasive deficiency is that out-of-range or illegal values are generally not checked. Thus, division by zero and similar mistakes will produce incorrect results.
This package uses the C standard integer package,
This package supports both unsigned and balanced ternary (signed) using the following representations:
Unsigned Balanced BCT 0 –1 00 1 0 01 2 +1 10
Note that the representation used for zero for balanced numbers is not the same as the representation used for unsigned numbers. This representation choice allows conventional unsigned binary comparisons to produce the correct result so long as both comparands are of the same type (either both signed or both unsigned, and the same length).
Given that two bits are used for each trit, 9-trit ternary values
are actually represented using at least 18 bits, rounded up to the next
available binary integer size which is 32 bits under the
typedef uint32_t uter9_t; /* 9-trit unsigned ternary in 32-bit binary */ typedef uint64_t uter27_t; /* 27-trit unsigned ternary in 64-bit binary */ typedef uint32_t bter9_t; /* 9-trit balanced ... */ typedef uint64_t bter27_t; /* 27-trit balanced ... */
Balanced and unsigned ternary numbers have a special relationship becaused balanced ternary is actually a biased ternary number system that can be seen in the following table of all 2-trit numbers:
Unsigned BCT Balanced Dec. Tern. Tern. Dec. 0 00 0000 – – –4 1 01 0001 – 0 –3 2 02 0010 – + –2 3 10 0100 0 – –1 4 11 0101 0 0 0 5 12 0110 0 + 1 6 20 1000 + – 2 7 21 1001 + 0 3 8 22 1010 + + 4
In the above table, note that the unsigned ternary representation of 0 is the same as the balanced representation of –4, and similarly, the balanced unsigned representation of 4 is the same as the balanced representaiton of 0. As such, balanced ternary numbers can be considered to be a biased number system.
In general, for an n-trit number, the bias b is ⌊ 3n/2 ⌋ which is (3n–1)/2. The ternary representation of b is n consecutive ones.
Also note that the bias for an n-trit number is equal to the maximum balanced ternary value representable in n trits, and note that the unsigned ternary representation of the bias is the same as the balanced ternary representation of zero.
Given that we have an add mechanism that works for unsigned ternary numbers, we can make this mechanism work for balanced ternary numbers as follows:
Given the balanced addends i and j, these correspond to the unsigned ternary values i+b and j+b. The unsigned sum is therefore (i+b)+(j+b) which equals (i+j)+2b. Subtracting the bias b from this, we get (i+j)+b which is the unsigned value with the same representation as the desired balanced sum. Similar tricks can be used for subtraction and to compute an unsigned sum using an adder that produces only a balanced sum. This trick was used directly in an early version of the header files:
#define BTER9_ADD( a, b ) uter9_sub( uter9_add( (a), (b) ), BTER9_C_0 ) #define BTER27_ADD( a, b ) uter27_sub( uter27_add( (a), (b) ), BTER27_C_0 )
The trick to computing unsigned BCT sums is an old one, originally developed in the 1960s for computing BCD sums on binary computers (see, for example, IBM, 1963). This basic methodology was modified to do packed BCD arithmetic (see, for example, Jones 1999). Applying this methodology to unsigned 9-trit BCT gives the following C code that was used in an early version of <libter9.c> prior to several optimizations:
uter9_t uter9_add( uter9_t a, uter9_t b ) {
uter9_t c = a + UINT32_C(0x00015555);
uter9_t d = b + c; /* tenative sum */
uter9_t e = b ^ c; /* sum without carry propagation */
e = e ^ d; /* just the carry bits */
e = ~e & UINT32_C(0x00055554); /* 1s where no carry frm trit */
e = e >> 2; /* fix: minus 1 wherever no carry from trit */
return (d - e) & UINT32_C(0x0003FFFF);
}
The above addition algorithm is the primary justificaiton for the encoding we use here. This algorithm uses 8 basic operations, and as we will see, balanced ternary addition takes 15 operations. In contrast, the balanced and unsigned addition algorithms used by Frieder and Luk, 1975 both required 20 oprations. (In these operation counts, the a and not b operation has been counted as a single operation.) Our approach pays a price, however, in the use of several 'magic' constants.
The radix-complement can be used compute the unsigned difference of two unsigned numbers, in any number base. In ternary, the 3's complement is computed by incrementing the 2's complement, where the ternary 2's complement is computed by subtracting the number from 222...3. This compares with the 9's complement of a decimal number, computed by subtraction from 999...10 or the 1's complement of a binary number, computed by subtraction from 111...2. Beware that the ternary 2's complement is quite different from the binary 2's complement. Here is code from an early version of <libter9.h>:
#define UTER9_2S_COMP( a ) (UINT32_C(0x0002AAAA) - (a)) #define UTER9_3S_COMP( a ) (UTER9_ADD( UTER9_2S_COMP( a ), UTER9_C_1 )) #define UTER9_SUB( a, b ) (UTER9_ADD( (a), UTER9_3S_COMP( b )))
The basic operations of ternary logic are min and max corresponding to the and and or operations of Boolean logic. For logic operations, we recode the ternary digits from their arithmetic representation to their logic representation as follows:
Unsigned Balanced BCT arithmetic logic 0 –1 00 00 1 0 01 01 2 +1 10 11
Once recoded, a Boolean and operation applied to a pair of 2-bit binary-coded ternary digits will compute the min of the ternary digits, and or computes the max. Conversion between arithmetic and logic representations in either direction is a simple matter of inverting the least significant bit of the ternary digit whenever the most significant bit is one. This conversion was done with the following code in an early version of the <libter9.h> file:
#define _TER9_LOGIC( a ) ((a) ^ (((a) & UINT32_C(0x0002AAAA)) >> 1))
Some simple benchmarks illustrate the performance of this code. These tests were done on an Intel Core i3 3.06 GHz computer under the GCC 4.2 compiler with the default compilation options.
The first benchmark tests the speed of addition and subtraction:
void count() {
int i = 2;
while (i != MAX) {
int j = i;
for (;;) {
int k = i - j;
if (k == i) break;
j = j - 1;
}
i = i + 1;
}
}
Doing this computation with type int changed to type uter9_t was a factor of 10.1 slower than using type int16_t. Similarly, uter27_t was a factor of 11.6 slower than int64_t.
The following code gives an indication of the relative speed of the divide operation:
void collatz() {
int i = 2;
while (i != MAX) {
int j = i;
while (j != 1) {
if (j%2 == 0) { /* even case */
j = j/2;
} else { /* odd case */
int k = 3*j + 1;
if (k > MAX) break;
j = k;
}
}
i = i + 1;
}
}
Doing this computation with all variables declared as type int above changed to type uter9_t is a factor of 19.8 slower than using type int16_t.
Similarly, uter27_t was a factor of 38.4 slower than int64_t. For both the binary and ternary cases, multiply and divide times are expected to be proportional to the number of digits; for the binary code, however, the divide times don't dominate the total execution time, while they do in the ternary case.