2017q3 Homework1 (作業區)

--- 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) ![](https://i.imgur.com/lMqYdOk.png) 我們可以發現，當數字趨近無窮大時，三進位所使用的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. 以下類推，最後將得出我們所要的圖形

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.