2017q3 Homework1 (ternary)
===
contribute by <`yuan922`>

---
### Review by `williamchangTW`
- 用printf() 去做偵測看到實際資料是一個滿好用的方式，或許可以藉由此方法去更改 code 有些疑慮的地方，比如到達哪個數會發生錯誤的資料
- 關於 ternary 的分析，看得出來你對該定義有一定程度的瞭解，試著分析老師給的案例，應該能銀刃而解
>小弟坐井觀天，如有冒犯請見諒[name="williamchangTW"]

---

## Ternary 定義:
以三為基底的進位，其位數稱為三進位數(trit)，使用0,1,2三個數表示。
P.S.二進位的位數稱為bit(binary digit的縮寫)。

## Balanced Ternary 定義:
相較於三進位用0,1,2表示，平衡三進位使用T(-1),0,1來表示數值，
這樣可以省去使用額外的負號表示負數。

### 整數
* #### $7_{10}=1T1_{bal3}$
> $1T1_{bal3}=1*3^2+(-1)*3^1+1*3^0\\
> =7$
* #### $-7_{10}=T1T_{bal3}$
> $T1T_{bal3}=(-1)*3^2+1*3^1+(-1)*3^0\\
> =-7$
* #### $2356_{10}=101T01T1_{bal3}$
>用3來除看看:
>$\begin{split}\ 2356/3&=785...1\\
>785/3&=262...T\\
>262/3&=87...1\\
>87/3&=29...0\\
>29/3&=10...T\\
>10/3&=3...1\\
>3/3&=1...0\\
>1/3&=0...1\\
>由下往上寫回去:101T01T1
>\end{split}$

#### 與一般的除法不一樣的地方:
一般除法是要除出一個餘數(不夠的數)，而這裡因為只用-1,0,1來表示，
所以要產生-1就要乘上一個會超過**被除數**的數字
**e.g.** 785/3=262...T 原本應該會是261...2
**e.g.** 29/3=10...T 原本應該會是9...2

### 小數
* #### $-22.4_{10}=T1TT.\overline{TT11}_{bal3}$
>$\begin{split}\ 整數部分:-22\\
>-22/3&= -7\dfrac{1}{3} 最接近整數為-7...-1\\
>-7/3&=-2\dfrac{1}{3} 最接近整數為-2...-1\\
>-2/3&=-\dfrac{2}{3} 最接近整數為-1...1\\\
>-1/3&=-\dfrac{1}{3} 最接近整數為0...-1\\
>\end{split}$
>$\begin{split}\ 小數部分:-0.4\\
>-0.4*3&=-1.2 圓整為-1... -0.2\\
>-0.2*3&=-0.6 圓整為-1... 0.4\\
>0.4*3&=1.2圓整為1... 0.2\\
>0.2*3&=0.6圓整為1...-0.4,循環\\
>\end{split}$

## 真值表
AND(Min取小):有T的都會是T，因為最小
| ∧ | T | 0 | 1 |
| -------- | -------- | -------- | -------- |
| T | T | T | T |
| 0 | T | 0 | 0 |
| 1 | T | 0 | 1 |
OR(Max取大):有1的都會是1，因為最大
| ∨ | T | 0 | 1 |
| -------- | -------- | -------- | -------- |
| T | T | 0 | 1 |
| 0 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 |
XOR (a ⊕ b) = ( (a ∧ – b) ∨ (b ∧ – a) )
| ⊕ | T | 0 | 1 |
| -------- | -------- | -------- | -------- |
| T | T | 0 | 1 |
| 0 | 0 | 0 | 0 |
| 1 | 1 | 0 | T |
## Balanced ternary 半加法器
先以logic table觀察Sum跟Carry的結果:
### Logic table
| Sum | -- | 0 |+ |
| -------- | -------- | -------- |-------- |
| -- | **<font color="red">+</font>**| -- |0 |
| 0 | -- | 0 |+ |
| + | 0 | + |**<font color="red">--</font>** |

| Carry | -- | 0 |+ |
| -------- | -------- | -------- |-------- |
| -- | **<font color="red">--</font>** | 0 |0 |
| 0 | 0 | 0 |0 |
| + | 0 | 0 |**<font color="red">+</font>** |

**紅字解釋:**
>(-1)+(-1)=-2在$bal_3$會用(-3)+1表示也就是$T1$
>(+1)+(+1)=2在$bal_3$會用3+(-1)表示也就是$1T$
>這我想好久...
>[name=yuan922]

**Balanced ternary half adder**
(a ⊠ b):a,b同時為-則-,同時為+則+,其餘皆0。

## **程式碼分析**

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

從第3行的判斷式來看，因為r一開始是0，所以一定會跳到後面的結果，
也就是說 p->exp=1;而 p = &digit[0]，
那麼 digit[0].exp 就會是1。

為了方便觀察 exp 的變化，用 **printf** 印出變化：

for (r = 0; r < SZD; ++r) {
        p = &digit[r];
        printf("exp_before %d \n",p->exp);
        p->exp = r ? (3 * digit[r-1].exp) : 1;
        printf("exp_after %d\n",p->exp);
        p->val = 0;
    }


可以看出exp就是不斷的*3，以$3^n$變化。

 p = &digit[SZD - 1];
    r = 3 * p->exp / 2;
    if (src > r)
        src = r;
    else
        r = src;

r=3*2184/2=3280.5，所以如果輸入大於r就只能最多到r。

  do {
        while (r < p->exp)
            --p;
        r -= p->exp;
        ++p->val;
    } while (r);

拿r=15為例：一開始進去迴圈會先不斷的遞減p直到r超過一個最近的值，
以15來說就會從2187一直遞減到9，之後15-9=6，
p->exp=9的val+1，再來6會對應到3，6-3=3，
p->exp=3的val+1，再來3也會對應到3，3-3=0，
p->exp=3的val再+1，跳出迴圈。
* 結果：15會被表示成1 * 9+2 * 3也就是$1*3^2+2*3^1$

 while (p < &digit[SZD]) {
        if (r)
            ++p->val;
        r = p->val > 1;
        if (r)
            p->val -= 3;
        p->val *= inv;
        ++p;
    }

這段是轉換成 $bal_3$的形式:
1. r=0進去之後跳到第4行，因為exp=3的val=2>1，所以r為真，
exp=3的val-3=-1，結束$3^1$項，再來換$3^2$項。
2. 因為r為真，第三行exp=9的val會+1變2，第4行2>1成立，
exp=3的val-3=-1，結束$3^2$項，再來換$3^3$項。
3. 因為r為真，第三行exp=27的val會從0+1，由於1>1不成立，直接跳到第7行，p再加1，但接下來的r跟p->val都沒值所以結束。

* 結果:15就會被換成 $1TT0$。

## Balanced Ternary 的設計要解決什麼類型的問題，需要詳述實際應用案例 (如 IOTA/Tangle)。

## 針對特定的領域 (如加密貨幣)，列出在 GitHub 裡頭可找到的應用案例

## 參考資料
* [C01: Ternary](https://hackmd.io/s/Sym0UAk9Z)
* [平衡三進位-wikipedia](https://zh.wikipedia.org/wiki/%E5%B9%B3%E8%A1%A1%E4%B8%89%E8%BF%9B%E5%88%B6#.E5.B0.8F.E6.95.B0)
* [台灣wiki](http://www.twwiki.com/wiki/%E4%B8%89%E9%80%B2%E4%BD%8D)