Balanced Ternary Arithmetic
April 14, 2015
We begin by writing a function that converts a decimal integer to ternary. As we learned in the previous exercise, (quotient n 3) does the wrong thing with negative n, so we use floor and the / division operator:
(define (ternary n)
(let loop ((n n) (ts (list)))
(if (zero? n) (normalize ts)
(case (modulo n 3)
; (quotient n 3) does the wrong thing if negative n
((0) (loop (floor (/ n 3)) (cons 0 ts)))
((1) (loop (floor (/ n 3)) (cons 1 ts)))
((2) (loop (floor (/ (+ n 1) 3)) (cons -1 ts)))))))
Turning a ternary number back into decimal works left-to-right through the trits, multiplying by 3 as it goes:
(define (decimal ts) (fold-left (lambda (x y) (+ x x x y)) 0 ts)) > (ternary 523) (1 -1 0 1 1 0 1) > (ternary -476) (-1 1 0 0 1 0 1)
Some people like to write ternary numbers as a string of trits with a plus sign, minus sign and zero for the 1, -1 and 0 trits:
(define (to-string ts)
(let ((digits '((0 . #) (1 . #\+) (-1 . #\-))))
(apply string (map (lambda (d) (cdr (assoc d digits))) ts))))
(define (from-string str)
(let ((chars '((# . 0) (#\+ . 1) (#\- . -1))))
(map (lambda (c) (cdr (assoc c chars))) (string->list str))))
> (to-string (ternary 523))
"+-0++0+"
> (to-string (ternary -476))
"-+00+0+"
Now the fun starts. Two ternary numbers are added trit-by-trit, from right-to-left, carrying as necessary. Here’s the addition table for two trits:
-1 0 1
---- ---- ----
-1 -1 1 -1 0
0 -1 0 1
1 0 1 1 -1
So to add two trits plus a carry, we first add the two trits, then add the carry in a second operation. Or, we could make a three-dimensional addition table and calculate the trit and the carry in a single step. The third possibility, which we choose, is to add the three trits using decimal arithmetic, then convert using the ternary function that we already wrote, and finally split the carry from the trit:
(define (plus xs ys)
(define (add x y c)
(let ((ts (ternary (+ x y c))))
(if (null? (cdr ts))
(values 0 (car ts))
(values (car ts) (cadr ts)))))
(let loop ((xs (reverse xs)) (ys (reverse ys)) (zs (list)) (carry 0))
(cond ((and (null? xs) (null? ys))
(normalize (cons carry zs)))
((null? xs)
(let-values (((c s) (add 0 (car ys) carry)))
(loop xs (cdr ys) (cons s zs) c)))
((null? ys)
(let-values (((c s) (add (car xs) 0 carry)))
(loop (cdr xs) ys (cons s zs) c)))
(else
(let-values (((c s) (add (car xs) (car ys) carry)))
(loop (cdr xs) (cdr ys) (cons s zs) c))))))
> (plus (ternary 523) (ternary 476))
(1 1 0 1 0 0 0)
> (decimal (plus (ternary 523) (ternary 476)))
999
Negating a number is easy; just multiply each trit, individually, by -1:
(define (negate xs) (map (lambda (d) (- d)) xs)) > (ternary 476) (1 -1 0 0 -1 0 -1) > (negate (ternary 476)) (-1 1 0 0 1 0 1)
Multiplication is easy: work through the multiplier trit-by-trit, working right to left, at each step shifting in one more zero on the right; if the current trit is 1, add the multiplicand (plus shifted zeros) to the accumulating product, if the current trit is 0, do nothing, and if the current trit is -1, add the negative of the multiplicand (plus shifted zeros) to the accumulating product:
(define (times xs ys)
(let loop ((xs (reverse xs)) (shift (list)) (prod (list)))
(if (null? xs) (normalize prod)
(loop (cdr xs) (cons 0 shift)
(case (car xs)
((-1) (plus (negate (append ys shift)) prod))
((0) prod)
((1) (plus (append ys shift) prod)))))))
> (times (ternary 523) (ternary 476))
(1 1 1 -1 0 -1 1 1 1 1 0 -1)
> (decimal (times (ternary 523) (ternary 476)))
248948
We’ll stop there. If you want to continue, you could do division using the grade-school algorithm, or you could write a library for working with fixed-point real numbers. Although binary computation won, in the early days of computing balanced ternary computation was considered as an alternative, because it is more efficient (the number of digits times the size of the “alphabet” is less for ternary than binary, leading to smaller, faster computation) and because comparisons are naturally three-valued (less than, equal, greater than), and there are still some arguments in its favor, not to mention some really neat trit-twiddling hacks. If you are interested, Google can tell you more.
You can run the program at http://ideone.com/97fr7R. Note that the ternary function changes because Chicken Scheme assumes that the division operator / indicates a floating-point number.
In Python.
# ternary number is represented by list of numbers {-1,0,1} # with a value of sum( list[0]*3**0, list[1]*3**1, list[2]*3**2, list[3]*3**3 ) # ! Thus, these methods use a left to right representation.. ! def int_to_ternary(n): def recursive(n): if n == 0: return [] if (n % 3) == 0: return [0] + recursive(n // 3) if (n % 3) == 1: return [1] + recursive(n // 3) if (n % 3) == 2: return [-1] + recursive((n + 1) // 3) return recursive(n) def ternary_to_int(t): result = 0 for exp, v in enumerate(t): result += (3**exp)*v return result def negate_ternary(t): return map((lambda x: x*-1), t) def add_ternaries_using_convert(t1,t2): return int_to_ternary(ternary_to_int(t1) + ternary_to_int(t2)) def add_ternaries_with_carry(t1,t2): # pad the longest ternary with 0's if t1 > t2: t1,t2 = t2,t1 if t2 > t1: t1 = t1 + [0]*(len(t2)-len(t1)) result = [0]*len(t1) carry = 0 for i in range(len(t1)): s = t1[i] + t2[i] + carry # print i, '|', t1[i],t2[i] , carry, s if s == 2: result[i] = -1 carry = 1 elif s == 3: result[i] == 0 carry = 1 elif s == -2: result[i] = 1 carry = -1 elif s == -3: result[i] == 0 carry = -1 else: result[i] = s carry = 0 if carry != 0: result.append(carry) return result if __name__ == "__main__": # ints to ternary assert int_to_ternary(18) == [0, 0, -1, 1] assert int_to_ternary(-47) == [1, -1, 1, 1, -1] assert int_to_ternary(18-47) == [1, -1, 0, -1] # 18-47 == -29 # identy check assert ternary_to_int(int_to_ternary(492366097)) == 492366097 # test negate assert ternary_to_int(negate_ternary(int_to_ternary(18))) == -18 # test add using convert assert ternary_to_int(add_ternaries_using_convert(int_to_ternary(18), int_to_ternary(-47))) == -29 # test add using addition table assert ternary_to_int(add_ternaries_with_carry( int_to_ternary(18), int_to_ternary(-47))) == -29We can do this in a similar way to the previous problem, here most of the work is done by the “adjust” function which puts a single digit into the correct range and adjusts the carry accordingly. I’ve added a separate “normalize” function, and we can simplify addition assuming the inputs are normalized:
#include <stdio.h> #include <stdlib.h> int value(int *a, int n) { int t = 0; for (int i = n; i > 0; i--) { t = 3*t + a[i-1]; } return t; } void show(int *a, int n) { bool started = false; for (int i = n; i > 0; i--) { if (a[i-1]) started = true; if (started) printf("%c", "-0+"[1+a[i-1]]); } if (!started) printf("0"); printf(": %d\n", value(a,n)); } // Adjust digit d to be in the correct range // Carry k is modified correspondingly int adjust(int d, int &k) { if (d > 1) { d -= 3; k += 1; } else if (d < -1) { d += 3; k -= 1; } return d; } void normalize(int *a, int n) { for (int k = 0, i = 0; i<n; i++) { int d = a[i]+k; k = d/3; a[i] = adjust(d%3,k); } } void add(int *a, const int *b, int n) { for (int k = 0, i = 0; i<n; i++) { int d = a[i]+b[i]+k; k = 0; a[i] = adjust(d,k); } } void mult(int *c, const int *a, const int *b, int n) { for (int i = 0; i < n; i++) { for (int k = 0, j = 0; j < n; j++) { int d = a[i]*b[j]+c[i+j]+k; k = d/3; c[i+j] = adjust(d%3,k); } } } void set(int *a, int n, int t) { a[0] = t; for (int i = 1; i < n; i++) a[i] = 0; normalize(a,n); } int main() { int N = 8; int a[N], b[N]; while(true) { int a0 = rand()%2000-1000; int b0 = rand()%2000-1000; set(a,N,a0); set(b,N,b0); show(a,N); show(b,N); int c[2*N]; set(c,2*N,0); mult(c,a,b,N); show(c,2*N); if (value(c,2*N) != a0*b0) break; add(a,b,N); show(a,N); if (value(a,N) != a0+b0) break; printf("\n"); } }That mult function is wrong – it throws away the final carry from each addition. Here’s a better version (and a better test program):
void clear(int *a, int n) { for (int i = 0; i < n; i++) a[i] = 0; } int add(int *a, const int *b, int n) { int k = 0; for (int i = 0; i < n; i++) { int d = a[i]+b[i]+k; k = 0; a[i] = adjust(d,k); } return k; } int sub(int *a, const int *b, int n) { int k = 0; for (int i = 0; i < n; i++) { int d = a[i]-b[i]+k; k = 0; a[i] = adjust(d,k); } return k; } void mult(int *c, const int *a, const int *b, int n) { clear(c,2*n); for (int i = 0; i < n; i++) { if (a[i] == 1) { c[i+n] = add(c+i,b,n); } else if (a[i] == -1) { c[i+n] = sub(c+i,b,n); } } } int main() { int N = 8; int a[N], b[N], c[2*N]; int max = 3280; // (3^N-1)/2 for (int i = -max; i <= max; i++) { for (int j = -max; j <= max; j++) { set(a,N,i); set(b,N,j); mult(c,a,b,N); assert(value(c,2*N) == i*j); int k = add(a,b,N); assert(value(a,N)+k*6561 == i+j); sub(a,b,N); assert(value(a,N) == i); } } }See this web site for a library of C (works in C++ too) code allowing use of binary-coded ternary data representations, coding each ternary trit as two consecutive binary bits.
— http://www.cs.uiowa.edu/~jones/ternary/libtern.shtml
This does a ternary add in about 10 times the time it takes for a corresponding integer add, so it’s way more efficient than the digit serial code shown above. There’s support there for both balanced ternary (trit values -1 0 +1) and unsigned ternary (trit values 0 1 2).