---
tags: sysprog2017
---

# 2017q3 Homework1 (ternary)
contributed by <`HexRabbit`,`Yuessiah`[^1]>

## Balanced Ternary 簡介

Balanced Ternary 即為平衡三進制，其與一般三進制最為不同的是它在維持以三為底的基礎下使用平衡的 -1(以下用 T 表示),0,1 而不是 0,1,2 作為基本數位，這使得平衡三進位能透過簡單的同乘上 T 轉換來改變正負，在等位元下相較於二進位系統也有了更大的表示範圍。

>中英文字間、中數字之間需以空白隔開
>[name=課程助教][color=red]
>>已修正
>>[name=HexRabbit][color=blue]

### b3k觀察

┌───┐      ┌───┐
│   │ = 1  ┤   │ = 5
└─┬─┘      └┴┴─┘

稍微觀察一下便可以發現這只是平衡三進制的圖像化而已，其中由六點鐘開始順時針方向依序為$3^0,3^1,3^2...3^7$，而指針凹向內為 T， 向外為 1，無指針為 0。
圖像的最大值為$11111111_{bal3}$ = $3280_{10}$，

├─┴─┤
┤   ├
├─┬─┤

最小值為$TTTTTTTT_{bal3}$ = $-3280_{10}$

┌┬┬┬┐
├   ┤
└┴┴┴┘

### 四則運算

- 加法

|+|T|0|1|
|--|--|--|--|
|T|T1|T|0|
|0|T|0|1|
|1|0|1|1T|

其中有T+T與1+1的運算較為特殊，
不過透過分析可以很快的瞭解。

T + T = -2 = -3 + 1 = T1
1 + 1 = 2 = 3 - 1 = 1T

- 減法

|-|T|0|1|
|--|--|--|--|
|T|0|T|T1|
|0|T|0|1|
|1|0|1|1T|

平衡三進制的減法可以利用同乘T轉換正負的特性，
輕鬆轉換為加法運算

- 乘法

|$\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|

乘法與除法則與一般數學運算相同

### 正負數

一般我們熟知的二進位負數是利用二補數(2's complement)的方式來定義，
在正負數相加時會歸零並產生Overflow(進位)，
而有號數中的最高位(MSB)被稱為Signed bit，
但是在平衡三進制的系統中並沒有區分有號和無號數，
也沒有一個符號用以表達正負，
而判斷正負方式是以從左數來第一個非0位的trit(或許可以簡稱MST?)判斷：T->負數, 1->正數
簡單證明如下：
假設該trit為1，總共有N trits
也就是無論該trit後的N-1 trits總和為多少其皆為正數，
則假設該N-1 trits皆為T，即為證明 $3^{N-1} >= 3^{N-2}+3^{N-3}+3^{N-4}+...+3^1+3^0$
$$
3^{N-2}+3^{N-3}+3^{N-4}+...+3^1+3^0 = \dfrac{1*(3^{N-1}-1)}{3-1} \\
3^{N-1} >= \dfrac{1*(3^{N-1}-1)}{3-1} \\
2*3^{N-1} >= 3^{N-1}-1 \\
3^{N-1} >= -1\ 得證
$$

### 名詞轉換

在二進制系統中，以bit來表示單一位元，以byte表示8bits
在平衡三進制系統中，以trit表示單一位元，以tryte表示多個trits
- [ Setun ] 1tryte = 6trits
- [ IOTA ] 1tryte = 3trits -> $3^3$種變化，官方以[9A-Z]表示
- [ other ] 1tryte = 9trits

### 十進制轉換

整數部份：
跟十進制轉二進制的方法幾乎相同，唯一特殊的點是當使用短除法時餘 2 要填入 T 並進位
($2_{10}$ = $1T_{bal3}$)

3|25  ...1
 └─┬─ 
  3|8 ...2(T)
   └─┬─
    3|2(+1) ...0
     └───
       1

以$25_{10}$舉例，在平衡三進制即為$10T1_{bal3}$

小數部份：

### Radex Econamy
根據定義[^2] $E(b, N)=b\div(log_{b}N ＋ 1)$
>$log_{b}N$?
>[name=課程助教][color=red]
>>已修正 感謝提醒
>>[name=HexRabbit][color=blue]

對$E(b, N)$求導得知$b=e$有最小值
可得知在扣除易於表達(相對其他進制)的特性，三進制系統在資訊傳遞上是優於其他整數進制的，因為整數集中 3 最接近 e。

## 實做探討

### IOTA
IOTA 使用自行研發的三進制hash算法 Curl 以及基於 Keccak(SHA-3) 的三進制加密算法 Kerl 來達到 quantum resistent，Curl 實際上是透過降低 PoW 的難度[^3](BTC: $2^{68}$ IOTA: $3^8$)而使得量子電腦相較於普通電腦無法拿到顯著的優勢[^4]，而 Keccak 本身就是一種 post-quantum sufficient 的算法，所以我其實不太清楚在這裡套用三進位有帶來什麼明顯的好處。

[^1]: 本共筆是與Yuessiah[共同研究](https://hackmd.io/s/rJVybfOiZ)得以撰寫而成
[^2]: [數學趣談:三生萬物](http://www.global-sci.org/mc/issues/5/no4/freepdf/79s.pdf)
[^3]: [Resistance to quantum computations](https://iota.org/IOTA_Whitepaper.pdf)
[^4]: [Grover's algorithm](https://en.wikipedia.org/wiki/Grover%27s_algorithm)