# 2017q3 Homework1 (ternary)
contributed by <`LinRiver`>

## Balanced Ternary 簡介

Balanced Ternary (中文稱「平衡三進位」)是以 -1(或T), 0, 1 作為數值計算系統。在不同情形下會使用 -，0，+ 表示。相較於其他數值系統(如二進位或十進位)，Balanced Ternary 無需額外位元表示正負號即可所有整數系呈現。

除此之外， base-b 之 single digit 擁有 $log_{2}b$ bits 的資訊。base-3 之 single digit 擁有 $log_{2}3$ 資訊，亦是 base-2 的 1.58 倍。

base-3 數值系統之邏輯狀態分為 true ， unknown ， false。 如下表格整理所示：

| true value | unsigned | balanced |
| -------- | -------- | -------- |
| $false$ | 0 | - |
| $unknown$ | 1 | 0 |
| $true$ | 2 | + |

> TODO: 詳細閱讀 [Fast Ternary Addition](http://homepage.divms.uiowa.edu/~jones/ternary/arith.shtml)，理解 base-3 的原理 (並且複習數位邏輯)，整理 base-3 基礎運算操作
> [name="jserv"][color=red]

## Balanced Ternary 運算
### 一般性表示法
$(a_{n}a_{n-1}...a_{1}a_{0}.c_{1}c_{2}c_{3}...)_{3}=\sum\limits_{i=1}^{n}a_{k}3^{k}+\sum\limits_{k=1}^{\infty}c_{k}3^{k}$，其中:

* $a_{n}a_{n-1}...a_{1}a_{0}.c_{1}c_{2}c_{3}...$為在 Balanced Ternary 之表示
* $a_{k}$ 或 $c_{k}$ 為第 k 個位元所對應之係數

> 請閱讀 [Ternary computing: basics](https://github.com/ssloy/tutorials/wiki/Ternary-computing:-basics)，關注於 ternary multiplexer, Unary functions, half-adder, Consensus, full adder, Overflow
> [name="jserv][color=blue]

>謝謝老師指導!
>[name=LinRiver][color=blue]

### 邏輯運算
**AND**
| | false | unknown | true |
| ------- | ----- | ------- | ------- |
| **false** | false | false | false |
| **unknown** | false | unknown | unknown |
| **true** | false | unknown | true |

**OR**
| | false | unknown | true |
| ------- | ------- | ------- | ---- |
| **false** | false | unknown | true |
| **unknown** | unknown | unknown | true |
| **true** | true | true | true |

**NOT**
| original | NOT |
| -------- | ------- |
| **false** | true |
| **unknown** | unknown |
| **true** | false |

以上運算不特別使用數值表示法，而是將真實狀態進行邏輯運算，所以 unsigned 或是 balanced ternary 皆適用。透過真實狀態呈現，可以清楚知道 unknown 狀態如何與其他狀態執行邏輯運算。

### 數值運算

## Balanced Ternary 優勢

### 數值呈現
相較於二進位數值系統，
* 可用較少位元呈現相同數值，例如$16_{dec}=1TT1_{bal3}=10000_{bin}$
* 相同位元數 n 下可涵蓋更多正負數值呈現，從 $-3^{n-1}$ 到 $3^{n-1}-1$

> 繼續研讀 [What is the most efficient numerical base system?](https://math.stackexchange.com/questions/446664/what-is-the-most-efficient-numerical-base-system)，並依據裡頭的分析，量化上述討論
> [name="jserv"][color=red]

>謝謝老師的資料!
>[name=LinRiver][color=blue]

### 經濟效率呈現

首先上圖是探討 radix economy 之經濟效率呈現。
* 可以清楚看到當 radix$(e)$ 時，在 五個不同的 radix$\times$width$(rw)$ 表現上皆為最低值呈現，其經濟效益最高。
* 探討 radix economy 是綜合考量了進制的數值和位元數的多寡的量化方式，其精準定義為：
* $E(b, N)=b \times (log_{b}N ＋ 1)$ ，其中 $b$ 為進制數值而 $N$ 為所欲表示之數值。
* 針對 radix economy 精準定義後，其後探討在 $b$ 為多少時可得到 $E(B, N)$ 為最小。
* 首先將 $b$ 從離散區間擴展成連續區間，將整體量化分析視為連續函數的極值問題。
* 將此連續函數 $E(b, N)=b \times (log_{b}N ＋ 1)$ 近似為 $E(b, N)=b \times log_{b}N=(b/log_{e}b) \times log_{e}N$ ，進行一階導數定理求其臨界點和二階導數定理判斷凹口方向。
* 一階導數定理: $E(b, N)'=(log_{e}N \times (log_{e}b-1)) / (log_{e}b)^2=0$ (令其為$0$)，明顯可得到 $b=e$。
* 二階導數定理: $E(b=e,N)''<0$ (二階函數圖形凹口向上)，確立當 $b=e$ 時其 radix economy 的 E(e,N) 有最大值。

對於 $b=e$ 時會有最大經濟效益下，在進制數值上我們選擇 $b=3$ 。然而我將此問題進一步思考，會選擇 $b=3$ 還有那些特殊數值? 顯然是 $\pi=3.1415926...$ ，目前仍持續研究。

## 參考資料
[Fast Ternary Addition](http://homepage.divms.uiowa.edu/~jones/ternary/arith.shtml)
[Wikipedia: Balanced ternary](https://en.wikipedia.org/wiki/Balanced_ternary)
[c2 wiki](http://wiki.c2.com/?ThreeValuedLogic)
[st9007a共筆](https://hackmd.io/AwFgrAxgZgphCGBaAbADgEYkSAnFAjIvFMjogMyoDsAJshBPsgEzkxA=?both)
[What is the most efficient numerical base system?](https://math.stackexchange.com/questions/446664/what-is-the-most-efficient-numerical-base-system)
[三生萬物](http://www.global-sci.org/mc/issues/5/no4/freepdf/79s.pdf)