Balanced ternary

Balanced ternary is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Balanced ternary is a way of representing numbers. Unlike the prevailing binary representation, a balanced ternary integer is in base 3, and each digit can have the values 1, 0, or −1. For example, decimal 11 = 3² + 3¹ − 3⁰, thus can be written as "++−", while 6 = 3² − 3¹ + 0 × 3⁰, i.e., "+−0".

For this task, implement balanced ternary representation of integers with the following

Requirements

1. Support arbitrarily large integers, both positive and negative;
2. Provide ways to convert to and from text strings, using digits '+', '-' and '0' (unless you are already using strings to represent balanced ternary; but see requirement 5).
3. Provide ways to convert to and from native integer type (unless, improbably, your platform's native integer type is balanced ternary). If your native integers can't support arbitrary length, overflows during conversion must be indicated.
4. Provide ways to perform addition, negation and multiplication directly on balanced ternary integers; do not convert to native integers first.
5. Make your implementation efficient, with a reasonable definition of "effcient" (and with a reasonable definition of "reasonable").

Test case With balanced ternaries a from string "+-0++0+", b from native integer -436, c "+-++-":

• write out a, b and c in decimal notation;
• calculate a × (b − c), write out the result in both ternary and decimal notations.

Common Lisp

<lang lisp>;;; balanced ternary

represented as a list of 0, 1 or -1s, with least significant digit first

convert ternary to integer

(defun bt-integer (b)

 (if (not b) 0
   (+ (car b) (* 3 (bt-integer (cdr b))))))

convert integer to ternary

(defun integer-bt (n)

 (if (zerop n) nil
   (case (mod n 3)
     (0 (cons  0 (integer-bt (/ n 3))))
     (1 (cons  1 (integer-bt (floor n 3))))
     (2 (cons -1 (integer-bt (floor (1+ n) 3)))))))

convert string to ternary

(defun string-bt (s)

 (loop with o = nil for c across s do

(setf o (cons (case c (#\+ 1) (#\- -1) (#\0 0)) o)) finally (return o)))

convert ternary to string

(defun bt-string (bt)

 (if (not bt) "0"
   (let* ((l (length bt))

(s (make-array l :element-type 'character)))

     (mapc (lambda (b)

(setf (aref s (decf l)) (case b (-1 #\-) (0 #\0) (1 #\+)))) bt)

     s)))

arithmetics

(defun bt-neg (a) (map 'list #'- a)) (defun bt-sub (a b) (bt-add a (bt-neg b)))

(let ((tbl #((0 -1) (1 -1) (-1 0) (0 0) (1 0) (-1 1) (0 1))))

 (defun bt-add-digits (a b c)
   (values-list (aref tbl (+ 3 a b c)))))

(defun bt-add (a b &optional (c 0))

 (if (not (and a b))
   (if (zerop c) (or a b)
     (bt-add (list c) (or a b)))
   (multiple-value-bind (d c)
     (bt-add-digits (if a (car a) 0) (if b (car b) 0) c)
     (let ((res (bt-add (cdr a) (cdr b) c)))

;; trim leading zeros (if (or res (not (zerop d))) (cons d res))))))

(defun bt-mul (a b)

 (if (not (and a b))
   nil
   (bt-add (case (car a)

(-1 (bt-neg b)) ( 0 nil) ( 1 b)) (cons 0 (bt-mul (cdr a) b)))))

division with quotient/remainder, for completeness

(defun bt-truncate (a b)

 (let ((n (- (length a) (length b)))

(d (car (last b))))

   (if (minusp n)
     (values nil a)
     (labels ((recur (a b x)

(multiple-value-bind (quo rem) (if (plusp x) (recur a (cons 0 b) (1- x)) (values nil a))

(loop with g = (car (last rem)) with quo = (cons 0 quo) while (= (length rem) (length b)) do (cond ((= g d) (setf rem (bt-sub rem b) quo (bt-add '(1) quo))) ((= g (- d)) (setf rem (bt-add rem b) quo (bt-add '(-1) quo)))) (setf x (car (last rem))) finally (return (values quo rem))))))

(recur a b n)))))

test case

(let* ((a (string-bt "+-0++0+"))

      (b (integer-bt -436))
      (c (string-bt "+-++-"))
      (d (bt-mul a (bt-sub b c))))
 (format t "a~5d~8t~a~%b~5d~8t~a~%c~5d~8t~a~%a × (b − c) = ~d ~a~%"

(bt-integer a) (bt-string a) (bt-integer b) (bt-string b) (bt-integer c) (bt-string c) (bt-integer d) (bt-string d)))</lang>output<lang>a 523 +-0++0+ b -436 -++-0-- c 65 +-++- a × (b − c) = -262023 ----0+--0++0</lang>

J

Implementation:

<lang j>trigits=: 1+3 <.@^. 2 * 1&>.@| trinOfN=: |.@((_1 + ] #: #.&1@] + [) #&3@trigits) :. nOfTrin nOfTrin=: p.&3 :. trinOfN trinOfStr=: 0 1 _1 {~ '0+-'&i.@|. :. strOfTrin strOfTrin=: {&'0+-'@|. :. trinOfStr

carry=: +//.@:(trinOfN"0)^:_ trimLead0=: (}.~ i.&1@:~:&0)&.|.

add=: carry@(+/@,:) neg=: - mul=: trimLead0@carry@(+//.@(*/))</lang>

trinary numbers are represented as a sequence of polynomial coefficients. The coefficient values are limited to 1, 0, and -1. The polynomial's "variable" will always be 3 (which happens to illustrate an interesting absurdity in the terminology we use to describe polynomials -- one which might be an obstacle for learning, for some people).

trigits computes the number of trinary "digits" (that is, the number of polynomial coefficients) needed to represent an integer. pseudocode: 1+floor(log3(2*max(1,abs(n))). Note that floating point inaccuracies combined with comparison tolerance may lead to a [harmless] leading zero when converting incredibly large numbers.

fooOfBar converts a bar into a foo. These functions are all invertable (so we can map from one domain to another, perform an operation, and map back using J's under). This aspect is not needed for this task and the definitions could be made simpler by removing it (removing the :. obverse clauses), but it made testing and debugging easier.

carry performs carry propagation. (Intermediate results will have overflowed trinary representation and become regular integers, so we convert them back into trinary and then perform a polynomial sum, repeating until the result is the same as the argument.)

trimLead0 removes leading zeros from a sequence of polynomial coefficients.

add adds these polynomials. neg negates these polynomials. Note that it's just a name for J's - mul multiplies these polynomials.

Definitions for example:

<lang j>a=: trinOfStr '+-0++0+' b=: trinOfN -436 c=: trinOfStr '+-++-'</lang>

Required example:

<lang j> nOfTrin&> a;b;c 523 _436 65

  strOfTrin a mul b (add -) c

---

0+--0++0

  nOfTrin   a mul b (add -) c

_262023</lang>

Ruby

<lang ruby>class BalancedTernary

 def initialize(str = "")
   if str !~ /^[-+0]+$/
     raise ArgumentError, "invalid BalancedTernary number: #{str}"
   end
   @digits = trim0(str)
 end

 def self.from_int(value)
   n = value
   digits = ""
   while n != 0
     quo, rem = n.divmod(3)
     case rem
     when 0
       digits = "0" + digits
       n = quo
     when 1
       digits = "+" + digits
       n = quo
     when 2
       digits = "-" + digits
       n = quo + 1
     end
   end
   new(digits)
 end

 def to_int
   @digits.chars.inject(0) do |sum, char|
     sum *= 3
     case char
     when "+"
       sum += 1
     when "-"
       sum -= 1
     end
     sum
   end
 end
 alias :to_i :to_int

 def to_s
   @digits
 end
 alias :inspect :to_s

 ADDITION_TABLE = {
   "-" => {"-" => ["-","+"], "0" => ["0","-"], "+" => ["0","0"]},
   "0" => {"-" => ["0","-"], "0" => ["0","0"], "+" => ["0","+"]},
   "+" => {"-" => ["0","0"], "0" => ["0","+"], "+" => ["+","-"]},
 }

 def +(other)
   maxl = [to_s, other.to_s].collect {|s| s.length}.max
   a = pad0(to_s, maxl)
   b = pad0(other.to_s, maxl)
   carry = "0"
   sum = a.reverse.chars.zip( b.reverse.chars ).inject("") do |sum, (c1, c2)|
     carry1, digit1 = ADDITION_TABLE[c1][c2]
     carry2, digit2 = ADDITION_TABLE[carry][digit1]
     sum = digit2 + sum
     carry = ADDITION_TABLE[carry1][carry2][1]
     sum
   end
   self.class.new(carry + sum)
 end

 MULTIPLICATION_TABLE = {
   "-" => {"-" => "+", "0" => "0", "+" => "-"},
   "0" => {"-" => "0", "0" => "0", "+" => "0"},
   "+" => {"-" => "-", "0" => "0", "+" => "+"},
 }

 def *(other)
   product = self.class.new("0")
   other.to_s.chars.each do |bdigit|
     row = to_s.chars.collect {|adigit| MULTIPLICATION_TABLE[adigit][bdigit] }.
       join
     product += self.class.new(row)
     product << 1
   end
   product >> 1
 end

 # negation
 def -@()
   self * BalancedTernary.new("-")
 end

 # subtraction
 def -(other)
   self + (-other)
 end

 # shift left
 def <<(count)
   @digits = trim0(@digits + "0"*count)
   self
 end

 # shift right
 def >>(count)
   @digits[-count..-1] = "" if count > 0
   @digits = trim0(@digits)
   self
 end

 private

 def trim0(str)
   str.sub!(/^0+/, "")
   str = "0" if str.empty?
   str
 end

 def pad0(str, len)
   str.rjust(len, "0")
 end

end

a = BalancedTernary.new("+-0++0+") b = BalancedTernary.from_int(-436) c = BalancedTernary.new("+-++-") calc = a * (b - c) puts "%s\t%d\t%s\n" % ['a', a.to_i, a] puts "%s\t%d\t%s\n" % ['b', b.to_i, b] puts "%s\t%d\t%s\n" % ['c', c.to_i, c] puts "%s\t%d\t%s\n" % ['a*(b-c)', calc.to_i, calc]</lang>

output

a       523     +-0++0+
b       -436    -++-0--
c       65      +-++-
a*(b-c) -262023 ----0+--0++0