$2017q3 \ Homework1(ternary)$
===
contributed by <`TsengWen`>
###### tags: `Balanced Ternary`
---
### Review by `williamchangTW`
- 在文章中提到的，設計中有避掉一些容易混淆的字，推測考量到資訊安全問題，這是我在研究中沒有窺見的一隅，受教了謝謝
- 或許可以針對上述的想法繼續往下個議做延伸，應該是一個可以完成的部份，期待您的討論
>小弟坐井觀天，如有冒犯請見諒[name="williamchangTW"]
---
## 作業要求
1. 研讀 Balanced Ternary，並依據 課前測驗參考解答: Q1 的風格和探討方式，涵蓋以下:
- [x] 解釋 Balanced Ternary 原理;
- [ ]Balanced Ternary 的設計要解決什麼類型的問題，需要詳述實際應用案例 (如 IOTA/Tangle)。提示：從算術表達的精準度和空間使用效率去探討;
- [ ] 針對特定的領域 (如加密貨幣)，列出在 GitHub 裡頭可找到的應用案例，不僅列出程式碼，還要解說;
- [ ]在研究的過程中，應該會對既有工具進行修改或者重新開發 (不限程式語言)，也該一併指出，程式碼應該維護在 GitHub 上;
2. 其他:
## $Balanced\ Ternary$
>數字與中文間記得以空白隔開!
>[name=課程助教][color=red]
>>ok
>>[name=TsengWen][color=#7affef]
### 平衡三進位:
是一種以 3 為基數，-1、0、1 為基本數位的進位。
#### 特點
1. 由於 -1 的引入，這種進位不需要額外的符號就能直接表示負數。正因為這一點，使得平衡三進位在加減法和乘法方面的效率要比二進位高。
2. 各位上的數字之和為偶數的整數是偶數；各位上的數字之和為奇數的整數是奇數。
##### 例如 :
$$\ + = \ 1\\
0 \ = 0\\
\ - = -1\\
$$
---
$$
42 = \begin{matrix}
3^4 & 3^3 & 3^2 &3^1&3^0&\\
+ & - & - &- &0 \\
81 & -27 & -9 &-3&+\ 0\\
\end{matrix}
$$
---
$$
平衡三進位
$$
>下兩個表格請改以縱向的表格表示，或是切成上下兩部分，塞在一起會超出畫面
>[name=課程助教][color=red]
>>OK[name=TsengWen][color=#7affef]
\begin{array}
{c|c|c|c|c|c|c|c|c|c|c}
\ 十進位 &-9&-8&-7&-6&-5&-4&-3&-2&-1 \\
\hline \\平衡三進位
&-00
&-0+
&-+-
&-+0
& -++
& 0--
& -0-
& 0-+
& 00-
\end{array}
\begin{array}
{c|c|c|c|c|c|c|c|c|c|c}
\ 十進位 &9&8&7&6&5&4&3&2&1 \\
\hline \\平衡三進位
&+00
&+0-
&+-+
&+-0
& +--
& 0++
& 0+0
& 0+-
& 00+
\end{array}
- 觀察發現：正負號轉換只需將 + 轉 - 和 - 轉 +
相較原本2's complement 反向 再加一 ，或許能夠少去加一的步驟。
---
#### 小數
平衡三進位和十進位一樣，用小數點分隔整數部分和小數部分。
\begin{array}
{c|c|c|c|c|c|c|c|c|c|c}
\ 十進位 &-0.5&-0.4&-0.3&-0.2&-0.1 \\
\hline \\平衡三進位
& 0.\overline{-}或-.\overline{+}
& 0.\overline{--+\ +}
& 0.\overline{-\ 0+0}
& 0.\overline{-++\ -}
& 0.\overline{0-0\ +}
\end{array}
\begin{array}
{c|c|c|c|c|c|c|c|c|c|c}
\ 十進位 &0.5&0.4&0.3&0.2&0.1 \\
\hline \\平衡三進位
& 0.\overline{+}或+.\overline{-}
& 0.\overline{++-\ -}
& 0.\overline{+\ 0-0}
& 0.\overline{+--\ +}
& 0.\overline{0+0\ -}
\end{array}
- 驗算0.5的兩種表示
- $0.\overline{+}$
$$\frac{1}{3}+\frac{1}{9}+\frac{1}{27}+\frac{1}{81}\ldots=\frac{\frac{1}{3}}{1-\frac{1}{3}}=\frac{\frac{1}{3}}{\frac{2}{3}} =\frac{1}{2}$$
- $+.\overline{-}$
$$1-\frac{1}{3}-\frac{1}{9}-\frac{1}{27}-\frac{1}{81}\ldots=1-(\frac{1}{3}+\frac{1}{9}+\frac{1}{27}+\frac{1}{81}\ldots)=1-\frac{1}{2}=\frac{1}{2}$$
---
#### 運算
\begin{array}{c|lcr}
\ + & - & 0 & +\ \\
\hline
\ - & +- & + & 0\ \\
0 & \ + & 0 & -\ \\
\ + & \ 0 & - & -+
\end{array}
\begin{array}{c|lcr}
\ * & - & 0 & + \\
\hline
\ - & + & 0 & - \\
0 & 0 & 0 & 0 \\
\ + & - & 0 & +
\end{array}
## $Ternary$
### 單位
- 位(trit) ----> 0,1,2
- 位元組(tryte) ----> 9-trit
- 字元(word) ----> 27-trit
### 範圍
- 一個word - 表達 $3^{27}$ = $7,625,597,484,987$值
### Heptavintimal Encoding of Ternary Values
- 為了讓人們方便使用Ternary Number，美國愛荷華州立大學將Ternary Number轉換成九進制或是二十七進制，像是將Binary Number轉換成octal(base 8)或是hexadecimal(base 16)。
- 其中跳過容易視覺混淆的字母
\begin{array}{c|c}
\ input&equivalent \\
\hline
\ I, J, L, Y & 1 \\
\ O, Q & 0\\
\ S & 5 \\
\ U, W & V \\
\end{array}
### 浮點數
- 因為balance ternary的特性，可以不須額外trit來表示正負符號。
- 給定一個27-trit word 表示浮點數，由3個tryte所組成，使用1個tryte表示指數。
- 指數部分，使用3's complement來表示。
- 不使用隱藏位元
## Fast Ternary Multiplication and Division
### 乘法
$$在不假設特殊硬體架構下，將數表示成\ \ \ a = (a<<_3 c) + d\\
<<_3 為向左位移一個trit$$
---
\begin{array}{l|l}
a\ \times 0 = 0 & a\ \times 15 = (a\ \times 5 )\times 3 \\
a\ \times 1 = a & \\
\ & a\ \times 16 = (a\ \times 4 )\times 4 \\
a\ \times 2 = (a<<_3 0) \ +\ a \\
a\ \times 2 = (a<<_3 1) \ -\ a & t\ = a\ \times 8 \\
\ & a\ \times 17 = (a<<_3 2) \ +\ t \\
a\ \times 3 = (a<<_3 1) \\
a\ \times 4 = (a<<_3 1) \ +\ a &a\ \times 18 = (a\ \times 6 )\times 3 \\
\ \\
t\ = a\ \times 2 & t\ = a\ \times 2\\
a\ \times 5 = (a<<_3 1) \ +\ t & a\ \times 19 = (t<<_3 2) \ +\ a\\
\ \\
a\ \times 6 = (a\ \times 2 )\times 3 & a\ \times 20 = (a\ \times 10 )\times 2\\
\ \\
t\ = a\ \times 2 &a\ \times 21 = (a\ \times 7 )\times 3\\
a\ \times 7 = (t<<_3 1) \ +\ a \\
\ & a\ \times 22 = (a\ \times 11 )\times 2\\
a\ \times 8 = (a<<_3 2) \ -\ a \\
a\ \times 8 = (a\ \times 2 )\times 4 & t\ = a\ \times 2\\
\ & u=(a<<_3 1)\ +\ t\\
a\ \times 9 = (a<<_3 2)&a\ \times 23 = (t<<_3 2) \ +\ u\\
\ \\
a\ \times 10 = (a<<_3 2) \ +\ a & a\ \times 24 = (a\ \times 6)\times4\\
\ \\
t\ = a\ \times 2 & a\ \times 25 = (a\ \times 5 )\times 5 \\
a\ \times 11 = (a<<_3 2) \ +\ t \\
\ & a\ \times 26 = (a\ \times 2 )\times 13\\
a\ \times 12 = (a\ \times 3 )\times 4\\
\ \\
t\ = a\ \times 4 \\
a\ \times 13 = (a<<_3 2) \ +\ t \\
\end{array}
## 除法
將除法轉換成乘一個對應的數。
\begin{array}{l}
\frac a2 = a × \frac12 = a × 0.11\overline1_3 \\
\frac a3 = a × \frac13 = a × 0.1_3 \\
\frac a4 = a × \frac14 = a × 0.0202\overline{02}_3 \\
\frac a5 = a × \frac15 = a × 0.01210121\overline{0121}_3 \\
\frac a6 = a × \frac16 = a × 0.011\overline1_3 \\
\frac a7 = a × \frac17 = a × 0.\overline{010212}_3 \\
\frac a8 = a × \frac18 = a × 0.0101\overline{01}_3 \\
\frac a9 = a × \frac19 = a × 0.01_3 \\
\frac a{10} = a × \frac1{10} = a × 0.0022\overline{0022}_3
\end{array}
### 參考網站
- [平衡三進位 - 維基百科，自由的百科全書](https://zh.wikipedia.org/wiki/%E5%B9%B3%E8%A1%A1%E4%B8%89%E8%BF%9B%E5%88%B6)
- [The ternary computer](http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=5176262)
- [Standard Ternary Logic](http://homepage.cs.uiowa.edu/~jones/ternary/)
- [Ternary Data Types for C Programmers](http://homepage.cs.uiowa.edu/~jones/ternary/libtern.shtml)
- [Arithmetic with Binary-Encoded Balanced Ternary Numbers](http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6810470)
## $\LaTeX$
- 是一種基於TEX的排版系統，適用於生成高印刷品質的科技和數學、化學類文件。
### MathJax語法
可以使用 **MathJax** 語法 來產生 *LaTeX* 數學表達式：
The *Gamma function* satisfying $\Gamma(n) = (n-1)!\quad\forall n\in\mathbb N$ is via the Euler integral
$$
x = {-b \pm \sqrt{b^2-4ac} \over 2a}.
$$
> 更多關於 **LaTeX** 數學表達式 [請至這裡](http://meta.math.stackexchange.com/questions/5020/mathjax-basic-tutorial-and-quick-reference)
### 參考網站
- [Latex in Ubuntu](http://pangomi.blogspot.tw/2012/11/latex-in-ubuntu.html)
- [語法教學](http://www.cs.nthu.edu.tw/~cherung/teaching/2009cs5321/link/latex.pdf)
Sign in with Wallet
Connect another wallet