2017q3 Homework1 (ternary)

contributed by <LinRiver>

Balanced Ternary 簡介

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

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

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

TODO: 詳細閱讀 Fast Ternary Addition，理解 base-3 的原理 (並且複習數位邏輯)，整理 base-3 基礎運算操作
"jserv"

$(a_{n} a_{n - 1} . . . a_{1} a_{0} . c_{1} c_{2} c_{3} . . .)_{3} = \sum_{i = 1}^{n} a_{k} 3^{k} + \sum_{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，關注於 ternary multiplexer, Unary functions, half-adder, Consensus, full adder, Overflow
"jserv

謝謝老師指導!
LinRiver

AND

NOT

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

相較於二進位數值系統，

繼續研讀 What is the most efficient numerical base system?，並依據裡頭的分析，量化上述討論
"jserv"

謝謝老師的資料!
LinRiver

Image Not Showing Possible Reasons

首先上圖是探討 radix economy 之經濟效率呈現。

可以清楚看到當 radix $(e)$ 時，在五個不同的 radix $\times$ width $(r w)$ 表現上皆為最低值呈現，其經濟效益最高。
探討 radix economy 是綜合考量了進制的數值和位元數的多寡的量化方式，其精準定義為：
- $E (b, N) = b \times (l o g_{b} N ＋ 1)$ ，其中 $b$ 為進制數值而 $N$ 為所欲表示之數值。
針對 radix economy 精準定義後，其後探討在 $b$ 為多少時可得到 $E (B, N)$ 為最小。
- 首先將 $b$ 從離散區間擴展成連續區間，將整體量化分析視為連續函數的極值問題。
- 將此連續函數 $E (b, N) = b \times (l o g_{b} N ＋ 1)$ 近似為 $E (b, N) = b \times l o g_{b} N = (b / l o g_{e} b) \times l o g_{e} N$ ，進行一階導數定理求其臨界點和二階導數定理判斷凹口方向。
- 一階導數定理: $E (b, N)^{'} = (l o g_{e} N \times (l o g_{e} b - 1)) / (l o g_{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$ 還有那些特殊數值? 顯然是 $π = 3.1415926 . . .$ ，目前仍持續研究。