# Balanced ternary

*is a*

**Balanced ternary****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^{2} + 3^{1} − 3^{0}, thus can be written as "++−", while 6 = 3^{2} − 3^{1} + 0 × 3^{0}, i.e., "+−0".

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

**Requirements**

- Support arbitrarily large integers, both positive and negative;
- 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).
- 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. - Provide ways to perform addition, negation and multiplication directly on balanced ternary integers; do
*not*convert to native integers first. - 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)

(nreverse (map 'list

#'(lambda (c) (case c (#\+ 1) (#\- -1) (#\0 0))) (coerce s 'list))))

- convert ternary to string

(defun bt-string (bt)

(if (not bt) "0" (let ((s (make-array (length bt) :element-type 'character

:adjustable t :fill-pointer 0)))

(mapc (lambda (b) (vector-push-extend

(case b (-1 #\-) (0 #\0) (1 #\+)) s)) (reverse 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 (or a b (not (zerop c)))) nil (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 >.@(-~/"1)@:^. 1.5,.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 values are limited to 1, 0, and -1. The polynomial will always use powers of 3.

`trigits`

computes the number of trinary "digits" (that is, the number of polynomial coefficients) needed to represent an integer.

foo`Of`

Bar converts a bar into a foo

`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,' ',":@nOfTrin) a mul b (add -) c

0+--0++0 _262023</lang>