;; balanced ternary notation (see ~/doc/ternary)
;;
;; "Perhaps the prettiest number system of all," writes Donald
;; E. Knuth in The Art of Computer Programming, "is the balanced
;; ternary notation." As in ordinary ternary numbers, the digits of a
;; balanced ternary numeral are coefficients of powers of 3, but
;; instead of coming from the set {0, 1, 2}, the digits are -1, 0 and
;; 1. They are "balanced" because they are arranged symmetrically
;; about zero. For notational convenience the negative digits are
;; usually written with a vinculum, or overbar, instead of a prefixed
;; minus sign, thus: I (imagine a 1 with an overbar here, we'll use N)
;;
;; As an example, the decimal number 19 is written 1N01 in balanced
;; ternary, and this numeral is interpreted as follows:
;;
;; 1 x 3^3 - 1 x 3^2 + 0 x 3^1 + 1 x 3^0,
;;
;; or in other words 27 - 9 + 0 + 1. Every number, both positive and
;; negative, can be represented in this scheme, and each number has
;; only one such representation. The balanced ternary counting
;; sequence begins: 0, 1, 1N, 10, 11, 1NN, 1N0, 1N1. Going in the
;; opposite direction, the first few negative numbers are N, N1, N0,
;; NN, N11, N10, N1N. Note that negative values are easy to recognize
;; because the leading trit is always negative.
;;
;; What makes balanced ternary so pretty? It is a notation in which
;; everything seems easy. Positive and negative numbers are united in
;; one system, without the bother of separate sign bits. Arithmetic is
;; nearly as simple as it is with binary numbers; in particular, the
;; multiplication table is trivial. Addition and subtraction are
;; essentially the same operation: Just negate one number and then
;; add. Negation itself is also effortless: Change every N into a 1,
;; and vice versa. Rounding is mere truncation: Setting the
;; least-significant trits to 0 automatically rounds to the closest
;; power of 3.
;;
;; The best-known application of balanced ternary notation is in
;; mathematical puzzles that have to do with weighing. Given a two-pan
;; balance, you are asked to weigh a coin known to have some integral
;; weight between 1 gram and 40 grams. How many measuring weights do
;; you need? A hasty answer would be six weights of 1, 2, 4, 8, 16 and
;; 32 grams. If the coin must go in one pan and all the measuring
;; weights in the other, you can't do better than such a powers-of-2
;; solution. If the weights can go in either pan, however, there's a
;; ternary trick that works with just four weights: 1, 3, 9 and 27
;; grams. For instance, a coin of 35 grams?110 in signed ternary?will
;; balance on the scale when weights of 27 grams and 9 grams are
;; placed in the pan opposite the coin and a weight of 1 gram lies in
;; the same pan as the coin. Every coin up to 40 grams can be weighed
;; in this way. (So can all helium balloons weighing no less than ?40
;; grams.)
;;
;; James Allwright, who maintains a Web site promoting balanced
;; ternary notation, suggests a monetary system based on the same
;; principle. If both a merchant and a customer have just one bill or
;; coin in each power-of-3 denomination, they can make exact change
;; for any transaction.
;; TODO
;; possible representations for ternary numbers:
;; - string: "1N01"; list (1 -1 0 1); vector #(1 -1 0 1)
;; LSB or MSB first?
;; - how to represent fractions, e.g.
;; 0.1 = 1x3^-1 = 1/3
;; 0.N = -1x3^-1 = -1/3
;; 0.11 = 1x3^-1 + 1x3^-2 = 4/9
;; 0.NN = -1x3^-1 - 1x3^-2 = -4/9
;; 0.1N = 1x3^-1 - 1x3^-2 = 2/9
;; 0.N1 = -1x3^-1 + 1x3^-2 = -2/9
;;
;; needed functions:
;; - decimal->ternary, ternary->decimal
;; - binary->ternary, ternary->binary
;; - ternary+, ternary-, ternary*, ternary/, ternary-modulo, etcetera.
;; - (?) ternary-and, ternary-or, ternary-not, ternary-xor
;; - print-ternary
;;
;; addition tests.
;;
;; 1 1 1 1N 1N
;; 1+ 1N+ 10+ 1N+ 10+
;; ---- ---- ---- ---- ----
;; 1N 10 11 11 1NN
;;
;; from this follow the rules:
;; 1+1=N (carry 1), 1+N=0, 1+0=1, N+N=1 (carry -1 or N), N+0=N
;;
;; applying the rules:
;;
;; 1N01 19 1N01 19 1N01 19
;; 1N0+ 6+ 1N01+ 19+ N10+ -6+ (subtraction)
;; ------ ---- ------ ---- ------ ----
;; 10N1 25 111N 38 111 13
;;
;; funny: 42 decimal -> 1NNN (81-27-9-3)
(define (decimal->ternary n)
'todo)
(define (ternary->decimal n)
'todo)
(define (add-digit-verbose a b carry)
"returns a list ((+ a b) carry)"
(let ((result (+ a b carry))
(local-carry 0))
(when (> result 1)
(set! result (- result 3))
(set! local-carry 1))
(when (< result -1)
(set! result (+ result 3))
(set! local-carry -1))
(format #t "(add ~d ~d ~d) -> (~d ~d)\n" a b carry result local-carry)
(list result local-carry)))
(define (add-digit a b carry)
"returns a list ((+ a b) carry)"
(let ((result (+ a b carry)))
(cond ((> result 1) (list (- result 3) 1))
((< result -1) (list (+ result 3) -1))
(else (list result 0)))))
(define (expect actual expected)
(unless (equal? actual expected)
(format #t "~s != ~s\n" actual expected)))
(define (test-add-digit)
(expect (add-digit 0 0 0) '(0 0))
(expect (add-digit 0 1 0) '(1 0))
(expect (add-digit 1 0 0) '(1 0))
(expect (add-digit 1 1 0) '(-1 1))
(expect (add-digit 0 -1 0) '(-1 0))
(expect (add-digit -1 0 0) '(-1 0))
(expect (add-digit -1 -1 0) '(1 -1))
(expect (add-digit 1 -1 0) '(0 0))
(expect (add-digit -1 1 0) '(0 0))
'ok)
(define (normalise a b)
;; make sure a and b are lists of the same length
;; fill with 0's to the right (insignificant)
'todo)
(define (add-recursive a b)
;; FIXME generally b0rken AND expects normalised numbers
(define (add. a b carry result)
(cond ((null? a) result)
(else
(let1 r (add-digit (car a) (car b) carry)
(add. (cdr a) (cdr b) (cadr r) (append result (car r)))))))
(add. a b 0 '()))
;; stklos version (no internal defines... d'oh)
(define (add-recursive a b)
(letrec
((add.
(lambda (a b carry result)
(cond
((null? a) result)
(else
(let ((r (add-digit (car a) (car b) carry)))
;;(format #t "~S~%" r)
(add. (cdr a) (cdr b) (cadr r)
(append result (list (car r))))))))))
(add. a b 0 '())))
(define (add-iterative a b)
(let ((result '())
(carry 0)
(current 0)
(i 0)
(la (length a))
(lb (length b)))
(while (or (not (= carry 0))
(< i la)
(< i lb))
(set! current carry)
(when (< i la)
(set! current (+ current (list-ref a i))))
(when (< i lb)
(set! current (+ current (list-ref b i))))
(set! carry 0)
(when (> current 1)
(set! current (- current 3))
(set! carry 1))
(when (< current -1)
(set! current (+ current 3))
(set! carry -1))
(set! result (append result (list current)))
(set! i (+ i 1)))
result))
;; 1N01 + 1N0 = 10N1
(expect (add-iterative '(1 0 -1 1) '(0 -1 1)) '(1 -1 0 1))
;;(print (add '(1 0 -1 1) '(0 -1 1)))
;;(print (add '(0 1) '(1)))