# 2017q3 Homework1 (ternary)
contributed by <`HMKRL`>

---
>**TODO**:
>* 為甚麼 IOTA seed 是 81 characters?
>* IOTA　為甚麼使用 tryte?
>[color=red]

## 解釋 Balanced Ternary 原理
- [x] 解釋 Balanced Ternary 原理

Balanced ternary 是一種數值表示系統，每個位數可以有三種狀態：
- `-`
- `0`
- `+`

將 $n$ 位 Balanced Ternary 數值 $T$ 轉為 Base10 的方法如下 (`T[0]` is the least significant digit)：

$$
\sum_{i=0}^n T[i]\times3^i
$$

考慮以下 Ternary 加法運算真值表：

| sum| +| 0| -|
|:--:|:--:|:--:|:--:|
| +| -| +| 0|
| 0| +| 0| -|
| -| 0| -| +|

|carry| +| 0| -|
|:---:|:--:|:--:|:--:|
| +| +| 0| 0|
| 0| 0| 0| 0|
| -| 0| 0| -|

參考 [Fast Ternary Addition](http://homepage.divms.uiowa.edu/~jones/ternary/arith.shtml), Balanced ternary 加法運算可以透過以下半加器實作：

$$
s_i=(a_i+c_i)\\
c_{i+1}=cons(a_i,c_i)
$$

其中 $cons(a,b)$ 為 [Ternary Logic](http://homepage.divms.uiowa.edu/~jones/ternary/logic.shtml) 的一種邏輯運算子，其真值表如下

| cons| +| 0| -|
|:---:|:--:|:--:|:--:|
| +| +| 0| 0|
| 0| 0| 0| 0|
| -| 0| 0| -|

再以此為基礎完成全加器：


其中 ANY 為 另一種邏輯運算子，其真值表如下

| cons| +| 0| -|
|:---:|:--:|:--:|:--:|
| +| +| +| 0|
| 0| +| 0| -|
| -| 0| -| -|

---

## Balanced Ternary 的設計要解決的問題類型

考慮 4 bit unsigned integer 能表達的數值範圍：

binary: 0 ~ 15 共 $2^4$ 個不同數值
ternary: 0 ~ 80 共 $3^4$ 個不同數值

由於每個位元能儲存的資料量較多，因此 ternary 系統本身能儲存的資料量較多

此時再考慮 4 bit signed integer, 比較 ternary 及 balanced ternary 的差異：

ternary: -27 ~ 26 共 54 個不同數值
balanced ternary: -40 ~ 40 共 81 個不同數值

可以發現在考慮正負的情況下，比起 balanced ternary, ternary 系統僅能提供 $\frac{2}{3}$ 的數值範圍，原因是表示正負號必須佔用一位，但正負僅有兩種狀態，因此一部份空間無法使用

在使用 balanced ternary 時，每個位元儲存各自的正負資料，可以帶來兩個優點：

1. 方便運算： 不需額外處理正負，直接取 not 即可完成變號：

$$
39_{10}=+++0_{bt}\\
-39_{10}=---0_{bt}
$$

2. 節省空間，增加儲存密度

現代硬體採用"開"與"關"兩種狀態代表 `0` 與 `1`
但若能製造一種硬體能儲存 `+` `-` `0` 三種狀態（猜想：利用電壓具有正負或磁極做儲存），即能更有效率的利用空間

---

## 在 GitHub 裡頭可找到的應用案例
在 [iotaledger](https://github.com/iotaledger)/[kerl](https://github.com/iotaledger/kerl) 專案的說明中敘述：

IOTA Kerl:
IOTA is adding an additional hashing function, based on Keccak, with conversion to ternary.

The following document describes the functionality and specification to be implemented.

觀察[此段程式碼](https://github.com/iotaledger/kerl/blob/7ca94d3e8bc7b8223fe10e25c853b01273735968/python3/conv.py#L7)

tryte_table = {
        '9': [ 0,  0,  0],  #   0
        'A': [ 1,  0,  0],  #   1
        'B': [-1,  1,  0],  #   2
        'C': [ 0,  1,  0],  #   3
        'D': [ 1,  1,  0],  #   4
        'E': [-1, -1,  1],  #   5
        'F': [ 0, -1,  1],  #   6
        'G': [ 1, -1,  1],  #   7
        'H': [-1,  0,  1],  #   8
        'I': [ 0,  0,  1],  #   9
        'J': [ 1,  0,  1],  #  10
        'K': [-1,  1,  1],  #  11
        'L': [ 0,  1,  1],  #  12
        'M': [ 1,  1,  1],  #  13
        'N': [-1, -1, -1],  # -13
        'O': [ 0, -1, -1],  # -12
        'P': [ 1, -1, -1],  # -11
        'Q': [-1,  0, -1],  # -10
        'R': [ 0,  0, -1],  #  -9
        'S': [ 1,  0, -1],  #  -8
        'T': [-1,  1, -1],  #  -7
        'U': [ 0,  1, -1],  #  -6
        'V': [ 1,  1, -1],  #  -5
        'W': [-1, -1,  0],  #  -4
        'X': [ 0, -1,  0],  #  -3
        'Y': [ 1, -1,  0],  #  -2
        'Z': [-1,  0,  0],  #  -1
        }

可以發現採用 3-bit balanced ternary 來表示 hash 結果

參考 [Creating a new Seed / Wallet](https://iotasupport.com/gui-newseed.shtml)

`A - Z` + `9` 就是組成 `seed` 的字元

而 `convertBaseToBigint(array, base)` 則用於計算一開始提到轉換為十進位的方法：

def convertBaseToBigint(array, base):
    bigint = 0

    for i in range(len(array)):
        bigint += array[i] * (base ** i)

    return bigint