# 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, 說明文件裡給了一個簡單的範例:
```clike=
int Foo(bool isBar)
{
if (isBar)
{
bar();
return 1;
}
else
return 0;
}
```
- indent=space=4
按下 `tab` 後縮排的字元是 4 個 `space`, 而不是 `\t` 字元.
- indent-switches
其實此選項只是將 switch 裡的內容進行縮排, 文件給出了一個很好懂的範例:
```clike=
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 設定:
```JS
// 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的部份:
``` c
/*------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 的最大值:
``` c
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 進位表示的好處
Sign in with Wallet
Connect another wallet