2017q3 Homework1 (ternary)

tags: 進階電腦系統理論與實作 (Fall 2017)

contributed by < jcyztw >

Balanced ternary 原理介紹

balanced ternary 是以 3 為基底的數值系統，一個 trit (即此系統下一個數的 digit )有三種數值：-1、0、1 ( -1 可寫作

$-$或 T，1 可寫作

$+$)。

數的表示法

與 10 進位之間的轉換

以下簡單舉例：

$\begin{array}{rl}-9_{dec}& =-1\times 3^2+0\times 3^1+0\times 3^0\\ & =T{00}_{bal3}\end{array}$

$\begin{array}{rl}10T_{bal3}& =1\times 3^2+0\times 3^1+(-1)\times 3^0\\ & =9+(-1)\\ & =8_{dec}\end{array}$

整數

(簡單以一些整數作例子)

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.\bar{T}$ or $T.\bar{1}$	$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.\bar{1}$ or $1.\bar{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}_k{b}^k+{\displaystyle \sum _{k=1}^{\mathrm{\infty }}{c}_k{b}^{-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：

$\begin{array}{rl}-{25.4}_{dec}& =-(2\times {10}^1+5\times {10}^0+4\times {10}^{-1}{)}_{dec}\\ & =-(1T\times {101}^1+1TT\times {101}^0+11\times {101}^{-1})\\ & =-(1T\times {101}^1+1TT+11÷101)\\ & =-10T1.\overline{11TT}\\ & =T01T.\overline{TT11}\end{array}$

邏輯運算

在 Balanced ternary 的邏輯 AND，OR，NOT 運算中，若-1、0、1分別代表 false，unknown，true，則

$A\wedge B\wedge C\wedge \cdot \cdot \cdot =MIN(A,B,C,\cdot \cdot \cdot )$

$A\vee B\vee C\vee \cdot \cdot \cdot =MAX(A,B,C,\cdot \cdot \cdot )$

以下表格為上述三個邏輯運算的 truth table：(F: false, U: unknown, T: true)

AND運算

$\wedge$	F	U	T
F	F	F	F
U	F	U	U
T	F	U	T

OR運算

$\vee$	F	U	T
F	F	U	T
U	U	U	T
T	T	T	T

NOT運算

$NOT(A)$

$A$	$\mathrm{\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
除法
$÷$	T	0	1
:-:	:-:	:-:	:-:
T	1	NaN	T
0	0	NaN	0
1	T	NaN	1

Multi-trit 運算(以下簡單舉例)

加法

$\begin{array}{l}\\ & 1TT1TT.1TT1\\ +& 11T1.T\\ & 1T0T10.0TT1\\ +& 1T& (\mathrm{進}\mathrm{位})\\ & 1T1110.0TT1\\ +& T& (\mathrm{進}\mathrm{位})\\ & 1T0110.0TT1\end{array}$

減法

$\begin{array}{l}\\ & 1TT1TT.1TT1& 1TT1TT.1TT1\\ -& 11T1.T& \to +TT1T.1\\ & & 1T1001.TTT1\\ & & +TT1& (\mathrm{進}\mathrm{位})\\ & & 1110TT.TTT1\\ & & +T1& (\mathrm{進}\mathrm{位})\\ & & 1100T.TTT1\end{array}$

乘法

$\begin{array}{ll}& 1TT1.TT\\ \times & T11T.1\\ & 1TT.1TT& (\mathrm{乘}\mathrm{以}1)\\ & T11T.11& (\mathrm{乘}\mathrm{以}T)\\ & 1TT1T.T& (\mathrm{乘}\mathrm{以}1)\\ & 1TT1TT& (\mathrm{乘}\mathrm{以}1)\\ & T11T11& (\mathrm{乘}\mathrm{以}T)\\ & 0T0000T.10T\end{array}$

除法
若 dividend 小於一半除數的絕對值，則商數的該 trit 不是 1 就是 T (取決於 dividend 是正數或負數)；若 dividend 大於一半除數的絕對值，則該 trit 為 0。而在決定商數的每個 trit 之前，dividend 都要先跟一半的除數先比較大小。

上述原文：
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

$$\begin{array}{r}1TTT\\ 11\text{enclose}longdiv1T01T& 1T=1T，\mathrm{但}1T.01>1T\to set1\\ \underset{―}{11}\phantom{01T}\\ T10\phantom{1T}& T10<T1\to setT\\ \underset{―}{TT}\phantom{T}\\ T11\phantom{T}& T11<T1\to setT\\ \underset{―}{TT}\phantom{T}\\ TT& TT<T1\to setT\\ \underset{―}{TT}\\ 0\end{array}$$

Balanced ternary 可用來解決什麼樣的問題？

應用案例：IOTA / Tangle

在 IOTA 其 GitHub 中，搜尋 "ternary"，可在 "kerl" 目錄中找到此關鍵字。
IOTA Kerl 依據其簡介，是用來作 ternary 轉換的 hashing function (基於 Keccak/SHA-3 演算法)，其 README 中有更詳細的規格以及實作的介紹。

以下摘錄自其 Kerl 實作的 Java 範例：

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
• IOTA介紹
• The Balanced Ternary Machines of Soviet Russia ???
• Three-valued logic
• The Tech Behind IOTA Explained
• IOTA · GitHub