ternary
===
contributed by < `loolofen`,`shanshow` >
# 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}$。
>
根據 economical radix 爭對 radix 及 width 測量(下圖)，在所有數字系統中以 $e$ 經濟效益最高，不過在現實中要如何在表示 Base $e$ 是很困難的，所以只能找相近的數字，其中以 Base 3最接近，所以其實 Base 3是比 Base 2還來得更有經濟效益的。
### 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 的數值最接近最小值。
### [台灣證交所異常熔斷](https://hackmd.io/s/B1eo44C1-)
* 原本台灣證券交易所內部系統中，紀錄股票交易價格的變數類型為 32-bit 的無號整數，有效範圍是介於 0 至 4,294,967,295之間。
* 然而證交所股票交易變數的設計會事先預留小數點後三位，比方說公司股票為 10 元，系統則會將其標註為 10.000 元，又方便系統進行整數運算，還會額外乘上 1000 倍，也就是說內部儲存 10000。
* 浮點數能夠表達出比整數更為寬廣的空間，但是準確度相對之下不算高，例如 0.1 + 0.2 = 0.30000000000000004
* 股票交易中時常出現兩方匯率不同貨幣的轉換，因此需使用到浮點數方可進行捨入的計算。
* 如果系統發現上下波動超過 3.5％，此時便會暫停交易撮合 2 至 3 分鐘。為了進行比較，交易系統會將股票交易價格變數的值乘上 1 + 3.5％ 來計算。但為避免因浮點數值運算而產生誤差，交易系統還會將處理數值乘上 1000 倍，也就說，實際乘法 1035 倍，而非僅是乘以 103.5%。
* 因此，假設股票上揚到 4150 元，經過相乘，股票交易價格變數所儲存的數值已經到達 4,295,250,000，後者已經超過前述 32-bit 無號整數的上界，進而產生溢位。
* 若是改以平衡三進位，給予相同 bit 數，進行計算，上述溢位將不會發生。
### 實際案例： 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。
#### IOTA 術語
| Term | Definition | Reference |
| -----| ---------- | --------- |
| Tangle |A directed acyclic graph (DAG) as a distributed ledger which stores all transaction data of the IOTA network. It is a Blockchain without the blocks and the chain (so is it really a Blockchain?). The Tangle is the first distributed ledger to achieve scalability, no fee transactions, data integrity and transmission as well as quantum-computing protection. Contrary to today’s Blockchains, consensus is no-longer decoupled but instead an intrinsic part of the system, leading to a completely decentralized and self-regulating peer-to-peer network.|[iota INSTRODUCTION](https://iota.readme.io/v1.2.0/docs/glossary)|
|Tips|transactions which have no other transactions referencing them.|[iota INSTRODUCTION](https://iota.readme.io/v1.2.0/docs/glossary)|
|Curl|The main hash function used in IOTA, Curl is based on well-studied sponge construction invented by the Keccak creators (SHA-3), and is specifically tailored for IoT, that also happens to be the world’s first trinary hash function.|[iota INSTRODUCTION](https://iota.readme.io/v1.2.0/docs/glossary)|
|Kerl|as Curl is a young hash function, IOTA currently uses Keccak (SHA-3) for signing. Kerl is Keccek-384, with additional conversion of its input and output from/to 243 trits to 48 bytes using basic two’s complement.|[iota INSTRODUCTION](https://iota.readme.io/v1.2.0/docs/glossary)|
|Winternitz one-time signature (W-OTS)| a Post Quantum Signature scheme, that is used to authorize spending from an address in IOTA (sign with your private key). Due to it's one-time nature, the security of funds in an address decreases rapidly if you sign multiple transactions using the same key. Therefore, in IOTA you never re-use an address that has been spent from (as one signature has already been shared with the network).|[iota INSTRODUCTION](https://iota.readme.io/v1.2.0/docs/glossary)|
|IOTA the token| Total supply - There are 2,779,530,283,277,761 IOTAs(280萬GI)、Units - IOTA notation follow SI units. Pi, Ti, Gi, Mi, Ki, i - more info|[iota INSTRODUCTION](https://iota.readme.io/v1.2.0/docs/glossary) |
| IRI | 全稱 IOTA Reference Implementation，以 Java 撰寫，為目前唯一可完整運行 Protocol 的 IOTA Node，基本上架設節點的話會使用 IRI 來用。作為 Reference Implementation，其餘的 Implementation 應該遵照 IRI 的行為來實做。 | [iota INSTRODUCTION](https://iota.readme.io/v1.2.0/docs/glossary) |
| iota.lib.* | The IOTA library, it has all the necessary functionality to fully use IOTA, including sending transactions, cryptography-related functions and the core API. iota.lib.js is the most established and used library currently.| [iota INSTRODUCTION](https://iota.readme.io/v1.2.0/docs/glossary) |
#### IOTA 特點
引述[如何向企业和研发人员介绍iota](https://forum.iota.org/t/iota/1289)
>首先你要记住IOTA的六个要点：
1） IOTA是为IoT而设计的区块链技术（分布式账本技术）。
2） 在感应器之间的去中心化数据交易/传输和代币支付。
3） 小微支付以及零数据交易和支付费。
4） 有助于把所有物件都归纳入分享经济之中。
5） 可扩容的分布式账本。
6） 加密信息传递和隐秘代币支付。
#### IOTA 使用 TERNARY
參考 [st9007a](https://hackmd.io/s/rJv_CTmsb)共筆 來源 : [iota library](iota.lib.js/lib/crypto/converter/converter.js)
```clike=
// All possible tryte values
var trytesAlphabet = "9ABCDEFGHIJKLMNOPQRSTUVWXYZ"
// map of all trits representations
var trytesTrits = [
[ 0, 0, 0],
[ 1, 0, 0],
[-1, 1, 0],
[ 0, 1, 0],
[ 1, 1, 0],
[-1, -1, 1],
[ 0, -1, 1],
[ 1, -1, 1],
[-1, 0, 1],
[ 0, 0, 1],
[ 1, 0, 1],
[-1, 1, 1],
[ 0, 1, 1],
[ 1, 1, 1],
[-1, -1, -1],
[ 0, -1, -1],
[ 1, -1, -1],
[-1, 0, -1],
[ 0, 0, -1],
[ 1, 0, -1],
[-1, 1, -1],
[ 0, 1, -1],
[ 1, 1, -1],
[-1, -1, 0],
[ 0, -1, 0],
[ 1, -1, 0],
[-1, 0, 0]
];
/**
* Converts trytes into trits
*
* @method trits
* @param {String|Int} input Tryte value to be converted. Can either be string or int
* @param {Array} state (optional) state to be modified
* @returns {Array} trits
**/
var trits = function( input, state ) {
var trits = state || [];
if (Number.isInteger(input)) {
var absoluteValue = input < 0 ? -input : input;
while (absoluteValue > 0) {
var remainder = absoluteValue % 3;
absoluteValue = Math.floor(absoluteValue / 3);
if (remainder > 1) {
remainder = -1;
absoluteValue++;
}
trits[trits.length] = remainder;
}
if (input < 0) {
for (var i = 0; i < trits.length; i++) {
trits[i] = -trits[i];
}
}
} else {
for (var i = 0; i < input.length; i++) {
var index = trytesAlphabet.indexOf(input.charAt(i));
trits[i * 3] = trytesTrits[index][0];
trits[i * 3 + 1] = trytesTrits[index][1];
trits[i * 3 + 2] = trytesTrits[index][2];
}
}
return trits;
}
```
### 程式範例
#### b3k程式碼探討：(參考[yuan922同學之共筆](https://hackmd.io/BwMwbArAJjDMC0B2ADBE8AsGCcj4CNgAmDeAY0QwEMjLgyiwMg==))
```clike=
/* Pictures of zero, largest positive and largest negative numbers. */
static const char *pat = "┌───┐\n"
"│ │\n"
"└───┘\n"
"├─┴─┤\n"
"┤ ├\n"
"├─┬─┤\n"
"┌┬┬┬┐\n"
"├ ┤\n"
"└┴┴┴┘\n";
#define SZD 8
#define SZP 42
```
* 此段程式碼畫出了 0 、最大正值、最大負值情形的圖案。
```clike=
for (r = 0; r < SZD; ++r) {
p = &digit[r];
p->exp = r ? (3 * digit[r-1].exp) : 1;
p->val = 0;
}
```
* 此段程式碼中，從 r = 0 的情形開始， p = &digit[0] 。
#### 補充 指標常數與變數：
* [之前的作業](https://hackmd.io/KYBghuBMoLQGYHY4BYbJATgCYwEaWQGYYtNIMBjCgVi3ISA=)中有遇到指標常數與指標變數的差異探討
* 根據測試，陣列作為指標常數，在決定好儲存位址後將不可手動改變，強行搬動會造成錯誤；而指標變數則可以自由地更改記憶體位址。
* 因為程式內含有 p = &digit[r] ，將指標 p 改成 digit[r] 的位址，在此回顧與複習。
####
* p->exp = r ? (3 * digit[r-1].exp) : 1; 因為 r = 1 所以 p->exp = 3 * digit[r-1].exp
* r 最初為 0 ，所以在程式碼第三行， p->exp 的判斷式 r ? (3 * digit[r-1].exp) : 1 最初結果必為 1
* 因此 p->exp = 1 ， 且根據上面的第一行敘述，這時候 p = &digit[0]
* 得出 digit[0].exp = 1。
* 將上述程式改動，試試看不同的 r 下所 print 出的 p->exp 與 digit[r].exp 是否相同。
```clike=
for (r = 0; r < SZD; ++r) {
p = &digit[r];
printf("第 %d 次\n",r+1);
printf("expBefore:%d r:%d \n",p->exp,r);
printf("(digit)expBefore:%d r:%d \n",digit[r].exp,r);
p->exp = r ? (3 * digit[r-1].exp) : 1;
printf("expAfter: %d r:%d \n",p->exp,r);
printf("(digit)expAfter: %d r:%d \n\n",digit[r].exp,r);
p->val = 0;
}
```
產出結果如下：
```
第 1 次
expBefore:0 r:0
(digit)expBefore:0 r:0
expAfter: 1 r:0
(digit)expAfter: 1 r:0
第 2 次
expBefore:0 r:1
(digit)expBefore:0 r:1
expAfter: 3 r:1
(digit)expAfter: 3 r:1
第 3 次
expBefore:0 r:2
(digit)expBefore:0 r:2
expAfter: 9 r:2
(digit)expAfter: 9 r:2
第 4 次
expBefore:0 r:3
(digit)expBefore:0 r:3
expAfter: 27 r:3
(digit)expAfter: 27 r:3
第 5 次
expBefore:0 r:4
(digit)expBefore:0 r:4
expAfter: 81 r:4
(digit)expAfter: 81 r:4
第 6 次
expBefore:0 r:5
(digit)expBefore:0 r:5
expAfter: 243 r:5
(digit)expAfter: 243 r:5
第 7 次
expBefore:0 r:6
(digit)expBefore:0 r:6
expAfter: 729 r:6
(digit)expAfter: 729 r:6
第 8 次
expBefore:0 r:7
(digit)expBefore:0 r:7
expAfter: 2187 r:7
(digit)expAfter: 2187 r:7
```
* p->exp 與 digit[r].exp 值將會相同
* exp 的值將以 $3^n$ 的形式變化， $n >=0$
```clike=
/* Truncate to the largest allowed positive. */
p = &digit[SZD - 1];//SZD = 8, then digit[8 - 1] = 2187
r = 3 * p->exp / 2;
if (src > r)
src = r;
else
r = src;
```
* r 的最大值為 $\dfrac{3\times2187}{2}=3280.5$， src 超過的話自身會變成 r
```clike=
/* Like 'echo "obase=3; $src" | bc'. */
do {
while (r < p->exp)
--p;
r -= p->exp;
++p->val;
} while (r);
```
* 先假設 r = 20 ，代入後推演過程：
* 因為 r > 0 ，觸發 do ，執行下面程式碼。
* --p 後 p->exp 的值為何？進行 print 的觀測：
```clike=
/* Like 'echo "obase=3; $src" | bc'. */
//Test
do {
while (r < p->exp)
{
printf("pTest1: %d \n",p->exp);
--p;
printf("pTest2: %d \n",p->exp);
}
r -= p->exp;
++p->val;
} while (r);
```
* 得到的成果如下：
```
pTest1: 2187
pTest2: 729
pTest1: 729
pTest2: 243
pTest1: 243
pTest2: 81
pTest1: 81
pTest2: 27
pTest1: 27
pTest2: 9
pTest1: 9
pTest2: 3
pTest1: 3
pTest2: 1
pTest1: 1
pTest2: 0
```
* p 的型態是指標，而且是指標變數，C 語言中指標以記憶體的位址來表示， 因此指標可以做加減的運算。
* [丁培毅教授撰寫的教學](http://squall.cs.ntou.edu.tw/cprog/materials/Pointers.html)中有以下範例：
```clike=
int x[20];
int *xPtr;
xPtr = &x[0]; // 也可以用 xPtr = x; 假設 xPtr 內的資料為 A000
xPtr++; // 也可以用 xPtr = xPtr + 1; 此運算完成後 xPtr 內之資料為 A002
// 剛好為變數 x[1] 之位址
xPtr = xPtr + 10; //此運算完成後 xPtr 內之資料為 A016，剛好為
// 變數 x[11] 之位址
```
* 而 p 位址移動後等同 digit[r] 的位址改變了，因此可以發現 p->exp 數值會被除 3 。
* while 迴圈會執行到 2187 被遞減成 $3^n<20$ 中 $3^n$ 的最大值 = 9
* 接著 r -= p->exp ，r = 20 - 9 = 11
* ++p->val ，意思是 在 p->exp = 9 的 p 所指向的 val 值 + 1。
* 11 對應到 $3^n<11$ 中 $3^n$ 的最大值 = 9 ， r = 11 - 9 = 2。
* 在 p->exp = 9 的 p 所指向的 val 值 + 1。
* 2 對應到 1 ， r = 1 。
* 在 p->exp = 1 的 p 所指向的 val 值 + 1。
* 1 對應到 1 ， r = 0 。
* 在 p->exp = 1 的 p 所指向的 val 值 + 1。
* 0 ，跳出迴圈。
* **這代表 20 這個數值可以表示成 $2\times3^2+2\times3^0$**
```clike=
/* Convert to the balanced form. */
while (p < &digit[SZD]) {
if (r)
++p->val;
r = p->val > 1;
if (r)
p->val -= 3;
p->val *= inv;
++p;
}
```
* 上述式子會將值轉換為 $bal_3$ 形式，試著把 20 轉換。
1. 一開始 r = 0 ，跳到第4行，因為 exp = 3 的 val = 2 > 1，所以 r 為 true ，p->val - 3 = -1 (T)， 結束 $3^0$ 項目，把 p->val 存到 inv 後 p++ ，進行下一輪 $3^1$。
2. 上一輪 r 為 true ， p->val + 1 = 1 (1)， r 變為 false ，進行下一輪 $3^2$
3. 上一輪 r 為 false ，跳到第四行， p->val = 2 > 1 ， r 為 true ， p->val - 3 = -1 (T)，進行下一輪 $3^3$。
4. 上一輪 r 為 true ，p->val + 1 = 1 (1) ， r 為 false ，跳到第七行， p + 1 ，但接下來的 r 會一直為 false ，導致 p->val 也不會再增加，直到 p 的大小突破上限，停止 while 迴圈。
**最後得到 1T1T 。**
[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)
* 因為本身為簡體中文網站，引用為求精確與尊重原作所以並無簡轉繁
Sign in with Wallet
Connect another wallet