# 2017q3 Homework1 (ternary)
contributed by <`amikai`>
###### tags: `sysprog2017`
# 作業要求
- [x] 解釋 Balanced Ternary 原理
- [ ] Balanced Ternary 的設計要解決什麼類型的問題，需要詳述實際應用案例 (如 IOTA/Tangle)。提示：從算術表達的精準度和空間使用效率去探討;
- [ ] 針對特定的領域 (如加密貨幣)，列出在 GitHub 裡頭可找到的應用案例，不僅列出程式碼，還要解說;
- [x] 在研究的過程中，應該會對既有工具進行修改或者重新開發 (不限程式語言)，也該一併指出，程式碼應該維護在 GitHub 上;

# 開發環境
- OS: Ubuntu
- IDE: vscode
# 環境配置
## astyle
首先 code style 被指定為以下指令: 但是我不懂就去查了一下說明文件

$ astyle --style=kr --indent=spaces=4 --indent-switches --suffix=none files

- style=kr
這個 option 只的是 k&r style, 說明文件裡給了一個簡單的範例:

int Foo(bool isBar)
{
    if (isBar)
    {
        bar();
        return 1;
    }
    else
        return 0;
}

- indent=space=4
按下 `tab` 後縮排的字元是 4 個 `space`, 而不是 `\t` 字元.
- indent-switches
其實此選項只是將 switch 裡的內容進行縮排, 文件給出了一個很好懂的範例:

switch (foo)
{
    case 1:
        a += 1;
        break;

    case 2:
    {
        a += 2;
        break;
    }
}
--------------------------becomes--------------------------

switch (foo)
{
    case 1:
        a += 1;
        break;

    case 2:
    {
        a += 2;
        break;
    }
}

- suffix=none
若不使用這個選項, Astyle 的預設行為會將 format 前的檔案進行備份並再原本檔名加上 `.orig`. 可以指定自己想要的名稱, Astyle 則會將備份的檔案命名為原本的檔案名稱+你指定的名稱. 舉個例子:

$ touch test
$ astyle --style=kr --indent=spaces=4 --indent-switches --suffix=yoyo test
$ ls
test  test.yoyo

作業裡我們將 suffix 指定為 none, 意思就是不進行備份.

參考資料:
- [astyle](https://sourceforge.net/projects/astyle/files/)

## astyle in vscode
先將 [astyle](https://marketplace.visualstudio.com/items?itemName=Lukamicoder.AStyleExtension) 安裝之後, 案 Preference -> setting, 將你需要的 `astyle.cmd_options` 加入 `User Settings` 檔案即可(加在右欄, 左欄是不能編輯的), 依我們的例子則將以下加入 `User Settings`

"astyle.cmd_options": [
        "--style=kr",
        "--indent=spaces=4",
        "--indent-switches",
        "--suffix=none"
    ], 

接下來可以使用 format 的快捷鍵, 在 linux 下快捷鍵為 `Ctrl`+`Shift`+`I`, 若不想每次 format 都要按快捷鍵, 可以試試看以下設定: 此三種設定式讓 vscode 再不同的時間點自動 format, 依序分別為 1. 再打字時 format 2. 再存檔時 format 3. 再貼上的時候 format

"editor.formatOnType": true,
"editor.formatOnSave": true,
"editor.formatOnPaste": true,

參考資料:
- [vscode astyle format](https://github.com/welkineins/vscode-astyle)
- [How do your format code in visual studio code](https://stackoverflow.com/questions/29973357/how-do-you-format-code-in-visual-studio-code-vscode)

## VSCodeVim
因為習慣 vim 的指法, 但是又想要有 vscode 的好用介面，所以就使用了 [VSCodeVim]( https://github.com/VSCodeVim/Vim) 套件以下式我的設定檔以及相對應的 vim 設定:

// inoremap jk <esc>
"vim.insertModeKeyBindingsNonRecursive": 
[
    {
        "before": [
            "j",
            "k"
        ],
        "after": [
            "<Esc>"
        ]
    }
],

// set hlsearch
"vim.hlsearch": true,

// set showcmd
"vim.showcmd": true,

// set ignorecase
"vim.ignorecase": true,

// other
"vim.useSystemClipboard": true,
"vim.statusBarColorControl": true,
"vim.statusBarColors": {
    "normal": "#005f5f",
    "insert": "#5f0000",
    "visual": "#5f00af",
    "visualline": "#005f87",
    "visualblock": "#86592d",
    "replace": "#000000"
},
"vim.disableAnnoyingNeovimMessage": true,

VSCodeVim 嵌入了 [vim-commentary](https://github.com/tpope/vim-commentary) 的功能:
- `gc` :增加 or 刪除(原文為 toggle )註解, 例如: `gcc` 為增加或刪除此行註解, `gc2j` 則圍註解或刪除此行和下行註解
- `gC`: 增加 or 刪除(原文為 toggle )區塊註解, `gCi)` 為增加或刪除小括號裡的註解

- `gd`: 跳轉到函數定義 (好用)

## gitignore file

加入 gitigonre 以免不需要的檔案被 git 追蹤, 我使用了 [C.gitignore](https://github.com/github/gitignore/blob/master/C.gitignore) 和 [VisualStudioCode.gitignore](https://github.com/github/gitignore/blob/master/Global/VisualStudioCode.gitignore), 後者是 vscode 所用的設定檔.

參考資料:
- [A collection of useful .gitignore templates](https://github.com/github/gitignore)

# Balanced tenary
一般三進位會以 0, 1, 2 表示數值, balanced tenary 則是以 -1, 0 , 1 表示數值, 舉例:
$67_{d}=1T111_{bal3}=1\times3^4 +(-1)\times3^3 + 1\times3^2 + 1\times3^0$
$38_{d}=111T_{bal3}= 1\times3^3 + 1\times3^2 + 1\times3^1 + (-1)\times3^0$

## 基本運算:

\begin{array}{c|ccc}
ADD & T & 0 & 1 \\
\hline
T & T1 & T & 0 \\
0 & T & 0 & 1 \\
1 & 0 & 1 & 1T
\end{array}

\begin{array}{c|ccc}
MUL & T & 0 & 1 \\
\hline
T & 1 & 0 & T \\
0 & 0 & 0 & 0 \\
1 & T & 0 & 1
\end{array}

首先看到作業的第一張圖 

如果我將此圖的正方形順時針從最底下的中間開始拉平, 並且將向內的改為 T , 向外的改為 1 , 沒向內或向外則為 0, 則會變成以下運算:

\begin{array}{ccccccccc}
& & 0 & 0 & 0 & 1 & T & 1 & 1 & 1 \\
& + & 0 & 0 & 0 & 0 & 1 & 1 & 1 & T \\
\hline
& & 0 & 0 & 0 & 1 & 0 & T & T & T \\
& + & & & & & 1 & 1 & & \\
\hline
& & 0 & 0 & 0 & 1 & 1 & 0 & T & 0
\end{array}

## 程式研讀
### 轉換部份

程式再前半段宣告了 `struct ds *p;` 變大量採用這個指標再控制到各個位數, 我在看懂程式之後進行了一些改寫, 讓我自己比較看的懂, 而不是依效能導向去更改程式:
整個程式最精華的部份應該就是由 ternary 轉換成 balanced-ternary的部份:

/*------before rewrite------*/

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


/*------after rewrite------*/

r = 0;
for (i = 0; i < SZD; i++) {
    if (r != 0)
        digit[i].val++;

    r = digit[i].val == 2;

    if (r != 0)
        digit[i].val = -1;
    
    digit[i].val *= inv;
}

了解這段程式前, 我們必須先知道這個式子:
> $2\times3^n=1\times3^{n+1}+(-1)\times3^{n}$

所以我們就可以輕鬆的之道轉換規則了:
> 只要遇到 2 的時候就轉換成 1T

舉例:

\begin{array}{ccccccccc}
& & 0 & 0 & 0 & 1 & 0 & 2 & 2 & 0 \\
\hline
& & & & & & & & & 0 \\
& & & & & & & 1 & T & \\
& & & & & & 1 & T & & \\
& + & & & & 1 & & & & \\
\hline
& & 0 & 0 & 0 & 1 & 1 & 0 & T & 0
\end{array}

---

另外以下程式決定了此程式表示　balanced-ternary 的最大值:

r = 3 * p->exp / 2;

其實只是一個很簡單的式子轉換, 假設我有 n 個位元表示三進位, 所以我能表示最大的數值為:
$3^0+3^1+3^2+...+3^n = \dfrac{3^{n+1}-1}{2}$
至於老師為什麼沒減 1, 我就沒有想到哩
:::danger
程式碼是寫給你修改的，不是給你欣賞用！
提出實驗方法並動手

:notes: jserv
:::

# 補強工作
- git message 詳細度
- iota 的應用實力分析
- 3 進位表示的好處