2017q3 Homework1 (ternary)

contributed by <amikai>

tags: sysprog2017

作業要求

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

astyle in vscode

先將 astyle 安裝之後, 案 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
• How do your format code in visual studio code

VSCodeVim

因為習慣 vim 的指法, 但是又想要有 vscode 的好用介面，所以就使用了 VSCodeVim 套件以下式我的設定檔以及相對應的 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 的功能:

• gc :增加 or 刪除(原文為 toggle )註解, 例如: gcc 為增加或刪除此行註解, gc2j 則圍註解或刪除此行和下行註解

• gC: 增加 or 刪除(原文為 toggle )區塊註解, gCi) 為增加或刪除小括號裡的註解

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

gitignore file

加入 gitigonre 以免不需要的檔案被 git 追蹤, 我使用了 C.gitignore 和 VisualStudioCode.gitignore, 後者是 vscode 所用的設定檔.

參考資料:

• A collection of useful .gitignore templates

Balanced tenary

一般三進位會以 0, 1, 2 表示數值, balanced tenary 則是以 -1, 0 , 1 表示數值, 舉例:

${67}_d=1T{111}_{bal3}=1\times 3^4+(-1)\times 3^3+1\times 3^2+1\times 3^0$

${38}_d=111T_{bal3}=1\times 3^3+1\times 3^2+1\times 3^1+(-1)\times 3^0$

基本運算:

$$\begin{array}{cccc}ADD& T& 0& 1\\ T& T1& T& 0\\ 0& T& 0& 1\\ 1& 0& 1& 1T\end{array}$$

$$\begin{array}{cccc}MUL& T& 0& 1\\ T& 1& 0& T\\ 0& 0& 0& 0\\ 1& T& 0& 1\end{array}$$

首先看到作業的第一張圖

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

$$\begin{array}{cccccccccc}& & 0& 0& 0& 1& T& 1& 1& 1\\ & +& 0& 0& 0& 0& 1& 1& 1& T\\ & & 0& 0& 0& 1& 0& T& T& T\\ & +& & & & & 1& 1& & \\ & & 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\times 3^n=1\times 3^{n+1}+(-1)\times 3^n$

所以我們就可以輕鬆的之道轉換規則了:

只要遇到 2 的時候就轉換成 1T

舉例:

$$\begin{array}{cccccccccc}& & 0& 0& 0& 1& 0& 2& 2& 0\\ & & & & & & & & & 0\\ & & & & & & & 1& T& \\ & & & & & & 1& T& & \\ & +& & & & 1& & & & \\ & & 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={\displaystyle \frac{3^{n+1}-1}{2}}$
至於老師為什麼沒減 1, 我就沒有想到哩

程式碼是寫給你修改的，不是給你欣賞用！
提出實驗方法並動手

jserv

補強工作

• git message 詳細度
• iota 的應用實力分析
• 3 進位表示的好處