owned this note
owned this note
Published
Linked with GitHub
# 2017q3 Homework1 (ternary)
contributed by <`tina0405`>
### 解釋 Balanced Ternary 原理
#### 先從影片著手:
* [Number Systems 3: Ternary](https://www.youtube.com/watch?v=vOyiHMa-mtQ)
* 介紹 ternary 有別於一般電腦 binary 的運算方式,利用 0,1,2來表達,影片中利用除法的機制來進行 10 進位和 ternary 的轉換:
* Example : 以 $45_{10}$ 為例(註:R 是 remainder)
$45/3 = 15 R 0$
$15/3 = 5 R 0$
$5/3 = 1 R 2$
$1/3 = 0 R 1$
以乘法驗證
$45 = 1\times3^3 + 2\times3^2+0\times3^1+0\times3^0$
* [Hackaday 10th Anniversary: Non-Binary Computing](https://www.youtube.com/watch?v=TFTK074nG_M)
* 影片介紹 balanced ternary 有趣的在於 T,0,1(或影片中-1,0,1)可延伸出電路中的 negative voltage , ground , positive voltage,有別於 binary 的 on , off
* 影片中所提到的 [Kleene logic ternary truth table](https://en.wikipedia.org/wiki/Three-valued_logic)
* T:True / F:False / U:unkown
![](https://i.imgur.com/453yrJg.png)
* 正負數的轉換:
$5=3^2-3^1-3^0$ 而 $-5=-3^2+3^1+3^0$
我們會發現其實正數(1)和負數(T)只是符號的差異,因此有了下表:
![](https://i.imgur.com/aUiIq4i.png)
參考 [balanced ternary](https://en.wikipedia.org/wiki/Balanced_ternary)
* 影片中所提到的 Sum 和 Carry
|sum| - | 0 | + |
|:-:|:-:|:-:|:-:|
| - | + | - | 0 |
| 0 | - | 0 | + |
| + | 0 | + | - |
|carry| - | 0 | + |
|:-:|:-:|:-:|:-:|
| - | - | 0 | 0 |
| 0 | 0 | 0 | 0 |
| + | 0 | 0 | + |
其實就是 [WiKi](https://en.wikipedia.org/wiki/Balanced_ternary) 中的 Addition ,只是它將 SUM 和 CARRY 寫在一起
![](https://i.imgur.com/VaqW3Au.png)
* [參考](http://homepage.divms.uiowa.edu/~jones/ternary/arith.shtml) half adder 的例子理解這段
5+6 in decimal decimal, unsigned and balanced ternary
![](https://i.imgur.com/ATS97mx.png)
![](https://i.imgur.com/E9bU7Ln.png)
* 在 the modulo-3 半加法器的實現上:
![](https://i.imgur.com/KJ4LM4Q.png)
* consensus function: 延伸 Boolean logic 的想法如果兩者都為 T 則 T,兩者都F則F,有 0 (unknown) 則 unknown
![](https://i.imgur.com/fPkOzKr.png)
* sum function: 就像是普通的 sum 但特別的地方在於如果是 2 的話在 modulo 3 是 3-1(sum:-1),而 -2 的話是 -3+1(sum:1)
![](https://i.imgur.com/r81EMV7.png)
* [Balanced Ternary Full Adder](https://www.youtube.com/watch?v=v7XxIjv_mUc)
* 因為 Full Adder 有三種元素要相加 A ,B ,C,因此影片列出Balanced Ternary Full Adder 可能會相加的27種情況
* [Modulo 3 Sum and Product Functions. ](https://www.youtube.com/watch?v=cgcXoCnyZhQ)
* 這部影片開頭用 binary 去實作 ternary logic output network
表格是在說明,把3進位(0,1,2)換成2進位
| F | F2 | F1 |
|:-:|:-:|:-:|
| 0 | 0 | 0 |
| 1 | 0 | 1 |
| 2 | 1 | X |
* 2 是換成 1X ,是有原因的,因為只要 F2 是 1 就可知道是 2 根本不必判斷 F1 ,而 don't care 在用 K-map 轉成邏輯式子時,不一定要圈到,所以簡化了設計
* [ Ripple Adder in Binary and Ternary Logic ](https://www.youtube.com/watch?v=TfJxAb0owj8)
* 模擬 ripple adder 在二進位和三進位的狀況,在 6-bit 情況下 31+1 時有二進位的 maximum ripple,4-bit 情況下 26+1 有三進位的 maximum ripple
* 順便想了一下 Ripple Adder 在二進位時,能藉由 Carry Lookahead 加速,那在 modulo-3 應該也能,因為我們已經知道只有 $1+1$ 其 C=1, $-1+-1$ 其 C=-1,其餘都為0
### Balanced Ternary 的設計要解決什麼類型的問題
* 先參考了一篇 [the tangle](https://iota.org/IOTA_Whitepaper.pdf)
* [ Whitepaper Circle: IOTA Tangle - Presented by Sunny Aggarwal ](https://www.youtube.com/watch?v=tYbRyVrrUDY)
* 先說明了需要的演算法
* Blockchain -> linked list
* Tangle -> DAG (= [directed acyclic graph](https://en.wikipedia.org/wiki/Directed_acyclic_graph))
* 節點發出的交易,構成了 site set of the tangle
* Its edge set is obtained in the following way:
* 當一個新交易到達,他將會批准前面兩筆交易
* these approvals are represented by directed edge
>> 目前不了為什麼是批准前面 2 筆,而不是更多
>> 猜測是 3bits 是 1bit 記目前交易arrive , 2bit 記先前兩筆批准交易做驗證,繼續往看找答案
* 名詞解釋
* A indirectly approves B:如果沒有直接的 edge 從 A 到 B,只要有路徑的能從 A 到 B 就稱之
* genesis transaction : approved (directly or indirectly) by all other transactions
* genesis 一開始就有一個地址包含 all the tokens
* 然後他發送 tokens 去 "founder" addresses
* token 不會再其他地方被創造
* 優點:因為交易都由先前幾筆交易批准,沒有挖礦,不用支付獎勵金
* block : transaction
* 小數字 : 權重
* 大數字 : 累積權重
![](https://i.imgur.com/FQcyLlq.png)
~~~
此圖說明
When the new transaction X comes and approves A and C , it becomes the only tip;
the cumulative weight of all other transactions increases by 3 (X 的權重)
~~~
>>文中其實有強調權重為 $3^n$ (ternary) ,但還沒看到他的好處,也還不理解為何所加的額外 X (the only tip)權重就為 3 不為 1
* 發現了三進位的一個好處 [Radix economy](https://en.wikipedia.org/wiki/Radix_economy)
公式: $E(b,N)=b ⌊ log b ( N ) + 1 ⌋$
* 為了解說公式的含意直接舉例子,如果我們要表達 100 這個數
| |decimal | binary | ternary |
| :--------: | :--------: | :--------: | :--------:|
| b: base | 10 | 2 | 3 |
| N | 100 | 100 | 100 |
| E(b,N) | $10\times3$ | $2\times7$|$3\times5$|
* 明明都是表達 100 這個數字但如果我們用 10 進位就只需要三位數只是每個位數都有 0~9 可選擇 ,這樣一共需要 30 個 bits
* 如果是三進位表達100 -> 10201, 如此一來只要五位數 , 每位有 0~3 可選擇,一共需要 15 bits
* wiki 的表格 , 有一一列出不同 N 範圍的平均 E(b,N)
![](https://i.imgur.com/ir7Uh0P.png)
* 在這我們必須先了解為什麼 "e has the lowest radix economy"
* 首先利用 $E(b,N)$ 近似於 ${b\ {\log _{b}(N)}}={b{\ln(N) \over \ln(b)}}$
* ln(N) 是固定的 ,所以求 ${b \over \ln(b)}$ 的最小值
* 在 ${e \over \ln(e)}$ 有 minimum
### 在[balanced-ternary](https://github.com/sysprog21/balanced-ternary),分析需求,進行修改
* 先研究一下程式碼
~~~c=
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組式等下會代入 *p 中,分別是 pos 和 len
~~~
我認為會分成8組是因為,每組之間轉換+SZP(42)
1 <=> 0 <=> -1
├─ <=> ┌─ <=> ┌┬
┴ <=> ─ <=> ┬
─┤ <=> ─┐ <=> ┬┐
┤ <=> │ <=> ├
├ <=> │ <=> ┤
├─ <=> └─ <=> └┴
┬ <=> ─ <=> ┴
─┤ <=> ─┘ <=> ┴┘
~~~
* 可是如果只有第 1 筆是 0,我想我會將 0 拿出迴圈外,如此一來,少做了7次判斷
~~~c=
//exp 會一直乘3,除了第1筆 r=0
for (r = 0; r < SZD; ++r) {
p = &digit[r];
p->exp = r ? (3 * digit[r-1].exp) : 1;
p->val = 0;
}
//改寫成
p = &digit[0];
p->exp=1;
p->val = 0;
for (r = 1; r < SZD; ++r) {
p = &digit[r];
p->exp = 3 * digit[r-1].exp;
p->val = 0;
}
~~~
~~~=
(gdb) n
52 p = &digit[r];
4: r = 1
3: *p = {pos = 32, len = 3, exp = 1, val = 0}
//下一round
(gdb)
52 p = &digit[r];
4: r = 2
3: *p = {pos = 26, len = 6, exp = 3, val = 0}
...
~~~
* 如果輸入負的, inv=-1, src 變成正數
~~~c=
if (src < 0)
src *= inv = -1;
~~~
* 首先發現的問題是輸入數據沒有範圍限制,所以超過 $(3^8-1)/2$ = 3280 ,都會是正的 maximum ,甚至輸入1個很大的正數,會跑出負的 maximum
~~~
3281 3282 1111111111111
├─┴─┤ ├─┴─┤ ┌┬┬┬┐
┤ ├ ┤ ├ ├ ┤
├─┬─┤ ├─┬─┤ └┴┴┴┘
~~~
* 首先看了 [limit.h 的 Library Macros](https://www.tutorialspoint.com/c_standard_library/limits_h.htm)
* 而正數有限制在 INT_MAX 為 +2147483647 所以超過就 overflow 變成負數,即使有 Truncate to the largest allowed positive 也逃不掉 。
* 所以先加了限制條件
~~~ c=
int flag=1;
while(flag) {
printf(usage);
scanf("%d", &src);
if( src>=-3280 && src<=3280) {
flag=0;
}
}
~~~
* 其實它有處理超過 3280 的數,但為什麼是 r = 3 * p->exp/2 原因在於在第7(SZD-1)筆的 p->exp 是 6561 但我們可能會寫成 $(6561-1)/2$ ,其實在 int 裡 $6561/2 =(6561-1)/2=3280$
~~~ c=
/* Truncate to the largest allowed positive. */
p = &digit[SZD - 1];
r = 3 * p->exp/2;
if (src > r)
src = r;
else
r = src;
~~~
* 這段是先把它變成三進位,舉個例子:
* 如果輸入 2 ,因為比 2 小的 3 的倍數,會選這組
input : *p = {pos = 32, len = 3, exp = 1, val = 0}
這表示他沒辦法進位成 $3^1$ 所以只能變成 2 組 $3^0$,結果記在 val
output : *p = {pos = 32, len = 3, exp = 1, val = 2}
~~~ c=
/* Like 'echo "obase=3; $src" | bc'. */
do {
while (r < p->exp)
--p;
r -= p->exp;
++p->val;
} while (r);
~~~
* 這裡先說明 p < &digit[SZD] ,因為矩陣是連續記憶體空間所以可以這樣比大小
* 還有這個寫法真的很厲害 r = p->val > 1 ,比完大小後直接assign true(1) or false(0)
* 如果拿剛剛的例子來說,這邊 2 就是會被 -3 然後進位 $3^1-1$ 記錄成:
~~~
*p = {pos = 32, len = 3, exp = 1, val = -1}
*p = {pos = 26, len = 6, exp = 3, val = 1}
~~~
* $3\times1+1\times-1$ : 原來是 exp $\times$ val 再相加阿
~~~ c=
/* Convert to the balanced form. */
while (p < &digit[SZD]) {
if (r)
++p->val;
r = p->val > 1;
if (r)
p->val -= 3;
p->val *= inv;
++p;
}
~~~
* 最後一段印出結果,我覺得比較特別的在於,+(SZP)42的轉換,正數加一次,負數加兩次,剛好符合圖形的轉換
* length 的長度這裡也派上用場
~~~ c=
/* Show the result. */
for (p = &digit[0]; p < &digit[SZD]; ++p) {
r = p->pos;
if (p->val)// 正數或負數加SZP
r += SZP;
if (p->val < 0)// 負數再加SZP
r += SZP;
strncpy(res + p->pos,
pat + r,
p->len);
}
~~~
* 前面並沒有特別解釋 length ,先從小排到大:
* ┌ ─ ─ ─ ┐ 每一劃都是 3 , \n 是 1
~~~
{ 0, 6 } -> 從 pos=0 , 往後 6 的長度 "┌ ─"
{ 6, 3 } -> 0 的位置 +6 下一個從 pos=6 開始, 往後3的長度 "─"
{ 9, 7 } -> 6 的位置 +3 下一個從 pos=9 開始, 往後7個長度 "─ ┐\n"
{ 16, 8 } -> 9 的位置 +7 下一個從 pos=16 開始, 這裡我覺得是往後 5,我有試著改成 5 下去跑
, 結果是對的, 但對長度 8 不太理解
以下就類推...
~~~
* 直接拿上面的例子來說明:
~~~
要怎麼印出圖形呢?
*p = {pos = 32, len = 3, exp = 1, val = -1}
他會抓 pos = 32, 原本是 "─"
如果 val 加了 1 次 42 就會拿 "┬"
因為 val = -1 加了 2 次 42 就會拿 "┴"
~~~
### 針對特定的領域 ,列出在應用案例
### 參考資料