libter27.h 27-trit Ternary SupportVersion 1.0, Dec 29, 2015
Part of
the libtern documentation
© 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. |
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
The following ternary data type is provided:
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.
The following add and subtract operators conform to the expectations of programmers used to working in high level languages:
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.
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.
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.
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.
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.
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 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:
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.
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.
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_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
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_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_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 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_{10}. 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.
The following conversions are provided for converting between ternary and binary:
The following functions are provided for converting between signed and unsigned ternary data types:
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.
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_uter27( x, stdout ) converts the unsigned 27-trit ternary value x to decimal text and outputs the value to the standard output file.
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_ter27() can be used to output either unsigned values of type uter27_t or balanced values of type bter27_t.
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_uter27( x, stdout ) converts the unsigned 27-trit ternary value x to decimal text and outputs the value to the standard output file.
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_ter27() can be used to output either unsigned values of type uter27_t or balanced values of type bter27_t.
The following decimal conversion routines are available: