# 2017 q3 Homework1 (作業區)
contributed by < `williamchangTW` >
###### tags: `Class_Project`, `Jserv`
> 注意格式，特別是該空白的地方。開發的紀律和對細節的重視，是我們強調的議題之一
> [name="jserv"][color=red]

### Reviewed by`vonchuang`
* "有趣的是只要簡化後有 0 就能被 3 整除"，此描述應有誤，如 8 為 +0-，有 0 卻無法被 3 整除
* "當 x > e , 值會向上低增"，錯字
* 在介紹 IOTA 時，部分英文與中文間沒有以空白相隔
* 程式執行結果應以文字表示之，而非圖形
* "再來我在用 2^63 輸入去測試"，數字部分的 Latex 沒寫好
* "平均表達位元較少意味著運算效能的提升，(註：這裡跟Ternary logic 有關)"，可再更詳盡的介紹
* 引用他人圖片應註明來源
* [Debug overflow](https://github.com/williamchangTW/balanced-ternary/commit/be044095b96838b486395cb651112172edfa565f) 這份 git commit 可再寫的詳盡些

## Balabced Ternary 研讀
### Balance Ternary 原理解析 :
---
- 是 Base on 3 ，可以表達所有整數，且在 Base 整數中為最低的整數，在應用上有許多好處，在相同十進位下可以比 Binary **表達位元更少**。
- 研讀 Balance ternary 的了解，與二進制差別在於有許多計算上的優勢，因為有了正負號的使用減少在乘法上進位速率，分號 Round rate 亦降低。
- Ternary 轉變成只用三個符號表示 - 、 + 、 0 來做運算，比如 ：
> ==45 = 0 * 3^0^ + 0 * 3^1^ + (-1) * 3^2^ + (-1) * 3^3^ + 1 * 3^4^==
>==-45 = 0 * 3^0^ + 0 * 3^1^ + 1 * 3^2^ + 1 * 3^3^ + (-1) * 3^4^==
>==13 = 1 * 3^0^ + 1 * 3^1^ + 1 * 3^2^==
>==-13 = (-1) * 3^0^ + (-1) * 3^1^ + (-1) * 3^2^==

- 依照上面的 decimal -> ternary 的運算式中，正負數間的轉換，只需做反向（ＮＯＴ）運算，則可簡化成 - ， + ， 0，且有趣的是只要簡化後有 0 就能被 3 整除。

> ==45 = 0 0 - - +==
> ==-45 = 0 0 + + -==
> ==13 = + + +==
> ==-13 = - - -==
> 即做ＮＯＴ運算

- 為何能表達所有的整數，我思考了一下，跟 Bianry 有點相關的一點是，都有==1 (即 3^0^ = 1 = 2^0^)== 只要這樣就能表達所有的**基數**及**偶數**，因為2在指數為整數的情況下皆為偶數，多了個2^0^可表達基數，同理可證在 Ternary 的式子上。
#### IOTA & Ternary Jinn {%youtube EbJMtJq20NY %}
https://www.reddit.com/r/CryptoCurrency/comments/6jgbvb/iota_isnt_it_the_perfect_cryptocurrency/#dje3bh7
>考慮片中的 4:20 的問題，需要多少 digit 去呈現所有整數
算式：
E(b,N) = b [log~b~(N)+1]
這裡稍微解釋一下：
$$
radix economy funtion : y = {x \over ln(x)}
$$
當 x = 1 , 值 = infinity
當 x > e , 值會向上低增
以下是驗算:
$$
infinity = {1 \over ln(1)}
$$
$$
(x=2):2.8853 \approx {2 \over ln(2)}
$$
$$
當(x=3)擁有最小值: 2.7307 \approx {3 \over ln(3)}
$$
$$
(x=4):2.8854 \approx {4 \over ln(4)}
$$
結論 Radix 為 3 較於 2 優


---
### Balanced Ternary 解決什麼問題 ＆ 應用實例探討
- [Soviet machine - balanced ternary machine](https://dev.to/buntine/the-balanced-ternary-machines-of-soviet-russia)在看完其內容後，知道它是 Stack machine ，是應用Balance ternary 實例之一。
- [IOTA/Tangle](https://iota.org/IOTA_Whitepaper.pdf)從題目知道這是應用實例，以下對這個議題做探討：
- 可以參考此連結 [IOTA & blockchain](https://blog.iota.org/a-primer-on-iota-with-presentation-e0a6eb2cc621)
- [IOTA](http://www.tangleblog.com/2017/01/25/the-tech-behind-iota-explained/)裡頭解釋到 **IOTA** 優點是**可擴展性、量子安全、迅速**，有別於 blockchain 使用 Tangle(DAG) ，先探討文中提到了 [DAO](http://www.ithome.com.tw/news/107405)被駭客攻擊盜走了 370W Ethereum 乙太幣，其構成的方式像是 **Bitcoin** 相似，是以 **Blockchain 為基底所構成**，為一種**共享式資料庫**，採**分散式技術**，資料散布於各區塊資料，無法被**單一實體掌控，並且採分散式共識演算法，解決同步問題，且交易資料安全、透明，可永久記錄無法被竄改**。

**這是各種的節點溝通概略圖分別是集中式、分散式與網狀式， Tangle 建構類似於第三種的方式**
**這是 blockchain 與 Tangle(Blockchainless) 之間的差異**

- 最後針對 [Tangle 白皮書](https://hackmd.io/s/B1YKzhbLb)
做最後的結論探討，**Tangle**為一種 DAG (Directed Allocated Graph)
- 從交易點切入，知道他不像Bitcoin可以挖礦挖到獎勵，有一個節點 **(Genesis trasaction)** 能被所有節點間接或直接的驗證，擁有所有 Token 再藉由此點把資金轉向其他 founder 的 address，當發起一筆交易，node需要作下列動作：
- 選擇兩筆交易驗證
- 檢查是否有衝突
- 交易要合法必須解密，與挖礦相似，找出一個 **特定點 (nonce)** 與其他驗證資料 hash 值為相同格式
- 若有交易 **不合法**，經由 Tip selection algorithm 驗算其 **信心值** 確定是否要孤立哪個點
- 可以與前文呼應為何 **IOTA** 多了這麼多好處

### 為何 IOTA 要用 Ternary
- [Why is iota ternary](https://www.reddit.com/r/CryptoCurrency/comments/6jgbvb/iota_isnt_it_the_perfect_cryptocurrency/#dje3bh7)，這個連結的文章提到，**為何是 Ternary** ，一開始有三位元的想法只是苦於沒有相關處理器可用，而最後也呼應了前面的解說，用 Balance ternary 是因為 **Radix economy**，以下解說：
- Radix economy 在 base on 3 的情況下能表現的所需位元數最少
- Ternary 能表示的範圍較大，2^n^ < 3^n^ 能表示的範圍，在 IOTA 用 Tangle 下也剛好符合其需求，Scalability up
- 平均表達位元較少意味著運算效能的提升，(註：這裡跟Ternary logic 有關)

### 加密貨幣實例應用

### 對現有的工具開發

## Github fork balanced-ternary 分析需求及修改

- 從 Github fork 出來專案後，發現其規律
>如下所示：
其規律從下面中間邊上開始做**順時鐘**的增加一個點，當那個 base on 3 的位元被 raise 後就做出反應，當為負數則反向顯示，而正方形表示當 **4 (edge) + 4 (cornor) = 8，我推測能表示到 3^8^ -1**。[color=yellow]
>>有趣的事情發生了，當大於 3^8^ - 1 = 3280 後，圖形表示就一直呈現全開。

- 因為上述的事情，讓我想去測試他的極限，果然在大於 **(2^31^ = 2147483648) + 1** 做到了收斂呈現最負的狀態，可是這樣的呈現並不符合邏輯應該呈現全開的樣子。
- 在這個測試中當然也有做負數測試產生一樣的結果，在 -(2^31^+1) 呈現全開圖示，有些機器會呈現 **Memory segment fault(core dump)** ...之類的記憶體區段錯，因為它超過他在該記憶體的區段位置出現錯誤會請 O.S 出來處理。
- 對於這個點在程式中，我加入了一段程式，判斷是否超出 (2^31^-1) ~ (-2^31^-1)，若超出則用 **最大值(最小值)** 做最終值，以致不會發生錯誤。
~~~c=
under scanf("%d", &src);
I add "if(...) else if (...)"
------------------------

if (src >= 3280)
src = 3280;
else if (src <= -3280)
src = -3280;
~~~
- 可是這樣的想法等於什麼都沒做，輸出還是沒有改變，當輸入大於 2^31^+1 時，還是出現不可預期的錯誤。有鑑於此我測試了一下，使用 printf 去測試 src 內的值，當我輸入 2^31^+1 中的直輸出作後續的程式判斷。
~~~c=
printf("%d\n",src);
~~~

- 可看出當我輸入 2^31^+1 呈現出來的是我設置區間的最小值。然後我寫了一段小程式去測試
~~~c=
#include <stdio.h>

int main(){
int s = 0;
long int i = 0;
scanf("%d %ld", &s, &i);
printf("%d\n %d\m %ld\n %ld\n", s, i, s, i);
return 0:
}
~~~
- 這裡我拿第一個拿 2^31^+1 做輸入，很明顯的出現全部顯示正常的值。再來我在用 2^63 輸入去測試，很明顯的 %d 呈現的字皆為 Overflow 而 %ld 呈現的不會超過 2^63^ 。
- 對於 4294967295 做解釋，是 %d 的最大值表示從 (-2147483648~2147483648)，要減一表示把多算進來的零刪掉。
$$
2147483648 + 2147483648 - 1 = 4294967295
$$

- 這個圖，我去測試有 scanf 即單純 printf 出來的數值一不一樣，最後發現兩者的值不一樣，證明 scanf 做了數值上的轉變，超出預設數值呈現 -1 ，如上圖所示。

- 有鑑於此，我把一些程式碼改了一下，讓他不要 Overflow。
~~~c=
static long int src = 0; /* int -> long int */
----------------------------------------------
scanf ("%ld", &src); /* %d -> %ld */
----------------------------------------------
~~~
經過上面修改過後，不會出現當一個非常大的值輸入後出現一個極小值狀態。