$2017q3Homework1(ternary)$

contributed by <TsengWen>

tags: Balanced Ternary

---

Review by williamchangTW

• 在文章中提到的，設計中有避掉一些容易混淆的字，推測考量到資訊安全問題，這是我在研究中沒有窺見的一隅，受教了謝謝
• 或許可以針對上述的想法繼續往下個議做延伸，應該是一個可以完成的部份，期待您的討論

小弟坐井觀天，如有冒犯請見諒"williamchangTW"

---

作業要求

1. 研讀 Balanced Ternary，並依據 課前測驗參考解答: Q1 的風格和探討方式，涵蓋以下:

   • 解釋 Balanced Ternary 原理;
   • [ ]Balanced Ternary 的設計要解決什麼類型的問題，需要詳述實際應用案例 (如 IOTA/Tangle)。提示：從算術表達的精準度和空間使用效率去探討;
   • 針對特定的領域 (如加密貨幣)，列出在 GitHub 裡頭可找到的應用案例，不僅列出程式碼，還要解說;
   • [ ]在研究的過程中，應該會對既有工具進行修改或者重新開發 (不限程式語言)，也該一併指出，程式碼應該維護在 GitHub 上;

2. 其他:

$BalancedTernary$

數字與中文間記得以空白隔開!
課程助教

ok
TsengWen

平衡三進位:

是一種以 3 為基數，-1、0、1 為基本數位的進位。

特點

1. 由於 -1 的引入，這種進位不需要額外的符號就能直接表示負數。正因為這一點，使得平衡三進位在加減法和乘法方面的效率要比二進位高。
2. 各位上的數字之和為偶數的整數是偶數；各位上的數字之和為奇數的整數是奇數。

例如 :

$$\begin{gathered} +=1 \\ 0=0 \\ -=-1 \end{gathered}$$

---

$$42=\begin{array}{cccccc}{3}^4& 3^3& 3^2& 3^1& 3^0& \\ +& -& -& -& 0\\ 81& -27& -9& -3& +0\end{array}$$

---

$$\mathrm{平}\mathrm{衡}\mathrm{三}\mathrm{進}\mathrm{位}$$

下兩個表格請改以縱向的表格表示，或是切成上下兩部分，塞在一起會超出畫面
課程助教

OKTsengWen

$$\begin{array}{cccccccccc}\mathrm{十}\mathrm{進}\mathrm{位}& -9& -8& -7& -6& -5& -4& -3& -2& -1\\ \\ \mathrm{平}\mathrm{衡}\mathrm{三}\mathrm{進}\mathrm{位}& -00& -0+& -+-& -+0& -++& 0--& -0-& 0-+& 00-\end{array}$$

$$\begin{array}{cccccccccc}\mathrm{十}\mathrm{進}\mathrm{位}& 9& 8& 7& 6& 5& 4& 3& 2& 1\\ \\ \mathrm{平}\mathrm{衡}\mathrm{三}\mathrm{進}\mathrm{位}& +00& +0-& +-+& +-0& +--& 0++& 0+0& 0+-& 00+\end{array}$$

• 觀察發現：正負號轉換只需將 + 轉 - 和 - 轉 +
  相較原本2's complement 反向 再加一 ，或許能夠少去加一的步驟。

---

小數

平衡三進位和十進位一樣，用小數點分隔整數部分和小數部分。

$$\begin{array}{cccccc}\mathrm{十}\mathrm{進}\mathrm{位}& -0.5& -0.4& -0.3& -0.2& -0.1\\ \\ \mathrm{平}\mathrm{衡}\mathrm{三}\mathrm{進}\mathrm{位}& 0.\overline{-}\mathrm{或}-.\overline{+}& 0.\overline{--++}& 0.\overline{-0+0}& 0.\overline{-++-}& 0.\overline{0-0+}\end{array}$$

$$\begin{array}{cccccc}\mathrm{十}\mathrm{進}\mathrm{位}& 0.5& 0.4& 0.3& 0.2& 0.1\\ \\ \mathrm{平}\mathrm{衡}\mathrm{三}\mathrm{進}\mathrm{位}& 0.\overline{+}\mathrm{或}+.\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}\dots =\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}\dots =1-(\frac{1}{3}+\frac{1}{9}+\frac{1}{27}+\frac{1}{81}\dots )=1-\frac{1}{2}=\frac{1}{2}$$

---

運算

$$\begin{array}{clcr}+& -& 0& +\\ -& +-& +& 0\\ 0& +& 0& -\\ +& 0& -& -+\end{array}$$

$$\begin{array}{clcr}\ast & -& 0& +\\ -& +& 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}{cc}input& equivalent\\ 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

乘法

$$\begin{gathered} \mathrm{在}\mathrm{不}\mathrm{假}\mathrm{設}\mathrm{特}\mathrm{殊}\mathrm{硬}\mathrm{體}\mathrm{架}\mathrm{構}\mathrm{下}，\mathrm{將}\mathrm{數}\mathrm{表}\mathrm{示}\mathrm{成}a=(a<{<}_{3}c)+d \\ <{<}_3\mathrm{為}\mathrm{向}\mathrm{左}\mathrm{位}\mathrm{移}\mathrm{一}\mathrm{個}trit \end{gathered}$$

---

$$\begin{array}{ll}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)\times 4\\ \\ 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{a}{2}=a\times \frac{1}{2}=a\times 0.11{\bar{1}}_3\\ \frac{a}{3}=a\times \frac{1}{3}=a\times {0.1}_3\\ \frac{a}{4}=a\times \frac{1}{4}=a\times 0.0202{\overline{02}}_3\\ \frac{a}{5}=a\times \frac{1}{5}=a\times 0.01210121{\overline{0121}}_3\\ \frac{a}{6}=a\times \frac{1}{6}=a\times 0.011{\bar{1}}_3\\ \frac{a}{7}=a\times \frac{1}{7}=a\times 0.{\overline{010212}}_3\\ \frac{a}{8}=a\times \frac{1}{8}=a\times 0.0101{\overline{01}}_3\\ \frac{a}{9}=a\times \frac{1}{9}=a\times {0.01}_3\\ \frac{a}{10}=a\times \frac{1}{10}=a\times 0.0022{\overline{0022}}_3\end{array}$$

參考網站

• 平衡三進位 - 維基百科，自由的百科全書
• The ternary computer
• Standard Ternary Logic
• Ternary Data Types for C Programmers
• Arithmetic with Binary-Encoded Balanced Ternary Numbers

$LATEX$

• 是一種基於TEX的排版系統，適用於生成高印刷品質的科技和數學、化學類文件。

MathJax語法

可以使用 MathJax 語法 來產生 LaTeX 數學表達式：

The Gamma function satisfying

$\mathrm{\Gamma }(n)=(n-1)!\mathrm{\forall }n\in \mathbb{N}$ is via the Euler integral

$$x=\frac{-b\pm \sqrt{b^2-4ac}}{2a}.$$

更多關於 LaTeX 數學表達式 請至這裡

參考網站

• Latex in Ubuntu
• 語法教學