2017q3 Homework1 (ternary)
===
contributed by < `shanshow` >

### Reviewed by`vonchuang`
* 引文中有一段:"三進位邏輯電路非但比二進位邏輯電路速度更快、可靠性更高，而且需要的設備和電能也更少"，可實際去了解電路並證實其真實性
* 可列出 IOTA 的程式碼並解釋，而非只寫出連結
* "在reddit的討論串中，有人提問，為何使用二進位系統而非最有效率的 base e 系統，底下有一連串討論。"，在文中沒有看到對此疑問做出明確的結論

[閱讀文件紀錄：重新理解數值](https://hackmd.io/AwEwZmIgRghgtAUwMYDZjwCwFYCcAmeXARnHgHYdloAOZWaU4IA=)
# Balanced Ternary：

### **介紹：**

三進位中的其中一種，其特色是將`+`與`-`、`0`作為基本數位的進位。
比較如下：

| Truth value | Unsigned | Balanced |
| ------------- |:--------------|:----------|
| **false** | 0 | - |
| **unknown** | 1 | 0 |
| **true** | 2 | + |

我們曾經學過許多二進位的表達正負方式，像是一的補數、二的補數等等，而這些方式都有或多或少的問題。
這兩種補數方式最大的問題在於必須犧牲最前頭的位數來表達正負，而一的補數因此會產生兩個0的表述方式；二的補數則是在正負轉換時需額外+1。
平衡三進位則把正負的表述方式內化成一種進位，不需要額外的符號表述正負就能夠達到效果，因此在加減法與乘法方面會較二進位為高效率。

### 由任何整數進位轉換成平衡三進位的方法
使用
$(a_n a_{n-1} \dotsi a_1 a_0. c_1 c_2 c_3 \dotsi)_b = \sum_{k=0}^{n}a_kb^k + \sum_{k=0}^{n}c_kb^{-k}$
其中
* $a_{n}a_{n-1}\cdots a_{1}a_{0}.c_{1}c_{2}c_{3}\cdots$ is the original representation in the original numeral system.
* 假設一個原本的數字是123.456，那麼 $a2$ = 1, $a1$ = 2, $a0$ = 3, $c1$ = 4, $c2$ = 5, $c3$ = 6
* $b$ is the original radix. b is 10 if converting from decimal.
* b數值告知那個數字是幾進位的，如果是10那那個數字就10進位。
* ${\displaystyle a_{k}}$ and ${\displaystyle c_{k}}$ are the digits $k$ places to the left and right of the radix point respectively.
* $k$數值可以決定 ${\displaystyle a_{k}}$ 跟 ${\displaystyle c_{k}}$ 的左移或右移，從0到n計算後求出其值。

舉例(以T代替原本的 $-$ 以讓版面好看)：
$\begin{split}\
{\displaystyle -25.4_{dec}} &= −(1T×{\displaystyle 101^{1}} + 1TT×{\displaystyle 101^{0}} + 11×{\displaystyle 101^{-1}})\\
&= −(1T×101 + 1TT + 11÷101)\\
&= −10T1.\overline{11TT}\\
&= T01T.\overline{TT11} \end{split}$

> 將$25.4$的三個數字分別拆開變成三個三進位帶入公式後的數值後代入公式，進行計算，此例使用到關於小數以及乘除法，將在下面介紹。

平衡三進位來表示十進位的整數時，長度會較十進位的數字長，但比二進位的短，且容易更改正負，不需像二進位使用一或二的補數。
舉個例子： ${\displaystyle 25_{dec}}$ , ${\displaystyle -25_{dec}}$分別改成平衡三進位表示
* ${\displaystyle 25_{dec}} = 1T×{\displaystyle 101^{1}} + 1TT×{\displaystyle 101^{0}} = {\displaystyle 10T1_{bac3}}$
* ${\displaystyle -25_{dec}} = -(1T×{\displaystyle 101^{1}} + 1TT×{\displaystyle 101^{0}} )= {\displaystyle T01T_{bac3}}$
* 其中十進位的數值正負相反時，平衡三進位數值的 $+$, $-$將會交換。

>若要表示十進位的小數，以上述的 ${\displaystyle -25.4_{dec}}$ 為例，只看小數點後面的 $4$，帶入公式後會得到 $11×{\displaystyle 101^{-1}}$，經由除法後可得到 $0.\overline{TT11}$。

### Balanced Ternary加減乘除運算的圖表

#### Addition

| + | T | 0 | 1 |
| ----- |:------|:---|:--|
| **T** | T1 | T | 0 |
| **0** | T | 0 | 1 |
| **1** | 0 | 1 |1T |

#### Subtraction

| - | T | 0 | 1 |
| ----- |:------|:---|:--|
| **T** | 0 | T |T1 |
| **0** | 1 | 0 | T |
| **1** | 1T | 1 | 0 |

#### Multiplication

| × | T | 0 | 1 |
| ----- |:------|:---|:--|
| **T** | 1 | 0 | T |
| **0** | 1 | 0 | 0 |
| **1** | T | 0 | 1 |

#### Division

| ÷ | T | 0 | 1 |
| ----- |:------|:---|:--|
| **T** | 1 |NaN | T |
| **0** | 0 |NaN | 0 |
| **1** | T |NaN | 1 |
>***注意：減法與除法並沒有符合交換律，可從圖中發現並不對稱。***

### Multi-trit addition and subtraction
1TT1TT.1TT1 1TT1TT.1TT1 1TT1TT.1TT1 1TT1TT.1TT1
+ 11T1.T − 11T1.T − 11T1.T -> + TT1T.1
-------------- -------------- ---------------
1T0T10.0TT1 1T1001.TTT1 1T1001.TTT1
+ 1T + T T + T T
-------------- ---------------- ----------------
1T1110.0TT1 1110TT.TTT1 1110TT.TTT1
+ T + T 1 + T 1
-------------- ---------------- ----------------
1T0110.0TT1 1100T.TTT1 1100T.TTT1

* 在上述例子中，可以將上面討論到的數值加減圖表內之結果代入，因此可以發現$1 + T = 0$，$T + T = 1$進位$T$，$1 + 1 = T$進位$1$。減法的計算可以將減去的數值反轉，然後相加，就能將減法計算化成加法計算，加法計算有符合交換律，較為直觀。

### Multi-trit multiplication

1TT1.TT
× T11T.1
-------------
1TT.1TT multiply 1
T11T.11 multiply T
1TT1T.T multiply 1
1TT1TT multiply 1
T11T11 multiply T
-------------
0T0000T.10T

* 乘法規則為：$1 × T = T$，$T × T = 1$，$1 × 1 = 1$，有乘到$0$的結果都為$0$。

### Multi-trit division

1TT1.TT quotient
0.5 × divisor T01.0 -------------
divisor T11T.1 ) T0000T.10T dividend
T11T1 T000<T010, set 1
-------
1T1T0
1TT1T 1T1T0>10T0, set T
-------
111T
1TT1T 1110>10T0, set T
-------
T00.1
T11T.1 T001<T010, set 1
--------
1T1.00
1TT.1T 1T100>10T0, set T
--------
1T.T1T
1T.T1T 1TT1T>10T0, set T
--------
0
* 相較於乘法，除法沒有交換律。
* 此外，(除數/2)將會被用來判斷商數的數值：
* 若算式途中被提出來除以除數的被除數> (除數/2)：商設為 $1$。
* 若算式途中被提出來除以除數的被除數< -(除數/2)：商設為 $T$。
* 若算式途中被提出來除以除數的被除數夾在(除數/2)與 -(除數/2) 之間：商設為 $0$。
* 因為與平常使用的十進位數字除法十分不同，需要花費更多時間理解。
* 若被除數與除數都為負數，如上述範例，可先轉為正數想法。例如 $T00 < T01$，照原本的思考模式會卡住，這時候把他們轉為正數再改變符號，變成 $100 > 10T$ ，可符合上述條件，故填商數1。

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

在以前，為了配合電腦的科技，所以大多使用2進位系統，2進位系統優勢在於
* 只需做到供給電流與否就能做到邏輯0，邏輯1，進而利用邏輯的安排產生出AND閘，OR閘。
* 因為結構簡單，所以二進制電路有最好的雜訊免疫能力，代表的是運作時的出錯機率能壓得很低。
他只有一條判斷標準值，超過這個值當作1，低於這個值的輸入當作0。電路上通常都是輸入電壓(5V，3.3或1.8V)代表邏輯的1，接地(0V或是接近0V)代表0。
但是各種內部外在的電磁效應以及電阻損耗等都會讓你的信號出現雜訊或是衰減。輸入的0或1往往都不是這麼理想的0或1，所以雜訊的容忍程度往往是實體電路考慮的首要條件。
* 省電。

不過，目前科技日新月異，硬體上的問題可被克服，平衡三進位的優勢就漸漸浮現了。

根據[曾經的黑科技：三進位計算機](https://kknews.cc/tech/ogl8yeq.html)一文，引用其中一段

>隨著技術的進步，真空管和電晶體等傳統的計算機元器件逐漸被淘汰，取而代之的是速度更快、可靠性更好的鐵氧體磁芯和半導體二極體。這些電子元器件組成了一個很好的可控電流變壓器，這為三進位邏輯電路的實現提供了可能，因為電壓存在著三種狀態：正電壓（「1」）、零電壓（「0」）和負電壓（「-1」）。三進位邏輯電路非但比二進位邏輯電路速度更快、可靠性更高，而且需要的設備和電能也更少。這些原因促成了三進位計算機「Сетунь」的誕生。
>原文網址：https://kknews.cc/tech/ogl8yeq.html

其實早在蘇聯時期，設備稍有進步時就有人成功研發，只是因官僚體制作祟，無疾而終。

### 平衡三進位較其他進位優秀的地方

在[reddit的討論串中](https://www.reddit.com/r/askscience/comments/3ds1oa/why_we_use_binary_numeral_system_instead_of_more/)，有人提問，為何使用二進位系統而非最有效率的 base e 系統，底下有一連串討論。
* 其中，關於 base e ，根據維基百科對於Non-integer_representation的討論：
>The base e is the most economical choice of radix β > 1 (Hayes 2001), where the radix economy is measured as the product of the radix and the length of the string of symbols needed to express a given range of values.
* 當radix β > 1時，base e會是最有效率的選擇，其中radix為指數，radix economy為指數經濟，意思是。
* 於是，根據[維基百科的radix economy頁面](https://en.wikipedia.org/wiki/Radix_economy)
>base e has the lowest radix economy
>First, note that the function
>$y = \dfrac{x}{ln(x)}$
>is strictly decreasing on 1 < x < e and strictly increasing on x > e. Its minimum, therefore, for x > 1, occurs at e.
> $E(b,N)=b log _{b}(N) = b\dfrac{ln(N)}{ln(b)}$
> Then for a constant N, $E(b,N)$ will have a minimum at e for the same reason y does, meaning e is therefore the base with the lowest average radix economy.
> Since 2 / ln(2) ≈ 2.89 and 3 / ln(3) ≈ 2.73, it follows that 3 is the integer base with the lowest average radix economy.
* 若是要在直觀與效率上做出抉擇，使用整數進位的前提下，$\dfrac{3}{ln(3)}$可以達到最接近最小值的結果。

| Base b | $Avg.E(b,N)$,N=1~43 | $Avg.E(b,N)$,N=1~5329 | $\dfrac{E(b)}{E(e)}$ |
| ----- |:------|:---|:--|
| **2** | 9.3 | 22.9 | 1.0615 |
| **e** | 9 | 22.1 | 1.0000 |
| **3** | 9.5 | 22.2 | 1.0046 |

> 與$E(e)$的比值，在N為極大數值下，為base 3 的數值最接近最小值。

### 實際案例： IOTA/Tangle

首先，從介紹IOTA的影片中，我們得知IOTA與比特幣等等所使用的架構有所不同。
IOTA使用的是tangle架構，而比特幣使用的是blockchain架構。
以下段落摘錄自[IOTA白皮書](https://hackmd.io/c/rkpoORY4W/https%3A%2F%2Fhackmd.io%2Fs%2FB1YKzhbLb%23)：
> 在一般情況下，IOTA 按如下方式運行。如前所述，不存在全域的區塊鏈，取而代之的是一個 DAG（有向無環圖），我們稱之為 Tangle。
> 通過節點發出的所有交易構成了這個 Tangle (存所有交易的帳本) 的集合。
> 這個圖的邊是這樣形成的：當一個新的交易產生，它必須驗證之前的兩個交易，這些驗證關係就通過有向的邊來表示，如圖 1 所示（在圖中，時間走向總是從左到右）。
> 如果從交易 A 到交易 B 之間沒有直接連接的有向邊，而有至少兩個有向邊的路徑存在，我們就說交易 A 間接地驗證了交易 B。另外，有一個創世交易 (genesis trasaction)，被所有交易直接或間接驗證，如圖 2。
> 創世交易有以下描述:在最一開始有一個地址 (address) 擁有全部的 token，接著創世交易會把金錢轉給其他 founder 的地址。我們強調所有的 token 皆是創世交易所產生的(不會再產生新的 token)，而且不會再有「挖礦」就可以收到金錢獎勵的概念了。
>
圖一
權重的（重新）計算

圖二
關於交易的積分計算（帶圓圈的數字）

* 沒有挖礦：比特幣之所以需要挖礦是因為那是把資訊安全所需的計算量給平分給願意跑的電腦，作為補償會給予報酬，而報酬會轉嫁到交易時所需的手續費。因此，比特幣在小額交易上十分劣勢，因為每次交易都會有不少的手續費，小額交易會讓人覺得虧。而IOTA因為把資訊安全所需的計算綁定在每個買賣身上，讓每次交易去驗證上次的兩個交易，自然不再需要額外的礦工，也省下手續費。
* scalability極佳：因為tangle的驗證模式是讓後面成立的交易方去驗證上次的兩個交易，所以使用者如果數量增加，對系統而言就是產生更多次的交易驗證，之前產生的交易也就越快被驗證。

不過這樣子看來好像無法馬上理解使用平衡三進位的必要？所以我去找了[另一個討論](https://www.reddit.com/r/CryptoCurrency/comments/6jgbvb/iota_isnt_it_the_perfect_cryptocurrency/dje8os2/)，他們的討論為為何IOTA要採用Balanced ternary ，由IOTA 基金會的創辦人 David Sønstebø 回答：
> Why ternary? As 'PuddingwithRum' has already provided a link to, ternary is the optimal radix, actually Base E (2.71....) is, but you can't make processors like that. So it comes down to Base Binary (2) vs Base Ternary (3). 3 is closer to the universal optimum 2.71 than is 2. That is the absolute most simple elevator pitch for ternary.
> The benefits of ternary go beyond mere computational performance in a parochial 1:1 comparison versus binary. Another area where ternary shines is Artificial Neural Networks, Artifical Neurons and Artificial Intelligence Logic. In fact this is actually how our brain also computes Other areas where ternary shines is in graphical processing, cryptography and search, among other things.

* 最划算的 radix 選用 base e 最好，但是處理器還沒有辦法處理 base e 的進位，所以回歸到base 2 vs base 3 。
* 上面已經討論過，base 3 最接近 base e 的效果，所以選擇 base 3 。
* 論計算能力，其實 ternary 並沒有真的大幅超越 binary ，不過因為 ternary 的思考對人類來說更為直觀，所以在神經網路、人工智慧邏輯、密碼學上會更具優勢。

此外，引用自[IOTACHINA](http://www.iotachina.com/iota)，優勢的探討：
> IOTA的量子安全是怎么来的？
IOTA使用哈希签名而不是椭圆曲线密码学（ECC）。哈希签名不仅仅在速度上胜过ECC，还能大大简化整个协议（签名和验证）。IOTA能够实现量子安全是因为我们采用了文格尼茨签名。IOTA的三进制哈希函数称为Curl（编程语言）。

* 中國的哈希 = 雜湊。也就是IOTA因為使用了雜湊簽名的方式所以效能會勝過ECC。

### 程式範例

[PyOTA: The IOTA Python API Library ](https://github.com/iotaledger/iota.lib.py/tree/master/iota/crypto/kerl)

[IOTA 2017-09-12 遭受攻擊摘要](https://hackmd.io/s/rkEg51F5b)

參考資料：
[wiki：平衡三進位](https://zh.wikipedia.org/wiki/%E5%B9%B3%E8%A1%A1%E4%B8%89%E8%BF%9B%E5%88%B6)
[wiki：Balanced Ternary](https://en.wikipedia.org/wiki/Balanced_ternary)
[百度：平衡三進位](https://baike.baidu.com/item/%E5%B9%B3%E8%A1%A1%E4%B8%89%E8%BF%9B%E5%88%B6#1_3)
[IOTA問答論壇](https://www.reddit.com/r/Iota/comments/73w6i7/why_ternary_arithmetic_in_iota_by_using_a_ternary/)
[知識+：關於二進位](https://tw.answers.yahoo.com/question/index?qid=20050610000011KK09056)
[二進位的優勢討論](https://forum.gamer.com.tw/C.php?bsn=60433&snA=27409)
[三進位計算機](https://kknews.cc/tech/ogl8yeq.html)
[reddit:askscience討論：為何不用最有效率的 base e 系統](https://www.reddit.com/r/askscience/comments/3ds1oa/why_we_use_binary_numeral_system_instead_of_more/)
[Non-integer_representation wiki](https://en.wikipedia.org/wiki/Non-integer_representation)
[IOTA/TANGLE白皮書](https://iota.org/IOTA_Whitepaper.pdf)
[IOTA BREAKDOWN: The Tangle Vs. Blockchain Explained](https://www.youtube.com/watch?v=I_jNH9BlEEo)
[IOTA介紹](http://www.iotachina.com/iota)
[Tangle白皮書](https://hackmd.io/c/rkpoORY4W/https%3A%2F%2Fhackmd.io%2Fs%2FB1YKzhbLb%23)
[How exactly is IOTA going to be infinitely scalable?](https://www.reddit.com/r/Iota/comments/6h0nvn/how_exactly_is_iota_going_to_be_infinitely/)
[IOTACHINA](http://www.iotachina.com/iota)
* 因為本身為簡體中文網站，引用為求精確與尊重原作所以並無簡轉繁