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)

 (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)))))

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>