Balanced Ternary Arithmetic

April 14, 2015

We studied mixed-radix arithmetic in a previous exercise. In today’s exercise we look at a different kind of non-standard positional notation: balanced ternary, which is a base-3 number system that uses -1, 0 and 1 as its “trits” rather than 0, 1 and 2. For instance, the number -47 is written as (-1 1 1 -1 1) in balanced ternary, which is equivalent to -34 + 33 + 32 – 31 + 30. No separate sign is needed when using balanced notation; the sign of the leading trit is the sign of the whole number.

Arithmetic on balanced ternary numbers is done using the grade-school algorithms. Addition is done right-to-left with a carry; it is easy and fun to work out the plus-table. Subtraction is done by adding the negative, which can be computed by changing the sign of every trit. Multiplication works trit-by-trit through the multiplier, shifting at each trit.

Your task is to write functions that perform arithmetic on balanced ternary integers. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

3 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[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))) == -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;
        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");
      }
    }
    
  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;
        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);
        }
      }
    }
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: