2017q3 Homework1 (ternary)

contributed by <apple11361>

Reviewed byvonchuang

• "再來直覺的認為是每行佔用14 bytes，不過隨即想到中間那行的空白和換行字元一定都是1 byte 呀。所以說是圖案部份佔3 btyes 囉，接下來直接印出長度來看看答案是不是跟我想的一樣"，建議可適當減少句末助詞的使用

已改進，謝謝。李俊德

• 在文末有一句："既然三進位是更接近人腦思維的系統，…"，然在其之前並無相關的敘述
• "那為什麼現在常見的 PC 沒有用所謂的三進位電腦？曾經莫斯科國立大學也打造過三進位電腦 Сетунь 不過最後卻不了了之。這其中的原因就是在已經發展二進位這麼久以來，突然要發展三進位且相容二進位是非常困難的，例如要將二進位數值轉換三進位就需要許多的乘法、除法。以及就硬體上來說，電晶體要表達通路和斷路十分簡單，但要有三種不同的狀態且兼顧高可靠度就不容易。"，不太確定這裡的原因是回答第一個問句，還是 Cетунь不了了之的原因。在這裡假設是回答問句，則可以對 Cетунь繼續深入研究
• 可繼續研究 Balanced Ternary 的應用案例

持續更新李俊德

隨手筆記

• tri-state
• trit
• more efficient as far as the how many components it used
  (18 trits 就能表示 387000000 但需要 29 bits 才能表示相同數字)
• balance puzzles
• 為什麼現在 PC 沒有在用三進位系統的？
• 1 Tryte = 6 trit
• 字串中有些字是1 byte 有些是 3 bytes 程式如何分辨？

Balanced Ternary原理

以 3 為 base 的數字系統，相對於二進位系統的 bit ，三進位系統稱作 trit 。但不同於標準 Ternary numeral system 的 1 trit 可以表示 0、1、2 ，Balanced Ternary numeral system 中 1 trit 可以表示 -1、0、1 。這種表示法不需要額外的 minus sign 就能直接表示負數，所以在加減法及乘法方面上效率要比二進位高。

1. 加法器 logic table

   Sum:

   $sum$	$-$	$0$	$+$
   $-$	$+$	$-$	$0$
   $0$	$-$	$0$	$+$
   $+$	$0$	$+$	$-$

   Carry:

   $C$	$-$	$0$	$+$
   $-$	$-$	$0$	$0$
   $0$	$0$	$0$	$0$
   $+$	$0$	$0$	$+$

   例如︰
   

   $8+9$ 寫做

   Carry︰  

   $+00$
       
   $+0-$
     
   $+$ 
   $+00$
     -–––––––––
   Sum︰    
   $-0-$
   Ans︰
   $+-0-$

   等於

   $27-9-1=17$

2. 減法只要將減數先乘以

   $-1$再做加法即可，而三進位中乘以
   $-1$這件事就是對每個 trit 的值做 not 。

3. 乘除

   multiplication table︰

   $\times$	$-$	$0$	$+$
   $-$	$+$	$0$	$-$
   $0$	$0$	$0$	$0$
   $+$	$-$	$0$	$+$

   division table︰

   $÷$	$-$	$0$	$+$
   $-$	$+$	$-\mathrm{\infty }$	$-$
   $0$	$0$	$Nan$	$0$
   $+$	$-$	$\mathrm{\infty }$	$+$

從以上真值表來看， Balanced Ternary numeral system 的硬體設計並不困難，但如果是標準 Ternary numeral system 就沒那麼簡單了。

現在來看看平衡三進位系統中的邏輯運算真值表，與其從

$T$(

$-1$)、

$0$、

$1$ 來看，我覺得把他想成

$F$(False)、

$U$(unknown)、

$T$(True) 會更好理解，其中

$U$ 可以想像成一個未知的狀態、可能是

$T$ 或

$F$ 。

例如像

$T$ 不管跟

$T$ 或

$F$ 做

$OR$ 都會是

$T$ ，所以

$T\vee U=T$

得到以下︰

$A$	$\mathrm{\neg }A$
$F$	$T$
$U$	$U$
$T$	$F$

$OR$	$F$	$U$	$T$
$F$	$F$	$U$	$T$
$U$	$U$	$U$	$T$
$T$	$T$	$T$	$T$

$AND$	$F$	$U$	$T$
$F$	$F$	$F$	$F$
$U$	$F$	$U$	$U$
$T$	$F$	$U$	$T$

$XOR$	$F$	$U$	$T$
$F$	$F$	$U$	$T$
$U$	$U$	$U$	$U$
$T$	$T$	$U$	$F$

現在將

$F$(False)、U(unknown)、

$T$(True)分別看作

$-1$、

$0$、

$1$，可以發現︰

$a\vee b=max(a,b)$

$a\wedge b=min(a,b)$

$a\oplus b=(\mathrm{\neg }a\wedge b)\vee (a\wedge \mathrm{\neg }b)$

加法器電路

從邏輯運算真值表和加法真值表可以看出平衡三進位的加法不像一般二進位可以用幾個邏輯閘直接組出來，在這邊用多工器來描述電路。

1. 先算 Sum ，因為
   $B$ 可能是
   $-1$、
   $0$、
   $1$ ，所以首先將
   $A-1$、
   $A$、
   $A+1$的電路畫好，再由
   $B$ 去選擇。

A-1:

$sum$	$-$	$0$	$+$
$-$	$+$	$-$	$0$
$0$	$-$	$0$	$+$
$+$	$0$	$+$	$-$

A+1:

$sum$	$-$	$0$	$+$
$-$	$+$	$-$	$0$
$0$	$-$	$0$	$+$
$+$	$0$	$+$	$-$

Sum:

$sum$	$-$	$0$	$+$
$-$	$+$	$-$	$0$
$0$	$-$	$0$	$+$
$+$	$0$	$+$	$-$

2. 再來是 Carry ，跟剛剛一樣的想法，如果
   $B$ 是負數， Carry 可能是負或零，如果
   $B$ 是正數， Carry 可能是正或零。

$C$	$-$	$0$	$+$
$-$	$-$	$0$	$0$
$0$	$0$	$0$	$0$
$+$	$0$	$0$	$+$

c語言實做

作業一給了一支c語言實做的三進位程式，內容是將輸入的十進位轉換成一個代表三進位數值的圖案，其中這個代表三進位數值的圖案是由8個trit組成。

最大值是︰

$$\begin{gathered} 3^0+3^1+3^2+3^3+3^4+3^5+3^6+3^7 \\ =\frac{1\cdot (1-3^8)}{1-3} \\ =3280 \end{gathered}$$

最小值是︰

$$\begin{gathered} (-3^0)+(-3^1)+(-3^2)+(-3^3)+(-3^4)+(-3^5)+(-3^6)+(-3^7) \\ =-(\frac{1\cdot (1-3^8)}{1-3}) \\ =-3280 \end{gathered}$$

程式流程︰

1. 讀取10進位輸入，如果是負數須紀錄起來並轉成正數
2. 轉換成一般3進位
3. 轉換成平衡3進位
4. 依照平衡3進位圖形輸出

其中稍微比較難懂的是4步驟，以下是程式碼

/* Show the result. */
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);
}

先簡單說明各個變數的意義
以下是 strcut ds 內容

struct ds {
    int pos, len, exp, val;
} digit[SZD] = {
    { 32, 3 },
    { 26, 6 },
    { 16, 8 },
    { 0, 6 },
    { 6, 3 },
    { 9, 7 },
    { 21, 5 },
    { 35, 7 }
};

1. digit 陣列是存放各個 trit 的資訊，有8個元素

2. 從 struct ds 的宣告可以看出每個 trit 結構中含有4種資訊

   1. int pos
      這是對應到結果圖形中該 trit 的位置
   2. int len
      這是對應到結果圖形中該 trit 的長度
   3. int exp
      這是對應到結果圖形中該 trit 的數值倍數，例如第一個是乘以
      $3^0$ 、第二個乘以
      $3^1$ 、第三個
      $3^2$…依此類推。
   4. int val
      這是對應到結果圖形中該 trit 的數值，在第二步驟中的一般三進位時值可能是 0、1、2，到第三步驟會被轉換成 -1、0、1。

3. SZD是常數8，代表程式中一個圖形包含8個 trit 資訊的資料結構

4. SZP是常數42，代表程式中一個圖形的表達需要用到42 bytes 。

5. res 是存結果圖形的陣列

不過我很納悶，為什麼一個圖案那樣的字串會佔用42 bytes ，看起來只有18 bytes 而已呀。為了先確定我上面的推測一個圖形佔用42 bytes是正確的，我就先直接印出變數 pat 的長度。

printf("%lu\n", strlen(pat));

得到的結果是 126 ，代表一個圖形的確是佔用42 bytes 。
再來直覺的認為是每行佔用14 bytes，不過隨即想到中間那行的空白和換行字元一定都是1 byte。所以說是圖案部份佔3 btyes，接下來直接印出長度來看看答案是不是跟我想的一樣。

printf("%lu\n", strlen("┌"));
printf("%lu\n", strlen("─"));

結果都是3。

所以看上去在宣告變數 digit 時就先設定好每個 trit 對應到圖形的位置和長度，上面程式碼再依照每個 trit 對應到的位置和長度複製正確的圖形到存結果的陣列 res 中。

這邊有兩件事讓我很疑惑了︰

1. 字串中有些字是1 byte 有些是 3 bytes 程式印出時如何分辨？

static const char *pat = "┌───┐\n"
                         "│   │\n"
                         "└───┘\n"
                         "├─┴─┤\n"
                         "┤   ├\n"
                         "├─┬─┤\n"
                         "┌┬┬┬┐\n"
                         "├   ┤\n"
                         "└┴┴┴┘\n";

2. 以下程式碼，為什麼 digit[2] 的位置、長度是 {16, 8} 而不是 {16, 5}？

struct ds {
    int pos, len, exp, val;
} digit[SZD] = {
    { 32, 3 },
    { 26, 6 },
    { 16, 8 },
    { 0, 6 },
    { 6, 3 },
    { 9, 7 },
    { 21, 5 },
    { 35, 7 }
};

如果長度是8，感覺會覆蓋到 digit[6] 的 trit 內容。而這支程式跑起來不會有錯誤的原因有兩個。

1. 圖形輸出的順序是從低位往高位，所以當 digit[6] 被 digit[2] 覆蓋後，等執行到 digit[6] 時會再次覆蓋正確的值。
2. 圖形字元的前2 bytes 相同，而且 digit[6] 剛好是由 pat 的第22、23、24 byte 表達，{ 16, 8 }只覆蓋到第23 byte 所以不會錯誤。

如果把程式碼改成以下，當 digit[2] 和 digit[6] 不屬於同個圖形時就可以看出錯誤了。

static const char *pat = "┌───┐\n"
                         "│   aaa\n"
                         "└───┘\n"
                         "├─┴─┤\n"
                         "┤   ├\n"
                         "├─┬─┤\n"
                         "┌┬┬┬┐\n"
                         "├   ┤\n"
                         "└┴┴┴┘\n";

for(p = &digit[SZD-1]; p >= &digit[0]; --p) {
    r = p->pos;
    if (p->val)
        r += SZP;
    if (p->val < 0)
        r += SZP;
    strncpy(res + p->pos,
            pat + r,
            p->len);
}

當執行程式時，輸入9，正確值應該是︰
┌───┐
┤   aaa
└───┘
但執行結果是︰
┌───┐
┤  ��a
└───┘

如果 digit[2] 的位置、長度是 {16, 5} 的話，執行上述程式碼的結果是正確的︰
┌───┐
┤   aaa
└───┘

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

為什麼現在常見的 PC 沒有在用三進位系統的？

  既然三進位是更接近人腦思維的系統，而且理論上也比二進位效能更好、更有效率、更少的硬體元件，那為什麼現在常見的 PC 沒有用所謂的三進位電腦？曾經莫斯科國立大學也打造過三進位電腦 Сетунь 不過最後卻不了了之。這其中的原因就是在已經發展二進位這麼久以來，突然要發展三進位且相容二進位是非常困難的，例如要將二進位數值轉換三進位就需要許多的乘法、除法。以及就硬體上來說，電晶體要表達通路和斷路十分簡單，但要有三種不同的狀態且兼顧高可靠度就不容易。
  但是如果未來光學電腦成功發展，將可以輕易結合三進位系統，因為光學電腦是利用光脈衝取代電子訊號，可以高準確度的表達三種狀態。

參考資料

• Number Systems 3: Ternary
• Hackaday 10th Anniversary: Non-Binary Computing
• LaTeX教材1
• LaTeX教材2
• Techopedia
• balanced-ternary