⍝   B a l a n c e d   T e r n a r y   A r i t h m e t i c

⍝ "Perhaps the prettiest number system of all." D.E.Knuth.      See →notes.bta←

⍝ function definitions:

    ← .()           ⍝ ternary digit binding:   8 → 1.0.¯1

      -()           ⍝ neg
    → ∧()           ⍝ pow
    ← *() /() %()   ⍝ mul div mod
    ← +() -()       ⍝ add sub

⍝ Pattern matching variables.

    i j :: ¯1 0 1   ⍝ single digits.
    p q ::
    r s ::

⍝ trim / carry

           0.i  =  i
       p.(i.j)  =  (p+i).j

⍝ negate
         -  ¯1  =  1
         -   0  =  0
         -   1  = ¯1
         - p.i  = (-p).(-i)
⍝ add
         p + 0  =  p
         0 + q  =  q

         i + i  =  i.(-i)       ⍝ same: overflow
         i + j  =  0            ⍝ diff: cancel

     p.i +   j  =     p.(i+j)
       i + q.j  =     q.(i+j)
     p.i + q.j  = (p+q).(i+j)

⍝ mul
       p *  ¯1  = -p
       p *   0  =  0
       p *   1  =  p
       p * q.j  =  (p*q).0 + p*j
⍝ pow
       p ∧   0  =  1
       p ∧   1  =  p
       p ∧ q.j  =  p∧q * p∧q * p∧(q+j)
⍝ sub
          p - q = p + -q
⍝ div
          p / q = div A0; p; q; ×p; ×q

          div   q; r  =  q                              ⍝ extract quotient
          div -(q; r) = -q
⍝ mod
          p % q = mod A0; p; q; ×p; ×q

          mod   q; r  =  r                              ⍝ extract remainder
          mod -(q; r) = -r

⍝ "long division" algorithm. See →notes.Long_division←

    A0; p; q;  0;  0       =   1; 0                     ⍝ adjust signs:
    A0; p; q;  0;  j       =   0; j
    A0; p; q;  i;  0       =   ?; ?                     ⍝ div-by-zero error
    A0; p; q;  1;  1       =  (A1;  p;  q;  p;  q)      ⍝ pos / pos
    A0; p; q;  1; ¯1       =  (A1;  p; -q;  p; -q)      ⍝ pos / neg
    A0; p; q; ¯1;  1       = -(A1; -p;  q; -p;  q)      ⍝ neg / pos
    A0; p; q; ¯1; ¯1       = -(A1; -p; -q; -p; -q)      ⍝ neg / neg

    A1; p; q; r.i; s.j     = A1; p; q; r; s             ⍝ A: left align divisor
    A1; p; q;   r;   j     = A2; p; q; |; r             ⍝ reset shift mechanism
    A1; p; q;   i; s       = A2; p; q; |; i

    A2; p; q; s; r.i       = A2; p; q.0; s.<; r         ⍝ shift divisor & count
    A2; p; q; s;   i       = B1; p; q.0; s.<; 0         ⍝ s+1 shifted divisor q

    B1; p; q; s; r         = B2; p; q; s; r; ×p-q       ⍝ B1: subtract

    B2; p; q.j; s.<; r;  1 = B1; p-q.j; q.j; s.<; r+1   ⍝ increment quotient
    B2; p; q.j; s.<; r;  0 =     r+1;   0               ⍝ 0 remainder: finished
    B2; p; q.j; s.<; r; ¯1 = B1; p;     q;   s;   r.0   ⍝ underflow: unshift

    B2; p; q;   |;   r;  1 = B1; p-q;   q;   |;   r+1   ⍝ q unshifted: finished
    B2; p; q;   |;   r;  0 =     r+1;   0
    B2; p; q;   |;   r; ¯1 =     r;     p

⍝ (low precedence) auxiliary functions

    ×()                         ⍝ signum:
    ×   i =   i                 ⍝   sign of number is,
    × p.i = × p                 ⍝   sign of most sig dig.

    ← ;()                       ⍝ division state item separator
    div() mod()                 ⍝ division result separation
    ← =()   ≡()                 ⍝ reduction equivalence/trace

⍝ Test cases:
⍝
⍝   1.1+1.1      ->  1.0.¯1                     ⍝ 4+4 → 8
⍝  ¯1.¯1+¯1.¯1   ->  ¯1.0.1                     ⍝ ¯4+¯4 → ¯8
⍝   1.1-1.1      ->  0                          ⍝ 4-4 → 0
⍝  -1.1.1        -> ¯1.¯1.¯1                    ⍝ -13 → ¯13
⍝   1.1.1*1.1.1  ->  1.¯1.0.1.¯1.1              ⍝ 13×13 → 169
⍝  ¯1.1∧1.0      -> ¯1.0.1                      ⍝ ¯2*3 → ¯8
⍝   1.1∧1.0.¯1   ->  1.0.1.0.0.0.¯1.0.1.¯1.1    ⍝ 4∧8 → 65536
⍝   1.0. 1/1.¯1  ->  1.¯1.¯1                    ⍝ 10÷2 → 5
⍝  ¯1.0.¯1/1.¯1  -> ¯1.1.1                      ⍝ ¯10÷2 → ¯5
⍝   1.1.1%1.0.¯1 ->  1.¯1.¯1                    ⍝ 13|⍨8 → 5
⍝   0/0          ->  1                          ⍝ 0÷0 → 1
⍝   1/0          ->  ?                          ⍝ 1÷0 → error
⍝   
⍝   Back to: Contents