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

### 解釋 Balanced Ternary 原理
#### 先從影片著手:
* [Number Systems 3: Ternary](https://www.youtube.com/watch?v=vOyiHMa-mtQ)

* 介紹 ternary 有別於一般電腦 binary 的運算方式，利用 0，1，2來表達，影片中利用除法的機制來進行 10 進位和 ternary 的轉換：
* Example : 以 $45_{10}$ 為例(註：R 是 remainder)
$45/3 = 15 R 0$
$15/3 = 5 R 0$
$5/3 = 1 R 2$
$1/3 = 0 R 1$
以乘法驗證
$45 = 1\times3^3 + 2\times3^2+0\times3^1+0\times3^0$
* [Hackaday 10th Anniversary: Non-Binary Computing](https://www.youtube.com/watch?v=TFTK074nG_M)
* 影片介紹 balanced ternary 有趣的在於 T,0,1(或影片中-1，0，1)可延伸出電路中的 negative voltage , ground , positive voltage,有別於 binary 的 on , off
* 影片中所提到的 [Kleene logic ternary truth table](https://en.wikipedia.org/wiki/Three-valued_logic)
* T:True / F:False / U:unkown
* 正負數的轉換：
$5=3^2-3^1-3^0$ 而 $-5=-3^2+3^1+3^0$
我們會發現其實正數(1)和負數(T)只是符號的差異，因此有了下表：
參考 [balanced ternary](https://en.wikipedia.org/wiki/Balanced_ternary)

* 影片中所提到的 Sum 和 Carry

|sum| - | 0 | + |
|:-:|:-:|:-:|:-:|
| - | + | - | 0 |
| 0 | - | 0 | + |
| + | 0 | + | - |

|carry| - | 0 | + |
|:-:|:-:|:-:|:-:|
| - | - | 0 | 0 |
| 0 | 0 | 0 | 0 |
| + | 0 | 0 | + |

其實就是 [WiKi](https://en.wikipedia.org/wiki/Balanced_ternary) 中的 Addition ，只是它將 SUM 和 CARRY 寫在一起
* [參考](http://homepage.divms.uiowa.edu/~jones/ternary/arith.shtml) half adder 的例子理解這段
5+6 in decimal decimal, unsigned and balanced ternary


* 在 the modulo-3 半加法器的實現上:

* consensus function: 延伸 Boolean logic 的想法如果兩者都為 T 則 T，兩者都F則F，有 0 (unknown) 則 unknown

* sum function: 就像是普通的 sum 但特別的地方在於如果是 2 的話在 modulo 3 是 3-1(sum:-1)，而 -2 的話是 -3+1(sum:1)

* [Balanced Ternary Full Adder](https://www.youtube.com/watch?v=v7XxIjv_mUc)
* 因為 Full Adder 有三種元素要相加 A ，B ，C，因此影片列出Balanced Ternary Full Adder 可能會相加的27種情況
* [Modulo 3 Sum and Product Functions. ](https://www.youtube.com/watch?v=cgcXoCnyZhQ)
* 這部影片開頭用 binary 去實作 ternary logic output network
表格是在說明，把3進位(0,1,2)換成2進位

| F | F2 | F1 |
|:-:|:-:|:-:|
| 0 | 0 | 0 |
| 1 | 0 | 1 |
| 2 | 1 | X |
* 2 是換成 1X ，是有原因的，因為只要 F2 是 1 就可知道是 2 根本不必判斷 F1 ，而 don't care 在用 K-map 轉成邏輯式子時，不一定要圈到，所以簡化了設計

* [ Ripple Adder in Binary and Ternary Logic ](https://www.youtube.com/watch?v=TfJxAb0owj8)
* 模擬 ripple adder 在二進位和三進位的狀況，在 6-bit 情況下 31+1 時有二進位的 maximum ripple，4-bit 情況下 26+1 有三進位的 maximum ripple
* 順便想了一下 Ripple Adder 在二進位時，能藉由 Carry Lookahead 加速，那在 modulo-3 應該也能，因為我們已經知道只有 $1+1$ 其 C=1, $-1+-1$ 其 C=-1，其餘都為0

### Balanced Ternary 的設計要解決什麼類型的問題
* 先參考了一篇 [the tangle](https://iota.org/IOTA_Whitepaper.pdf)
* [ Whitepaper Circle: IOTA Tangle - Presented by Sunny Aggarwal ](https://www.youtube.com/watch?v=tYbRyVrrUDY)
* 先說明了需要的演算法
* Blockchain -> linked list
* Tangle -> DAG (= [directed acyclic graph](https://en.wikipedia.org/wiki/Directed_acyclic_graph))
* 節點發出的交易，構成了 site set of the tangle
* Its edge set is obtained in the following way:
* 當一個新交易到達，他將會批准前面兩筆交易
* these approvals are represented by directed edge
>> 目前不了為什麼是批准前面 2 筆，而不是更多
>> 猜測是 3bits 是 1bit 記目前交易arrive ， 2bit 記先前兩筆批准交易做驗證，繼續往看找答案
* 名詞解釋
* A indirectly approves B：如果沒有直接的 edge 從 A 到 B，只要有路徑的能從 A 到 B 就稱之
* genesis transaction : approved (directly or indirectly) by all other transactions
* genesis 一開始就有一個地址包含 all the tokens
* 然後他發送 tokens 去 "founder" addresses
* token 不會再其他地方被創造
* 優點：因為交易都由先前幾筆交易批准，沒有挖礦，不用支付獎勵金
* block : transaction
* 小數字 : 權重
* 大數字 : 累積權重

~~~
此圖說明
When the new transaction X comes and approves A and C , it becomes the only tip;
the cumulative weight of all other transactions increases by 3 (X 的權重)

~~~
>>文中其實有強調權重為 $3^n$ (ternary) ，但還沒看到他的好處，也還不理解為何所加的額外 X (the only tip)權重就為 3 不為 1

* 發現了三進位的一個好處 [Radix economy](https://en.wikipedia.org/wiki/Radix_economy)
公式： $E（b,N）=b ⌊ log b ⁡ ( N ) + 1 ⌋$
* 為了解說公式的含意直接舉例子，如果我們要表達 100 這個數

| |decimal | binary | ternary |
| :--------: | :--------: | :--------: | :--------:|
| b: base | 10 | 2 | 3 |
| N | 100 | 100 | 100 |
| E（b,N） | $10\times3$ | $2\times7$|$3\times5$|
* 明明都是表達 100 這個數字但如果我們用 10 進位就只需要三位數只是每個位數都有 0~9 可選擇 ，這樣一共需要 30 個 bits
* 如果是三進位表達100 -> 10201， 如此一來只要五位數 ， 每位有 0~3 可選擇，一共需要 15 bits

* wiki 的表格 ， 有一一列出不同 N 範圍的平均 E（b,N）
* 在這我們必須先了解為什麼 "e has the lowest radix economy"
* 首先利用 $E(b,N)$ 近似於 ${b\ {\log _{b}(N)}}={b{\ln(N) \over \ln(b)}}$
* ln(N) 是固定的 ，所以求 ${b \over \ln(b)}$ 的最小值
* 在 ${e \over \ln(e)}$ 有 minimum

### 在[balanced-ternary](https://github.com/sysprog21/balanced-ternary)，分析需求，進行修改
* 先研究一下程式碼
~~~c=
struct ds {
int pos, len, exp, val;
} digit[SZD] = {
{ 32, 3 },
{ 26, 6 },
{ 16, 8 },
{ 0, 6 },
{ 6, 3 },
{ 9, 7 },
{ 21, 5 },
{ 35, 7 }
};
~~~
這８組式等下會代入 *p 中,分別是　pos 和 len
~~~
我認為會分成８組是因為，每組之間轉換+SZP（42）
1 <=> 0 <=> -1

├─ <=> ┌─ <=> ┌┬

┴ <=> ─ <=> ┬

─┤ <=> ─┐ <=> ┬┐

┤ <=> │ <=> ├

├ <=> │ <=> ┤

├─ <=> └─ <=> └┴

┬ <=> ─ <=> ┴

─┤ <=> ─┘ <=> ┴┘

~~~

* 可是如果只有第 1 筆是 0，我想我會將 0 拿出迴圈外，如此一來，少做了7次判斷

~~~c=
//exp 會一直乘3,除了第1筆 r＝0
for (r = 0; r < SZD; ++r) {
p = &digit[r];
p->exp = r ? (3 * digit[r-1].exp) : 1;
p->val = 0;
}
//改寫成
p = &digit[0];
p->exp=1;
p->val = 0;

for (r = 1; r < SZD; ++r) {
p = &digit[r];
p->exp = 3 * digit[r-1].exp;
p->val = 0;
}

~~~

~~~=
(gdb) n
52 p = &digit[r];
4: r = 1
3: *p = {pos = 32, len = 3, exp = 1, val = 0}

//下一round

(gdb)
52 p = &digit[r];
4: r = 2
3: *p = {pos = 26, len = 6, exp = 3, val = 0}
...
~~~

* 如果輸入負的, inv=-1, src　變成正數
~~~c=
if (src < 0)
src *= inv = -1;
~~~

* 首先發現的問題是輸入數據沒有範圍限制，所以超過 $(3^8-1)/2$ = 3280 ,都會是正的　maximum　,甚至輸入１個很大的正數，會跑出負的　ｍaximum
~~~
3281　　　3282　　　1111111111111
├─┴─┤　　├─┴─┤　　　┌┬┬┬┐
┤ ├　　┤ ├　　　├ ┤
├─┬─┤　　├─┬─┤　　　└┴┴┴┘
~~~
* 首先看了 [limit.h 的 Library Macros](https://www.tutorialspoint.com/c_standard_library/limits_h.htm)
* 而正數有限制在 INT_MAX 為 [phone] 所以超過就 overflow 變成負數，即使有 Truncate to the largest allowed positive 也逃不掉 。

* 所以先加了限制條件
~~~ c=
int flag=1;
while(flag) {
printf(usage);
scanf("%d", &src);
if( src>=-3280 && src<=3280) {
flag=0;
}
}
~~~
* 其實它有處理超過 3280 的數，但為什麼是 r = 3 * p->exp/2 原因在於在第7（SZD-1）筆的 p->exp 是 6561 但我們可能會寫成 $（6561-1）/2$ ，其實在 int 裡 $6561/2 =（6561-1）/2=3280$

~~~ c=
/* Truncate to the largest allowed positive. */
p = &digit[SZD - 1];
r = 3 * p->exp/2;
if (src > r)
src = r;
else
r = src;
~~~
* 這段是先把它變成三進位，舉個例子：
* 如果輸入 2 ，因為比 2 小的 3 的倍數，會選這組
input : *p = {pos = 32, len = 3, exp = 1, val = 0}
這表示他沒辦法進位成 $3^1$ 所以只能變成 2 組 $3^0$，結果記在 val
output : *p = {pos = 32, len = 3, exp = 1, val = 2}

~~~ c=
/* Like 'echo "obase=3; $src" | bc'. */
do {
while (r < p->exp)
--p;
r -= p->exp;
++p->val;
} while (r);
~~~
* 這裡先說明 p < &digit[SZD] ，因為矩陣是連續記憶體空間所以可以這樣比大小
* 還有這個寫法真的很厲害 r = p->val > 1 ，比完大小後直接assign true(1) or false(0)
* 如果拿剛剛的例子來說，這邊 2 就是會被 -3 然後進位 $3^1-1$ 記錄成：
~~~
*p = {pos = 32, len = 3, exp = 1, val = -1}
*p = {pos = 26, len = 6, exp = 3, val = 1}
~~~
* $3\times1+1\times-1$ : 原來是 exp $\times$ val 再相加阿

~~~ c=
/* 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;
}

~~~
* 最後一段印出結果，我覺得比較特別的在於，+(SZP)42的轉換，正數加一次，負數加兩次，剛好符合圖形的轉換
* length 的長度這裡也派上用場
~~~ c=
/* Show the result. */
for (p = &digit[0]; p < &digit[SZD]; ++p) {
r = p->pos;
if (p->val)// 正數或負數加SZP
r += SZP;
if (p->val < 0)// 負數再加SZP
r += SZP;
strncpy(res + p->pos,
pat + r,
p->len);
}
~~~
* 前面並沒有特別解釋 length ，先從小排到大:
* ┌ ─ ─ ─ ┐ 每一劃都是 3 , \n 是 1

~~~
{ 0, 6 } -> 從 pos=0 ， 往後 6 的長度 "┌ ─"
{ 6, 3 } -> 0 的位置 +6 下一個從 pos=6 開始， 往後3的長度 "─"
{ 9, 7 } -> 6 的位置 +3 下一個從 pos=9 開始， 往後7個長度 "─ ┐\n"
{ 16, 8 } -> 9 的位置 +7 下一個從 pos=16 開始， 這裡我覺得是往後 5，我有試著改成 5 下去跑
， 結果是對的， 但對長度 8 不太理解

以下就類推...
~~~
* 直接拿上面的例子來說明：
~~~
要怎麼印出圖形呢？
*p = {pos = 32, len = 3, exp = 1, val = -1}

他會抓 pos = 32， 原本是 "─"
如果 val 加了 1 次 42 就會拿 "┬"
因為 val = -1 加了 2 次 42 就會拿 "┴"

~~~
### 針對特定的領域 ，列出在應用案例

### 參考資料