2017q3 Homework1 (ternary)

contribute by <yuan922>

Review by williamchangTW

  • 用printf() 去做偵測看到實際資料是一個滿好用的方式，或許可以藉由此方法去更改 code 有些疑慮的地方，比如到達哪個數會發生錯誤的資料
  • 關於 ternary 的分析，看得出來你對該定義有一定程度的瞭解，試著分析老師給的案例，應該能銀刃而解

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

Ternary 定義:

以三為基底的進位，其位數稱為三進位數(trit)，使用0,1,2三個數表示。
P.S.二進位的位數稱為bit(binary digit的縮寫)。

Balanced Ternary 定義:

相較於三進位用0,1,2表示，平衡三進位使用T(-1),0,1來表示數值，
這樣可以省去使用額外的負號表示負數。

整數

  • \(7_{10}=1T1_{bal3}\)

\(1T1_{bal3}=1*3^2+(-1)*3^1+1*3^0\\ =7\)

  • \(-7_{10}=T1T_{bal3}\)

\(T1T_{bal3}=(-1)*3^2+1*3^1+(-1)*3^0\\ =-7\)

  • \(2356_{10}=101T01T1_{bal3}\)

用3來除看看:
\(\begin{split}\ 2356/3&=785...1\\ 785/3&=262...T\\ 262/3&=87...1\\ 87/3&=29...0\\ 29/3&=10...T\\ 10/3&=3...1\\ 3/3&=1...0\\ 1/3&=0...1\\ 由下往上寫回去:101T01T1 \end{split}\)

與一般的除法不一樣的地方:

一般除法是要除出一個餘數(不夠的數)，而這裡因為只用-1,0,1來表示，
所以要產生-1就要乘上一個會超過被除數的數字
e.g. 785/3=262…T 原本應該會是261…2
e.g. 29/3=10…T 原本應該會是9…2

小數

  • \(-22.4_{10}=T1TT.\overline{TT11}_{bal3}\)

\(\begin{split}\ 整數部分:-22\\ -22/3&= -7\dfrac{1}{3} 最接近整數為-7...-1\\ -7/3&=-2\dfrac{1}{3} 最接近整數為-2...-1\\ -2/3&=-\dfrac{2}{3} 最接近整數為-1...1\\\ -1/3&=-\dfrac{1}{3} 最接近整數為0...-1\\ \end{split}\)
\(\begin{split}\ 小數部分:-0.4\\ -0.4*3&=-1.2 圓整為-1... -0.2\\ -0.2*3&=-0.6 圓整為-1... 0.4\\ 0.4*3&=1.2圓整為1... 0.2\\ 0.2*3&=0.6圓整為1...-0.4,循環\\ \end{split}\)

真值表

AND(Min取小):有T的都會是T，因為最小

∧ T 0 1
T T T T
0 T 0 0
1 T 0 1
OR(Max取大):有1的都會是1，因為最大
∨ T 0 1
–––– –––– –––– ––––
T T 0 1
0 0 0 1
1 1 1 1
XOR (a ⊕ b) = ( (a ∧ – b) ∨ (b ∧ – a) )
⊕ T 0 1
–––– –––– –––– ––––
T T 0 1
0 0 0 0
1 1 0 T

Balanced ternary 半加法器

先以logic table觀察Sum跟Carry的結果:

Logic table

Sum – 0 +
– + – 0
0 – 0 +
+ 0 + –
Carry – 0 +
– – 0 0
0 0 0 0
+ 0 0 +

紅字解釋:

(-1)+(-1)=-2在\(bal_3\)會用(-3)+1表示也就是\(T1\)
(+1)+(+1)=2在\(bal_3\)會用3+(-1)表示也就是\(1T\)
這我想好久…
yuan922

Balanced ternary half adder

(a ⊠ b):a,b同時為-則-,同時為+則+,其餘皆0。

程式碼分析







for (r = 0; r < SZD; ++r) {
        p = &digit[r];
        p->exp = r ? (3 * digit[r-1].exp) : 1;
        p->val = 0;
    }

從第3行的判斷式來看，因為r一開始是0，所以一定會跳到後面的結果，
也就是說 p->exp=1;而 p = &digit[0]，
那麼 digit[0].exp 就會是1。

為了方便觀察 exp 的變化，用 printf 印出變化：









for (r = 0; r < SZD; ++r) {
        p = &digit[r];
        printf("exp_before %d \n",p->exp);
        p->exp = r ? (3 * digit[r-1].exp) : 1;
        printf("exp_after %d\n",p->exp);
        p->val = 0;
    }

可以看出exp就是不斷的*3，以\(3^n\)變化。







 p = &digit[SZD - 1];
    r = 3 * p->exp / 2;
    if (src > r)
        src = r;
    else
        r = src;

r=3*2184/2=3280.5，所以如果輸入大於r就只能最多到r。








  do {
        while (r < p->exp)
            --p;
        r -= p->exp;
        ++p->val;
    } while (r);

拿r=15為例：一開始進去迴圈會先不斷的遞減p直到r超過一個最近的值，
以15來說就會從2187一直遞減到9，之後15-9=6，
p->exp=9的val+1，再來6會對應到3，6-3=3，
p->exp=3的val+1，再來3也會對應到3，3-3=0，
p->exp=3的val再+1，跳出迴圈。

  • 結果：15會被表示成1 * 9+2 * 3也就是\(1*3^2+2*3^1\)










 while (p < &digit[SZD]) {
        if (r)
            ++p->val;
        r = p->val > 1;
        if (r)
            p->val -= 3;
        p->val *= inv;
        ++p;
    }

這段是轉換成 \(bal_3\)的形式:

  1. r=0進去之後跳到第4行，因為exp=3的val=2>1，所以r為真，
    exp=3的val-3=-1，結束\(3^1\)項，再來換\(3^2\)項。
  2. 因為r為真，第三行exp=9的val會+1變2，第4行2>1成立，
    exp=3的val-3=-1，結束\(3^2\)項，再來換\(3^3\)項。
  3. 因為r為真，第三行exp=27的val會從0+1，由於1>1不成立，直接跳到第7行，p再加1，但接下來的r跟p->val都沒值所以結束。
  • 結果:15就會被換成 \(1TT0\)。

Balanced Ternary 的設計要解決什麼類型的問題，需要詳述實際應用案例 (如 IOTA/Tangle)。

針對特定的領域 (如加密貨幣)，列出在 GitHub 裡頭可找到的應用案例

參考資料

Select a repo