Try   HackMD

2017q3 Homework1 (作業區)

contributed by <twngbm>

Review by williamchangTW

  • Wikipedia 不等於 Wiki ，詳文可見於2017年系統軟體系列討論區貼文中看見，簡易而論前者是架構在 Wiki 下的線上百科全書，後者是多人協同的超本文系統
  • 根據三進位要解決什麼問題是可以繼續往下延伸的，比如老師說的 IOTA-Tangle 是基於此方式建構出來的想法，可以試著討論看看

小弟坐井觀天，如有冒犯請見諒"williamchangTW"

解釋 Balanced Ternary 原理

簡介

Balanced Ternary基本上是由三進位轉變而來的，十進位轉三進位可以用簡單的除法，商數與餘數去轉換。

  • EX:4210=>X3
    • 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
    • 4210=1X33+1X32+2X31+0X30=11203

Balanced Ternary則是利用-1,0,1來做三進位的運算，以下將以T來代表-1的值。

  • EX:T01B3=-1X32+0X31+1X30=-810

假如我們帶入8，會發現8的balanced ternary表示法，剛好會是10TB3。
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(1X31+(-1)X30=2)
以下將舉例如何轉換

  • 4210=11203




















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

1TTT0B3即為42的Balanced Ternary表示法
自此我們便有辦法將十進位數字轉換為Balanced Ternary

Balanced Ternary 的設計要解決什麼類型的問題

三進位的好處 Radix economy

Radix Ecinomy的概念就是，表達同一個數目時，所需要的E越小，則其表現越好
公式為: E（b,N）=b⌊logb(N)+1⌋ ，b為數字基底，N為被運算的目標數字
舉例，以轉換100為例

  • 2-Base:E(2,100)=2X⌊log2(100)+1⌋=2X7=14
  • 3-Base:E(3,100)=3X⌊log3(100)+1⌋=3X5=15
  • 10-Base:E(10,100)=10X⌊log10(100)+1⌋=10X3=30

我們從上面可以發現，同樣是100這個數目，用10進位會需要30bits來儲存，而2進位只需要14bits
以下圖片轉自wiki

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

我們可以發現，當數字趨近無窮大時，三進位所使用的bits數會僅次於使用自然對數為底的進位表示法。表現甚至比二進位好

  • 我們可以來計算為何e有最小的radix ecinomy
    • E(b,N)=b⌊logb(N)+1⌋趨近於b(ln(N)/ln(b))
    • ln(N)為變數，我們將尋找何時(b/ln(b))有最小值
    • e代入會有最小值

針對特定的領域，列出在 GitHub 裡頭可找到的應用案例

Code Review

這是一個將十進位數字轉換成Balanced Ternary並用圖形表示出來的程式碼
首先我發現以下這個for loop，每次執行時都會產生相同的結果






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處做賦值得動作。

assign 在繁體中文的慣例，不翻譯為「賦值」(這是中國境內用語)，應該改寫為「指派…數值給…」 – jserv













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 }
};

這樣就能避免每次進入程式都需要做一次運算。

再來就是







  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並結束程式。

此段程式碼，將輸入的十進位轉換為三進位







 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的內容將會被更新成









{ 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 }

可以發現將000000203=610
至此我們將十進位轉換為三進位

此段程式碼將三進位轉換為balanced ternary










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結構會成為









{ 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 }

最後這段將畫出圖形












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來看














//所有文字單元(┌，─，┐，│，└，┘以及底下的變形)
//其長度皆為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
  1. 以下類推，最後將得出我們所要的圖形
Last changed by 
 
Jack-Chen
0
967
Published on HackMD