## 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)
(let ((ts (ternary (+ x y c))))
(if (null? (cdr ts))
(values 0 (car 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.

Pages: 1 2

### 4 Responses to “Balanced Ternary Arithmetic”

1. Rutger said

In Python.

```# ternary number is represented by list of numbers {-1,0,1}
# with a value of sum(  list*3**0, list*3**1, list*3**2, list*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  + recursive(n // 3)
if (n % 3) == 1:
return  + 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)

return int_to_ternary(ternary_to_int(t1) + ternary_to_int(t2))

# pad the longest ternary with 0's
if t1 > t2:
t1,t2 = t2,t1
if t2 > t1:
t1 = t1 + *(len(t2)-len(t1))

result = *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
assert ternary_to_int(add_ternaries_with_carry( int_to_ternary(18), int_to_ternary(-47))) == -29

```
2. matthew said

We 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;
}
}

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;
}
}

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;
}
}
}

void set(int *a, int n, int t) {
a = 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;
show(a,N);
if (value(a,N) != a0+b0) break;
printf("\n");
}
}
```
3. matthew said

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;
}
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;
}
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) {
} 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);