---
tags: 研究所
---
# 2017q3 Homework1 (作業區)
contributed by <twngbm>
---
### Review by `williamchangTW`
- Wikipedia 不等於 Wiki ，詳文可見於[2017年系統軟體系列討論區](https://www.facebook.com/search/top/?q=2017%20%E5%B9%B4%E7%B3%BB%E7%B5%B1%E8%BB%9F%E9%AB%94%E7%B3%BB%E5%88%97%E8%AA%B2%E7%A8%8B%E8%A8%8E%E8%AB%96%E5%8D%80)貼文中看見，簡易而論前者是架構在 Wiki 下的線上百科全書，後者是多人協同的超本文系統
- 根據三進位要解決什麼問題是可以繼續往下延伸的，比如老師說的 IOTA-Tangle 是基於此方式建構出來的想法，可以試著討論看看
>小弟坐井觀天，如有冒犯請見諒[name="williamchangTW"]
---
### 解釋 Balanced Ternary 原理
#### 簡介
Balanced Ternary基本上是由三進位轉變而來的，十進位轉三進位可以用簡單的除法，商數與餘數去轉換。
+ EX:42~10~=>X~3~
+ 42/3=14...0->digit 1
+ 14/3=4...2->digit 2
+ 4/3=1...1->digit 3
+ 1/3=0...1->digit 4(Stop here because商數=0)
+ Combine those digit we have
+ 42~10~=1X3^3^+1X3^2^+2X3^1^+0X3^0^=1120~3~
Balanced Ternary則是利用-1,0,1來做三進位的運算，以下將以T來代表-1的值。
+ EX:T01~B3~=-1X3^2^+0X3^1^+1X3^0^=-8~10~
假如我們帶入8，會發現8的balanced ternary表示法，剛好會是10T~B3~。
8與-8的總和為0，就如同T01和10T的三個位元的值剛好是相反的一樣。
Balanced Ternary表示法的特點就如上述所呈現的一樣，他是以0為原點平衡的一個表示法
#### 運算
首先引入加法表
| SUM | T | 0 | 1 |
| -------- | -------- | -------- |-------- |
| T | T1 | T |0|
| 0 | T | 0 |1 |
| 1 | 0 | 1 | 1T |
注意到T與T相加時會產生一個T的進位
而1與1相加時，和會變成T，並產生一個1的進位
再來我們嘗試將三進位轉換成Balanced Ternary
首先我們發現在三進位中，2的值不存在Balanced Ternary中，因此必須將他轉換成1T(1X3^1^+(-1)X3^0^=2)
以下將舉例如何轉換
* 42~10~=1120~3~
``` c=
Step1:
1 1 2 0 //將2置換為1T
Step2:
1
1 1 T 0 //將進位後的1擺上
Step3:
1 2 T 0//將2置換為1T
Step4:
1
1 T T 0
Step5:
2 T T 0 //將2置換為1T
Step6:
1 T T T 0
```
1TTT0~B3~即為42的Balanced Ternary表示法
自此我們便有辦法將十進位數字轉換為Balanced Ternary
### Balanced Ternary 的設計要解決什麼類型的問題
#### 三進位的好處 Radix economy
Radix Ecinomy的概念就是，表達同一個數目時，所需要的E越小，則其表現越好
公式為: ***E（b,N）=b⌊log~b~(N)+1⌋*** ，b為數字基底，N為被運算的目標數字
舉例，以轉換100為例
+ 2-Base:E(2,100)=2X⌊log~2~(100)+1⌋=2X7=14
+ 3-Base:E(3,100)=3X⌊log~3~(100)+1⌋=3X5=15
+ 10-Base:E(10,100)=10X⌊log~10~(100)+1⌋=10X3=30
我們從上面可以發現，同樣是100這個數目，用10進位會需要30bits來儲存，而2進位只需要14bits
以下圖片轉自[wiki](https://en.wikipedia.org/wiki/Radix_economy)
我們可以發現，當數字趨近無窮大時，三進位所使用的bits數會僅次於使用自然對數為底的進位表示法。表現甚至比二進位好
+ 我們可以來計算為何e有最小的radix ecinomy
+ E(b,N)=b⌊log~b~(N)+1⌋趨近於b(ln(N)/ln(b))
+ ln(N)為變數，我們將尋找何時(b/ln(b))有最小值
+ e代入會有最小值
### 針對特定的領域，列出在 GitHub 裡頭可找到的應用案例
### Code Review
這是一個將十進位數字轉換成Balanced Ternary並用圖形表示出來的程式碼
首先我發現以下這個for loop，每次執行時都會產生相同的結果
```c=
for (r = 0; r < SZD; ++r) {
p = &digit[r];
p->exp = r ? (3 * digit[r-1].exp) : 1;
p->val = 0;
}
```
這個for loop的作用在於，他將結構ds的exp與val值做初始化的動作，但是這個for迴圈的動作，不論輸入為何，每次結束的結果都相同，因此我直接把值做一次運算後，直接在定義結構ds處做<s>賦值</s>得動作。
:::danger
assign 在繁體中文的慣例，不翻譯為「賦值」(這是中國境內用語)，應該改寫為「指派...數值給...」 -- jserv
:::
```c=
struct ds {
int pos, len, exp, val;
} digit[SZD] = {
{ 32, 3, 1, 0 },
{ 26, 6, 3, 0 },
{ 16, 8, 9, 0 },
{ 0, 6, 27, 0 },
{ 6, 3, 81, 0 },
{ 9, 7, 243, 0 },
{ 21, 5, 729, 0 },
{ 35, 7, 2187,0 }
};
```
這樣就能避免每次進入程式都需要做一次運算。
再來就是
```c=
p = &digit[SZD - 1];
r = 3 * p->exp / 2;
if (src > r)
src = r;
else
r = src;
```
這段程式碼再做例外處理，處理說如果輸入的值大於或小於圖形最大能表示的上下限(±3280)，則將值設定成圖形能表現的極值。
但是目前遇到的狀況為，假如輸入int的最大值+1(2147483648)，則執行時會出現segmentation fault
目前處理方式為在數值輸入後，利用判斷式判斷是否大於3280與小於-3280，如果否，則繼續執行，如果超出此範圍，則return並結束程式。
此段程式碼，將輸入的十進位轉換為三進位
```c=
do {
while (r < p->exp)
--p;
r -= p->exp;
++p->val;
} while (r);
```
舉例來說輸入r=6，--p會一直執行到p={ 26, 6, 3, 0 }此結構，r-(p->exp)，且p->val+1
r被更新成3，結構p被更新成{ 26, 6, 3, 1 }。
此時r=3依舊符合進入此結構的條件，因此此過程會再被執行一次，結構p被更新成{ 26, 6, 3, 2 }
此do loop結束後，結構p的內容將會被更新成
```c=
{ 32, 3, 1, 0 },
{ 26, 6, 3, 2 },
{ 16, 8, 9, 0 },
{ 0, 6, 27, 0 },
{ 6, 3, 81, 0 },
{ 9, 7, 243, 0 },
{ 21, 5, 729, 0 },
{ 35, 7, 2187,0 }
```
可以發現將00000020~3~=6~10~
至此我們將十進位轉換為三進位
此段程式碼將三進位轉換為balanced ternary
```c=
while (p < &digit[SZD]) {
if (r)
++p->val;
r = p->val > 1;
if (r)
p->val -= 3;
p->val *= inv;
++p;
}
```
此段概念為
+ 當p->val=0且r=0時，則++P ***(0+0=0)***
+ 0無須進位，也無須轉換
+ 當p->val=0且r=1時，p->val=1 ***(0+1=1)***
+ 當p->val=1且r=0時，則++P(此處r被當成進位位元使用，r=0代表無進位)(1+0=0)
+ 當p->val=1且r=1時 ***(1+1=1T)***
+ p->val=2且r=1，注意2並不存在於balanced ternary中，因此我們將其轉換為1T，
即為p->val=-1，r=1
+ 當p->val=2且r=0時 ***(2+0=1T)***
+ 設定p->val=-1，r=1
+ 當p->val=2且r=1時 ***(2+1=3=10)***
+ 設定p->val=0,r=1
以剛剛的6為例，轉換完後p結構會成為
```c=
{ 32, 3, 1, 0 },
{ 26, 6, 3, -1 },
{ 16, 8, 9, 1 },
{ 0, 6, 27, 0 },
{ 6, 3, 81, 0 },
{ 9, 7, 243, 0 },
{ 21, 5, 729, 0 },
{ 35, 7, 2187,0 }
```
最後這段將畫出圖形
```c=
for (p = &digit[0]; p < &digit[SZD]; ++p) {
r = p->pos;
if (p->val)
r += SZP;
if (p->val < 0)
r += SZP;
strncpy(res + p->pos,
pat + r,
p->len);
}
```
此段程式碼必須搭配預先定義的*pat來看
```c=
//所有文字單元(┌，─，┐，│，└，┘以及底下的變形)
//其長度皆為3，而\n長度為1，空格( )長度為1
//因此我們可以計算*pat的每個元素的絕對位置
static const char *pat = "┌───┐\n"//0~15
"│ │\n"//16~25
"└───┘\n"//26~41
"├─┴─┤\n"//42~57
"┤ ├\n"//58~67
"├─┬─┤\n"//68~83
"┌┬┬┬┐\n"//84~99
"├ ┤\n"//100~109
"└┴┴┴┘\n";//110~124
```
因此以剛剛的例子來說
1. 結構P第一個進入for迴圈的數值是{ 32, 3, 1, 0 }
我們的p->val=0因此r=p->pos=32
strncpy將會在res中32的位置放置pat中32為起點，長度為3的字元 ***(─)***
2. 結構P第二個進入for迴圈的數值是{ 26, 6, 3, -1 },
我們的r->pal有值(-1)，因此兩個if判斷是都會進入，最後r的值會是110
strncpy將會在res中26的位置，放置pat中以110為起點，長度為6的兩個字元 ***(└┴)***
3. 結構P第三個進入for迴圈的數值是{ 16, 8, 9, 1 },
我們的r->pal有值(1)，因此只會進入第一個if判斷式，最後r的值會是58
strncpy將會在res中16的位置，放置pat中以58為起點，長度為8的兩個字元 ***(┤ )***
+ 此處有一個很奇怪的地方，如果取長度為8，則會取到別的元素，故將長度8改為5
4. 以下類推，最後將得出我們所要的圖形
Sign in with Wallet
Connect another wallet