libter27.h 27-trit Ternary Support

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
  Converting Between 9 and 27-trit Representations
Input/Output
  Heptavintimal
  Decimal

Data Types and Constants

The following ternary data type is provided:

uter27_t

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

UTER27_C_0 through UTER27_C_26

The numerical constants 0 through 26 represented as 27-trit unsigned numbers.

UTER27_C_MAX = 3²⁷ – 1 = 7,625,597,484,986

The the maximum value representable in this type.

UINT16_UTER27_C_MAX = 3²⁷ – 1 = 7,625,597,484,986

The equivalent binary representation of the maximum value.

bter27_t

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

BTER27_C_0 through BTER27_C_13 and BTER27_C_N1 through BTER27_C_N13

The numerical constants 0 through 13 and –1 through –13 represented as 27-trit balanced numbers.

BTER27_C_MAX = (3⁹ – 1)/2 = 3,812,798,742,493

The the maximum value representable in this type.

INT16_BTER27_C_MAX = (3⁹ – 1)/2 = 3,812,798,742,493

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 -bter27 100 150
#define BTER27_C_100	UINT64_C(0x0015555555555686)
#define BTER27_C_150	UINT64_C(0x0015555555555841)

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:

uter27_add( a, b )

bter27_add( a, b )

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

uter27_sub( a, b )

bter27_sub( a, b )

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

bter27_neg( a )

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

uter27_addsr_c( a, b, s )

bter27_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,
    bter27_addsr_c( BTER27_C_5, BTER27_C_0, 1 ) == BTER27_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.

uter27_addc( a, b, c )

uter27_carry

bter27_addc( a, b, c )

bter27_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 uter27_carry or bter27_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 27-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 Ster27_sD_c( a, b ) where Ster27 is one of the ternary type prefixes uter27 or bter27. 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 bter27_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.

uter27_sl_c( a, b )

bter27_sl_c( a, b )

27-trit unsigned and balanced left shift, equivalent to a×3^b, truncated to the indicated precision.

uter27_sr_c( a, b )

bter27_sr_c( a, b )

27-trit unsigned and balanced right shift, equivalent to a÷3^b, 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,
    bter27_sr_c( BTER27_C_8, 1 ) == BTER27_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:
    BTER27_SR_C( x, 1 ) == bter27_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:

ter27_min( a, b )

27-trit ternary min or logical and function. Each trit of the result is the minimum of the corresponding trits of the two operands.

ter27_max( a, b )

27-trit ternary max or logical or function. Each trit of the result is the maximum of the corresponding trits of the two operands.

ter27_neg( a )

27-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:
    TER27_MAX( x, y ) == ter27_max( x, y ).
Using the macro verions avoides the overhead of a subroutine call and is appropriate in applications where speed is particularly important.

ter27_xor( a, b )

27-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).

ter27_equ( a, b )

27-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:

uter27_mul( a, b )

bter27_mul( a, b )

27-trit unsigned and balanced multiply. The behavior of these routines for out-of-range results is currently undefined.

void_uter27_div( a, b )

uter27_quo

uter27_rem

void_bter27_div( a, b )

bter27_quo

bter27_rem

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

(uter27_div( a, b ), uter27_quo)
(bter27_div( a, b ), bter27_quo)

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

0 ≤ (uter27_div( a, b ), uter27_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 ≤ (uter27_div( a, b ), uter27_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:

(uter27_div( a, b ), uter27_rem) = b/2
(uter27_div( a, b ), uter27_rem) = –b/2

void_bter27_div_down( a, b )

void_bter27_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_uter27_mul( a, b )

uter27_prod_low

uter27_prod_top

void_bter27_mul( a, b )

bter27_prod_low

bter27_prod_top

27-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 27 least-significant trits, and the second holding the 27 most-significant trits. In general, even in the presence of overflow and aside from speed,

(void_uter27_mul( a, b ), uter27_prod_low) = uter27_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_uter27_divl( ah, al, b )

uter27_rem

uter27_quo

void_bter27_divl( ah, al, b )

bter27_rem

bter27_quo

27-trit unsigned and balanced long divide. The long divide functions divide an 54-trit dividend by the 27-trit divisor b. The dividend is expressed as two values, ah, the top 27 trits and al, the bottom 27 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_uter27_div( a, b ) = void_uter27_divl( UTER27_C_0, a, b )

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

void_bter27_mul( a, b );
void_bter27_divl( bter27_prod_top, bter27_prod_low, b );

we can assert bter27_quo = a, and, we can assert bter27_rem = BTER27_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 uter27_t uter27_c_100 = uter27_uint64( UINT64_C(100) );

This declares uter27_c_100 to be a 27-trit unsigned ternary constant with the numeric value 100₁₀. Here, the UINT64_C() function from <stdint.h> is the standard way to write a constant of the indicated (binary) integer type uint16_t in C, while uter27_uint64() is a function for converting this to ternary.

Converting To and From Binary

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

uter27_uint64( a )

bter27_int64( 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.

uint64_uter27( a )

int64_bter27( 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:

bter27_uter27( 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.

uter27_bter27( 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.

Converting Between 9 and 27-trit Representations

The following functions are provided for converting between ternary data types of different widths. For binary integer types in C, widening and narrowing are done implicitly when dictated by context. For ternary values, widening and narrowing must be done explicitly.