# 2017q3 Homework1 (ternary)
###### tags: `進階電腦系統理論與實作 (Fall 2017)`
contributed by < `jcyztw` >
## Balanced ternary 原理介紹
balanced ternary 是以 3 為基底的數值系統，一個 trit (即此系統下一個數的 digit )有三種數值：-1、0、1 ( -1 可寫作$-$或 T，1 可寫作$+$)。
### 數的表示法
#### 與 10 進位之間的轉換
以下簡單舉例：
:::info
$\begin{split} -9_{dec} &= -1 \times 3^2 + 0 \times 3^1 + 0 \times 3^0 \\ &= T00_{bal3}\end{split}$
:::
:::info
$\begin{split} 10T_{bal3} &= 1 \times 3^2 + 0 \times 3^1 + (-1) \times 3^0 \\ &= 9 + (-1) \\ &= 8_{dec}\end{split}$
:::
#### 整數
(簡單以一些整數作例子)
|decimal|-12|-11|-10|-9|-8|-7|-6|-5|-4|-3|-2|-1|0|
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
|__bal3__|TT0|TT1|T0T|T00|T01|T1T|T10|T11|TT|T0|T1|T|0|
|decimal|12|11|10|9|8|7|6|5|4|3|2|1|
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
|__bal3__|110|11T|101|100|10T|1T1|1T0|1TT|11|10|1T|1|
#### 小數
(簡單以一些小數作例子)
|decimal|-0.9|-0.8|-0.7|-0.6|-0.5|-0.4|-0.3|-0.2|-0.1|
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
|__bal3__|$T.\overline{010T}$|$T.\overline{1TT1}$|$T.\overline{10T0}$|$T.\overline{11TT}$|$0.\overline T$ or $T.\overline1$|$0.\overline{TT11}$|$0.\overline{T010}$|$0.\overline{T11T}$|$0.\overline{0T01}$|
|decimal|0.9|0.8|0.7|0.6|0.5|0.4|0.3|0.2|0.1|
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
|__bal3__|$1.\overline{0T01}$|$1.\overline{T11T}$|$1.\overline{T010}$|$1.\overline{TT11}$|$0.\overline1$ or $1.\overline T$|$0.\overline{11TT}$|$0.\overline{10T0}$|$0.\overline{1TT1}$|$0.\overline{010T}$|
#### 從任何整數基底轉換為 balanced ternary
透過以下公式，可轉換成 balanced ternaryl：
$(a_n a_{n-1} \cdot\cdot\cdot a_1 a_0. c_1 c_2 c_3 \cdot\cdot\cdot)_b = \displaystyle\sum_{k=0}^{n}a_kb^k + \displaystyle\sum_{k=1}^{\infty}c_kb^{-k}$
其中 $a_n a_{n-1} {\cdot\cdot\cdot} a_1 a_0. c_1 c_2 c_3 {\cdot\cdot\cdot}$ 為該數在原來數值系統的表示方式，$_b$ 為原來的基底，$a_k$ 為小數點左邊第 k 位數值，$c_k$ 為小數點右邊第 k 位數值。
以下示範將一個十進位的數轉為 balanced ternary：
::: info
$\begin{split}-25.4_{dec} &= -(2\times10^1+5\times10^0+4\times10^{-1})_{dec} \\ &= -(1T\times101^1+1TT\times101^0+11\times101^{-1}) \\ &= -(1T\times101^1+1TT+11\div101) \\ &= -10T1.\overline{11TT} \\ &= T01T.\overline{TT11}\end{split}$
:::
### 邏輯運算
在 Balanced ternary 的邏輯 AND，OR，NOT 運算中，若-1、0、1分別代表 false，unknown，true，則
$A \land B \land C \land \cdot\cdot\cdot = MIN(A, B, C, \cdot\cdot\cdot)$
$A \lor B \lor C \lor \cdot\cdot\cdot = MAX(A, B, C, \cdot\cdot\cdot)$
以下表格為上述三個邏輯運算的 truth table：(F: false, U: unknown, T: true)
AND運算
|$\land$|F|U|T|
|:-:|:-:|:-:|:-:|
|__F__|F|F|F|
|__U__|F|U|U|
|__T__|F|U|T|
OR運算
|$\lor$|F|U|T|
|:-:|:-:|:-:|:-:|
|__F__|F|U|T|
|__U__|U|U|T|
|__T__|T|T|T|
NOT運算
$NOT(A)$
|$A$|$\neg A$|
|:-:|:-:|
|F|T|
|U|U|
|T|F|
### 四則運算
#### Single-trit 運算
加法
| $+$ | T | 0 | 1 |
|:-:|:-:|:-:|:-:|
| T | T1| T | 0 |
| 0 | T | 0 | 1 |
| 1 | 0 | 1 | 1T|
減法
(與除法一樣，最左方行為第 1 個運算元，最上方列為第 2 個運算元，且無交換性。例如 1-T 的答案在表格左下角那格，所以 1-T = 1T)
| $-$ | T | 0 | 1 |
|:-:|:-:|:-:|:-:|
| __T__ | 0 | T | T1|
| __0__ | 1 | 0 | T |
| __1__ | 1T| 1 | 0 |
乘法
| $\times$ | T | 0 | 1 |
|:-:|:-:|:-:|:-:|
| __T__ | 1 | 0 | T |
| __0__ | 0 | 0 | 0 |
| __1__ | T | 0 | 1 |
除法
| $\div$ | T | 0 | 1 |
|:-:|:-:|:-:|:-:|
| __T__ | 1 |NaN| T |
| __0__ | 0 |NaN| 0 |
| __1__ | T |NaN| 1 |
#### Multi-trit 運算(以下簡單舉例)
加法
:::info
$\begin{array}{l} \\
&1TT1TT.1TT1\\ +
&\ \ \ \ \ \ 11T1.T \\
\hline
&\ 1T0T10.0TT1 \\ +
&\ \ \ \ \ 1T &(進位) \\
\hline
&\ \ 1T1110.0TT1 \\ +
&\ \ \ \ \ \ T &(進位) \\
\hline
&\ \ 1T0110.0TT1
\end{array}$
:::
減法
:::info
$\begin{array}{l} \\
&1TT1TT.1TT1 &\ \ \ \ \ \ \ \ \ 1TT1TT.1TT1\\ -
&\ \ \ \ \ 11T1.T & \rightarrow +\ \ \ \ \ \ TT1T.1\\
\hline
& &\ \ \ \ \ \ \ \ \ \ \ 1T1001.TTT1 \\
&&\ \ \ \ \ +\ \ \ \ T\ \ \ T1 &(進位) \\
\hline
& &\ \ \ \ \ \ \ \ \ \ \ 1110TT.TTT1 \\
&&\ \ \ \ \ +\ T\ \ \ \ \ \ 1&(進位) \\
\hline
& &\ \ \ \ \ \ \ \ \ \ \ \ \ \ 1100T.TTT1 \\
\end{array}$
:::
乘法
:::info
$\begin{array}{l}
&\ \ \ \ \ \ \ \ \ \ \ \ 1TT1.TT \\
\times &\ \ \ \ \ \ \ \ \ \ \ \ T11T.1\ \ \ \\
\hline
&\ \ \ \ \ \ \ \ \ \ \ \ \ \ 1TT.1TT &(乘以\ 1) \\
&\ \ \ \ \ \ \ \ \ \ \ \ T11T.11 &(乘以\ T) \\
&\ \ \ \ \ \ \ \ \ 1TT1T.T &(乘以\ 1) \\
&\ \ \ \ \ \ \ 1TT1TT &(乘以\ 1) \\
&\ \ \ \ \ T11T11 &(乘以\ T) \\
\hline
&\ \ \ \ \ \ 0T0000T.10T
\end{array}$
:::
除法
若 dividend 小於一半除數的絕對值，則商數的該 trit 不是 1 就是 T (取決於 dividend 是正數或負數)；若 dividend 大於一半除數的絕對值，則該 trit 為 0。而在決定商數的每個 trit 之前，dividend 都要先跟一半的除數先比較大小。
:::success
上述原文：
If the dividend over the plus or minus half divisor, the trit of the quotient must be 1 or T. If the dividend is between the plus and minus of half the divisor, the trit of the quotient is 0. The magnitude of the dividend must be compared with that of half the divisor before setting the quotient trit.
:::
以下簡單舉例：
divisor: 11
0.5 $\times$ divisor: 1T
$$
\require{enclose}
\begin{array}{r}
1TTT \\
11 \enclose{longdiv}{1T01T} &1T=1T，但1T.01 > 1T \rightarrow set\ 1 \\
\underline{11} \phantom{01T} \\
T10 \phantom{1T} &T10<T1 \rightarrow set\ T \\
\underline{TT} \phantom{T} \\
T11 \phantom{T} &T11<T1 \rightarrow set\ T \\
\underline{TT} \phantom{T} \\
TT &TT<T1 \rightarrow set\ T \\
\underline{TT} \\
0
\end{array}$$
## Balanced ternary 可用來解決什麼樣的問題？
### 應用案例：IOTA / Tangle
在 IOTA 其 GitHub 中，搜尋 "ternary"，可在 "kerl" 目錄中找到此關鍵字。
IOTA Kerl 依據其簡介，是用來作 ternary 轉換的 hashing function (基於 [Keccak/SHA-3 演算法](https://zh.wikipedia.org/wiki/SHA-3))，其 README 中有更詳細的規格以及實作的介紹。
以下摘錄自其 Kerl 實作的 [Java 範例](https://github.com/iotaledger/kerl/blob/master/java/Kerl.java)：
```java=33
public void absorb(final int[] trits, int offset, int length) {
if (length % 243 != 0) throw new RuntimeException("Illegal length: " + length);
do {
//copy trits[offset:offset+length]
System.arraycopy(trits, offset, trit_state, 0, HASH_LENGTH);
//convert to bits
trit_state[HASH_LENGTH - 1] = 0;
byte[] bytes = convertBigintToBytes(convertTritsToBigint(trit_state, 0, HASH_LENGTH), BYTE_HASH_LENGTH);
//run keccak
keccak.update(bytes);
offset += HASH_LENGTH;
} while ((length -= HASH_LENGTH) > 0);
}
```
## 對既有工具進行修改或者重新開發
- [ ] (pending)
## 參考資料
* [Balanced ternary](https://en.wikipedia.org/wiki/Balanced_ternary "Balanced ternary from the Wikipedia")
* [IOTA介紹](http://www.iotachina.com/iota "IOTA介紹｜IOTA中國")
* [The Balanced Ternary Machines of Soviet Russia](https://dev.to/buntine/the-balanced-ternary-machines-of-soviet-russia) ???
* [Three-valued logic](https://en.wikipedia.org/wiki/Three-valued_logic "Three-valued logic from the Wikipedia")
* [The Tech Behind IOTA Explained](http://www.tangleblog.com/2017/01/25/the-tech-behind-iota-explained/)
* [IOTA · GitHub](https://github.com/iotaledger)
Sign in with Wallet
Connect another wallet