# 2017q3 Homework1 (ternary)
contributed by<`zhanyangch`>
###### tags:`sysprog2017`
> TODO: 詳細閱讀 [Fast Ternary Addition](http://homepage.divms.uiowa.edu/~jones/ternary/arith.shtml)，理解 base-3 的原理 (並且複習數位邏輯)，整理 base-3 基礎運算操作
> [name="jserv"][color=red]
---
### Review by `williamchangTW`
- 根據電路的分析應該可以得出相關好處，比如運算較快或其餘能推導出來的想法
- 了解三位元的好處後，可以順利的把接下來的作業完成，電路分析的還滿詳細，受教了
>小弟坐井觀天，如有冒犯請見諒[name="williamchangTW"]
---
## Ternary 介紹
Ternary 以三為底，每個 ternary digit(trit) 有三個符號表示 0,1,2 ，Balanced Ternary 則是 +,0,- 或 1,0,T，一個無號整數 N，可以用 log~3~(N+1)(無條件進位) 位三進位表示，與二進位需要 log~2~(N+1) 相比，三進位只須 log~3~N/log~2~N(0.63) 倍的位數，除了用來代表數字以外，也對應的 Kleene logic
|truth value|unsigned|balanced|
|:---------:|:------:|:------:|
|false(F)|0|-|
|unknown(U)|1|0|
|true(T)|2|+|
Kleene logic 運算，參考 [Three-valued logic(wikipedia)](https://en.wikipedia.org/wiki/Three-valued_logic)
**NOT(A)：¬A**
|A|¬A|
|-|--|
|F|T|
|U|U|
|T|F|
**AND(A,B)：A∧B**
|A\B|F|U|T|
|:-:|:-:|:-:|:-:|
|**F**|F|F|F|
|**U**|F|U|U|
|**T**|F|U|T|
**OR(A,B)：A∨B**
|A\B|F|U|T|
|:-:|:-:|:-:|:-:|
|**F**|F|U|T|
|**U**|U|U|T|
|**T**|T|T|T|
## b3k 程式
* 下載及編譯
```shell
$ git clone https://github.com/sysprog21/balanced-ternary
$ cd balanced-ternary
$ make
```
> 作業要求頁面已更新，請注意。重新 `git clone` 並依據裡頭的程式碼，對下方程式碼做對應的縮排 (4 個空白，而不是 tab)
> [name="jserv"][color=red]
> >以修正
> >[name="zhanyangch"][color=#907bf7]
* digit 的數量為8，可表示的數為 -3280~3280
$3280= \dfrac {1(3^8-1)}{3-1}$
```clike
p = &digit[SZD - 1];
r = 3 * p->exp / 2;
if (src > r)
src = r;
else
r = src;
```
* 此段為十進位轉為三進位 (Ternary)，以減法代替除法，注意 `++p->val` 的運算順序是 `++(p->val)`
```clike
// Like 'echo "obase=3; $src" | bc'.
do {
while (r < p->exp)
--p;
r -= p->exp;
++p->val;
} while (r);
```
* 加入一段程式碼查看三進位的輸出
```clike
for(p = &digit[SZD-1]; p >= &digit[0]; --p)
printf("%d",p->val);
printf("\n");
```
```shell
$ echo 25 | ./b3k
00000221
├───┐
│ │
└┴┬─┘
```
$25=(2\times3^2 + 2\times3^1 +1\times3^0)$
* 轉換成 Balanced Ternary，當 val 為 2 將其轉換為 1T (在此 T 表是-，與減號區別，與老師上課講義的表示法稍有不同)，並且將正負號補上。
$3^k \times 2=3^{k+1}-3^k$
例如：
$\begin{split}25_{dec}&=221_{3}\\&= 1T00_{bal3}+1T0_{bal3}+1_{bal3}\\&=10T1_{bal3}\\25_{dec}&= 3^3+(-1)\times3^1+1 \end{split}$
```clike
// Convert to the balanced form.
while (p < &digit[SZD]) {
if (r)
++p->val;
r = p->val > 1;
if (r)
p->val -= 3;
p->val *= inv;
++p;
}
```
## 運算
> 請閱讀 [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]
* balance teneray multiplexer
當 sel 分別是 -1,0,1 時輸出為 inN,inO,inP
* 如果將 sel 設為 A 則可以得到幾個跟 A 有關的 unary functions
* half-adder ：首先算出 A,A+1,A-1 的值，利用 B 作為 multiplexer 的 sel
|B|-1|0|1|
|:-:|:-:|:-:|:-:|
|**S**|A-1|A|A+1|
**A+B**
|A\B|-1|0|1|
|:-:|:-:|:-:|:-:|
|**-1**|1|-1|0|
|**0**|-1|0|1|
|**1**|0|1|-1|
* 進位則是當 A,B 為(1,1)時 C為-1，A,B 為(-1,-1)時時 C為1
|B|-1|0|1|
|:-:|:-:|:-:|:-:|
|**C**|min(A,0)|0|max(A,0)|
* full adder:利用上面的半加器算出 A+B-1,A+B,A+B+1 後，由 Cin 決定 S
* A+B-1 可以先計算出 A-1 對 B 相加的真值表inN,inO,inP的順序即可，A+B+1亦同。
**(A-1)+B**
|B|-1|0|1|
|:-:|:-:|:-:|:-:|
|**A+B-1**|A+1|A-1|A|
**(A+1)+B**
|B|-1|0|1|
|:-:|:-:|:-:|:-:|
|**A+B+1**|A|A+1|A-1|
*Cout:比較難直接看懂，用 Cin 回推各種情形
Cin:0 與半加器相同
Cin:1,A+B>0 Cout:1
Cin:1,A+B<0 Cout:0
Cin:-1,A+B>0 Cout:0
Cin:-1,A+B<0 Cout:1
Sign in with Wallet
Connect another wallet