libter9.h: 9-trit Ternary Support

Version 1.0, Dec 29, 2015

Part of the libtern documentation
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

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

Contents

Data Types and Constants
Simple Arithmetic
  Simple Add and Subtract
  Special Add and Subtract
Comparsion
Shifting
Logic Functions
Multiplication and Division
  Simple Multiply and Divide
  Special Multiply and Divide
Conversion Functions
  Converting To and From Binary
  Converting Between Balanced and Unsigned Types
Input/Output
  Heptavintimal
  Decimal

Data Types and Constants

The following ternary data type is provided:

uter9_t
9-trit unsigned ternary numbers, with digit values 0, 1 and 2. The following constant definitions are provided for use with these types:

UTER9_C_0 through UTER9_C_26
The numerical constants 0 through 26 represented as 9-trit unsigned numbers.

UTER9_C_MAX = 39 – 1 = 19,682
The the maximum value representable in this type.

UINT16_UTER9_C_MAX = 39 – 1 = 19,682
The equivalent binary representation of the maximum value.

bter9_t
9-trit balanced ternary numbers, with digit values –1, 0 and +1. The following constant definitions are provided for use with these types:

BTER9_C_0 through BTER9_C_13 and BTER9_C_N1 through BTER9_C_N13
The numerical constants 0 through 13 and –1 through –13 represented as 9-trit balanced numbers.

BTER9_C_MAX = (39 – 1)/2 = 9,841
The the maximum value representable in this type.

INT16_BTER9_C_MAX = (39 – 1)/2 = 9,841
The equivalent binary representation of the maximum value.

For other constants, a utility program, terconst, is provided that will generate appropriate C definitions. The following dialogue illustrates the generation of balanced representations of 100 and 150:

$ terconst -bter9 100 150
#define BTER9_C_100	UINT32_C(0x00015686)
#define BTER9_C_150	UINT32_C(0x00015841)

The naming convention for constants generated by the terconst routine is the same as that for the predefined constants; in fact, the definitions for all but the first few predefined constants were created using terconst.

The hexadecimal values generated above are not intended to be human readable; they are, however, the binary-coded-ternary representations of the constants, packed 2 BCT digits per hexadecimal digit. For details, see the implementation notes.

Note that the unsigned and balanced ternary representations of zero are not the same. This is unlike the relationship between unsigned and two's complement binary numbers, where zero is represented identically in both systems, and more akin to the relationship between unsigned and biased binary numbers (as commonly used for the exponent field of floating point numbers). For more detail, see the implementation notes.

Simple Arithmetic

Simple Add and Subtract

The following add and subtract operators conform to the expectations of programmers used to working in high level languages:

uter9_add( a, b )
bter9_add( a, b )
9-trit unsigned and balanced ternary addition. In each case, the operands must be the same type as the result. Explicit conversion functions must be used for operands of any other type.

uter9_sub( a, b )
bter9_sub( a, b )
9-trit unsigned and balanced ternary subtraction. The second operand is subtracted from the first. In each case, the operands must be the same type as the result. Explicit conversion functions must be used for operands of any other type.

bter9_neg( a )
9-trit balanced ternary negation. Negation is not defined for unsigned ternary values. Negation is equivalent to subtraction from zero.

Special Add and Subtract

The following add and subtract functions are not typically found in high-level languages but are typical of operations found in arithmetic-logic units and are particularly useful when building high-precision number representations on a lower-precision foundation.

uter9_addsr_c( a, b, s )
bter9_addsr_c( a, b, s )
Note that the third parameter, s is an unsigned integer shift count. For most purposes,
    addsr_c( a, b, s ) = sr_c( add( a, b ), s ).
That is, this operation combines an add with a right-shift, or equivalently, an add combined with division by a power of three. Note, however, the combination of add() with sr_c() will discard the carry out of the add operation before shifting, while the combined addsr_c() preserves this carry.

In balanced ternary, shifts may produce unexpected results because of rounding to the nearest integer. This rounding rule minimizes the absolute value of the remainder. Thus,
    bter9_addsr_c( BTER9_C_5, BTER9_C_0, 1 ) == BTER9_C_2.
A programmer accustomed to unsigned numbers or binary computers would expect 5/3 = 1 with a remainder of 2, but here, we get 5/3 = 2 with a remainder of –1.

uter9_addc( a, b, c )
uter9_carry
bter9_addc( a, b, c )
bter9_carry
In general
    add( a, b ) == addc( a, b, C_0 )
for any of the ternary types. These variant add functions take a third parameter, carry-in, and deliver a second result, carry out in the global variables uter9_carry or bter9_carry. The absolute value of the carry-in parameter c must never exceed one.

A sequence of addc() instructions can be used to compose an add operation over operands of any length. The carry in to the least significant bit should be zero (as represented in the number system of the operands). The carry in to successively more significant addc() operations should be the carry out from the previous one.

Comparsion

The representation used for ternary data types is such that the standard C comparison operators <, <=, =, >=, > and != all give the correct results for both unsigned and balanced ternary numbers, so long as the operands are of the same type.

For the purpose of comparison, typing is defined strictly: Do not compare balanced and unbalanced ternary operands. Do not compare 9-trit operands with ternary operands of different widths. Unlike C and C++ binary integers, where comparison of different integer types involves automatic widening of the narrower operand to match the wider one, no automatic conversions are provided here. If operands of different types must be compared, explicit conversion functions must first be used to convert the operands to the same type.

Shifting

Shift operators shift the first operand left or right the number of trits indicated by the second operand. Shifting one place left is equivalent to multiplication by 3, while shifting one place right is broadly equivalent to division by 3.

All shift operators take the form Ster9_sD_c( a, b ) where Ster9 is one of the ternary type prefixes uter9 or bter9. This prefix gives the type of both the returned value and the first operand a, which is the operand that will be shifted. The sD field indicates the shift direction, either sl or sr, and the second operand gives the shift count, which must be a simple constant and which must be less than the number of trits in the type. For example bter9_sl_c( a, 1 ) is a balanced one-place left shift, multiplying the operand a by 3.

All shifts discard trits at one end of the operand while shifting in new trits at the opposite end. The new trits are always equal to zero in the number system of the shift. For unsigned shifts, this is the minimum value, while for balanced shifts, this is the middle value.

uter9_sl_c( a, b )
bter9_sl_c( a, b )
9-trit unsigned and balanced left shift, equivalent to a×3b, truncated to the indicated precision.

uter9_sr_c( a, b )
bter9_sr_c( a, b )
9-trit unsigned and balanced right shift, equivalent to a÷3b, except for unsigned shifts, the result is truncated toward zero, while for balanced shifts, the result is rounded to the nearest integer.

Note again, shifts in balanced ternary may produce unexpected results because of rounding to the nearest integer. This rounding rule minimizes the absolute value of the remainder. Thus,
    bter9_sr_c( BTER9_C_8, 1 ) == BTER9_C_3.
A programmer accustomed to unsigned numbers or binary computers would expect 8/3 = 2 with a remainder of 2, but here, we get 8/3 = 3 with a remainder of –1.

Note that because of the data representation used for ternary numbers, all of the shift functions are fairly simple. Because of this, equivalent macros are provided for all of the above shift operations. These differ from the above only in the capitalization of their names. Thus, for example:
    BTER9_SR_C( x, 1 ) == bter9_sr_c( x, 1 ).
Using the macro verions avoides the overhead of a subroutine call and is appropriate in applications where speed is particularly important.

Logic Functions

Logic functions operate identically on signed and unsigned Ternary values, so the names of these functions omit the u or b prefix designating unsigned or balanced operands.

The following table relates the values used in each trit for unsigned, balanced and ternary logic values:

Unsigned Balanced Logic
0 –1 false
1 0 unknown
2 +1 true

The following functions are provided:

ter9_min( a, b )
9-trit ternary min or logical and function. Each trit of the result is the minimum of the corresponding trits of the two operands.

ter9_max( a, b )
9-trit ternary max or logical or function. Each trit of the result is the maximum of the corresponding trits of the two operands.

ter9_neg( a )
9-trit ternary logical negation, the ternary equivalent of the not operation in Boolean logic. For unsigned operands, this is the same as a ternary 2's complement operation (where each trit is subtracted from 2), and for balanced operands, this is the same as negation.

Note that because of the data representation used for ternary numbers, the basic logic functions are fairly simple. Because of this, equivalent macros are provided for all of the above operations. These differ from the above only in the capitalization of their names. Thus, for example:
    TER9_MAX( x, y ) == ter9_max( x, y ).
Using the macro verions avoides the overhead of a subroutine call and is appropriate in applications where speed is particularly important.

ter9_xor( a, b )
9-trit ternary exclusive or, sometimes described as logical sum. In Boolean logic,
    a xor b = (a and not b) or (b and not a).
Similarly, in ternary logic,
    a xor b = (a min neg b) max (b min neg a).

ter9_equ( a, b )
9-trit ternary logical equivalence, sometimes described as logical product. In Boolean logic,
    a equ b = not(a xor b) = (a and b) or (not b and not a).
Similarly, in ternary logic,
    a equ b = neg(a xor b) = (a min b) max (neg b min neg a).

Note that equivlent macros are not provided for the xor() or equ() functions because these are sufficiently complex that there is no point to using a macro.

Multiplication and Division

Simple Multiply and Divide

The most basic multiplication and division routnes take arguments of the same type as their return type. For multiplication, these routines truncate their results to the indicated precision:

uter9_mul( a, b )
bter9_mul( a, b )
9-trit unsigned and balanced multiply. The behavior of these routines for out-of-range results is currently undefined.

void_uter9_div( a, b )
uter9_quo
uter9_rem
void_bter9_div( a, b )
bter9_quo
bter9_rem
9-trit unsigned and balanced divide and remainder. Note that the divide functions have a void return value, but they leave both the remainder and quotient in global variables. Where a/b suffices to take the quotient of two binary variables, the following expressions do this for ternary variables; note that when both quotient and remainder are needed, a second call to the appropriate _div routine is unneeded.
(uter9_div( a, b ), uter9_quo)
(bter9_div( a, b ), bter9_quo)

For unsigned division, the remainder always falls between zero and the divisor. That is:

0 ≤ (uter9_div( a, b ), uter9_rem) < b

For balanced division, the remainder follows a "round to nearest" rule, assuring that the accumulated error will be minimized after long strings of computations on integer approximations of real numbers. With this rule, the absolute value of the remainder will never be greater than half the absolute value of the divisor. That is:

– |b| /2 ≤ (uter9_div( a, b ), uter9_rem) ≤ + |b| /2

For balanced division, in the event that the fractional part of the un-rounded quotient is exactly 1/2, it may be rounded up or down; that is, either of the following may be true, and they are equally likely:

(uter9_div( a, b ), uter9_rem) = b/2
(uter9_div( a, b ), uter9_rem) = –b/2

void_bter9_div_down( a, b )
void_bter9_div_up( a, b )
There are two obvious alternative rounding rules for signed division: round the quotient down to the nearest integer, assuring a non-negative remainder, and round the quotient up, assuring a non-positive remainder. Euclid defined division in terms of rounding down over 2 millenia ago, but most programmers expect other rounding rules.

Special Multiply and Divide

The regular multiply routines give only the least significant word of the product. Special routines are provided that give (at marginally higher cost) a product double-word, allowing higher precision multiplication to be constructed from multiple lower precision multiply operations.

void_uter9_mul( a, b )
uter9_prod_low
uter9_prod_top
void_bter9_mul( a, b )
bter9_prod_low
bter9_prod_top
9-trit unsigned and balanced multiply. The long multiply function itself is a void function, leaving the product in a pair of global variables, one holding the 9 least-significant trits, and the second holding the 9 most-significant trits. In general, even in the presence of overflow and aside from speed,
(void_uter9_mul( a, b ), uter9_prod_low) = uter9_mul( a, b )

The long versions are slower because of the additional computations needed to retain the entire result instead of just the least significant trits.

void_uter9_divl( ah, al, b )
uter9_rem
uter9_quo
void_bter9_divl( ah, al, b )
bter9_rem
bter9_quo
9-trit unsigned and balanced long divide. The long divide functions divide an 18-trit dividend by the 9-trit divisor b. The dividend is expressed as two values, ah, the top 9 trits and The dividend is expressed as two values, al, the bottom 9 trits. In general, for both signed and unsigned forms, the normal (short) division operation faster than but otherwise equivalent to the long form. That is:

void_uter9_div( a, b ) = void_uter9_divl( UTER9_C_0, a, b )

In addition, long divide undoes the computation done by long multiply, that is, after:

void_bter9_mul( a, b );
void_bter9_divl( bter9_prod_top, bter9_prod_low, b );

Now, we can assert bter9_quo = a, and, we can assert bter9_rem = BTER9_C_0.

Conversion Functions

Conversion functions are named uniformly with a pair of type names in the form to_from where to gives the result type, and from gives the argument type. Thus, for example, if the terconst utility were not available, it would be reasonable to write:

const uter9_t uter9_c_100 = uter9_uint16( UINT16_C(100) );

This declares uter9_c_100 to be a 9-trit unsigned ternary constant with the numeric value 10010. Here, the UINT16_C() function from <stdint.h> is the standard way to write a constant of the indicated (binary) integer type uint16_t in C, while uter9_uint16() is a function for converting this to ternary.

Converting To and From Binary

The following conversions are provided for converting between ternary and binary:

uter9_uint16( a )
bter9_int16( a )
Conversions to ternary from binary. In each case, the range of binary values in the argument exceeds the range of ternary values representable in the result. The behavior of these routines for out-of-range values is currently undefined.

uint16_uter9( a )
int16_bter9( a )
Conversions to binary from ternary. In each case, the range of ternary values in the argument is entirely within the range of binary values representable in the result.

Converting Between Balanced and Unsigned Types

The following functions are provided for converting between signed and unsigned ternary data types:

bter9_uter9( a )
Conversion of unsigned operands to signed form. Here, the maximum value representable in the argument is twice the maximum that can be represented in the result. The behavior of this for out-of-range values is currently undefined.

uter9_bter9( a )
Conversion of signed operands to unsigned form. Here, negative operands cannot be represented in the result. The behavior of this for out-of-range values is currently undefined.

Input/Output

All of the output routines have names that start with put, following the conventions of the standard C putchar() routine. These are void functions, returning nothing, and they all take a file pointer as a second parameter, in the style of the standard C fputc() routine. So, putdec_uter9( x, stdout ) converts the unsigned 9-trit ternary value x to decimal text and outputs the value to the standard output file.

Heptavintimal

Heptavintimal (base 27) output is done identically for signed and unsigned numbers, since heptavintimal is used to output the internal representation of the value, not the interpretation of that representation. Thus, puthept_ter9() can be used to output either unsigned values of type uter27_t or balanced values of type bter27_t.

puthept_ter9( a, f )
Output the value a in heptavintimal from the C file f.

gethept_ter9( f )
Read a heptavintimal value from the C file f. On return, the file will be positioned to read the first character after the value read. Currently, there is no provision for handling out-of-range values.

Decimal

The following decimal conversion routines are available:

putdec_uter9( a, f )
putdec_bter9( a, f )
Output the decimal representation of the indicated ternary value; for balanced ternary, if the operand is negative, a leading minus sign is output.

getdec_uter9( f )
getdec_bter9( f )
Read a decimal value from the C file f. On return, the file will be positioned to read the first character after the value read. Currently, there is no provision for handling out-of-range values.