跳至內容

平衡三進位

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書

平衡三進制(英語:balanced ternary)是一種非標準的計數進位制,它是一種基數為的進位制系統,其中用於計數的符碼為,與標準基數 3 進制系統對比:其中的計數符號為。以平衡三進制所記錄的數字可以表達出全部整數,由於的引入,而且對負數不必使用額外的負號;應用在於解決秤重問題[1],或在一些早期的計算機中使用[2]

有些地方使用不同符碼來表示平衡三進制中的三個數符。本文中以 T(連在 1 上方的負號)表示 ,而 表示自身。其他約定包括使用 '-' 和 '+'分別表示 ,或使用希臘字母 Θ(於圓圈中的負號)來表示 。在 Setun計算機中 表示為倒轉的阿拉伯數字一:「1[2]

平衡三進制在 Michael Stifel(1544)的書《Arithmetica Integra》中出現過[3]。它也曾出現在 Kepler和 LéonLalanne 的作品中。對負數不必使用額外的負號這一點,使得平衡三進制在四則運算的加、減、乘法效率,會比二進制高。美國著名電腦學家高德納在《編程的藝術》一書中指出,「也許最美的進制是平衡三進制」。

數的表示方法

[編輯]

整數的轉換

[編輯]

平衡三進制和其他進制一樣,各位的數字和位權相乘然後疊加起來,就是該數的數值。數字下標 bal3 表示為平衡三進制,而下標 dec 則為十進制:

10bal3 = 1×31 + 0×30 = 3dec
10Tbal3 = 1×32 + 0×31 + (-1)×30 = 8dec
-9dec = -1×32 + 0×31 + 0×30 = T00bal3
8dec = 1×32 + 0×31 + (-1)×30 = 10Tbal3

平衡三進制不需要額外的符號就可以表示負數。左起第一位若非 0 而是 T 的即為負數,若是 1 的則是正數。

在平衡三進制中,各位上的數字之和為偶數的整數是偶數;各位上的數字之和為奇數的整數是奇數。

比如:

十進制 平衡三進制 轉換展開 十進制 平衡三進制 轉換展開
0 0 0
1 1 +1 -1 T -1
2 1T +3-1 -2 T1 -3+1
3 10 +3 -3 T0 -3
4 11 +3+1 -4 TT -3-1
5 1TT +9-3-1 -5 T11 -9+3+1
6 1T0 +9-3 -6 T10 -9+3
7 1T1 +9-3+1 -7 T1T -9+3-1
8 10T +9-1 -8 T01 -9+1
9 100 +9 -9 T00 -9
10 101 +9+1 -10 T0T -9-1
11 11T +9+3-1 -11 TT1 -9-3+1
12 110 +9+3 -12 TT0 -9-3
13 111 +9+3+1 -13 TTT -9-3-1

小數

[編輯]

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

十進制 −0.9 −0.8 −0.7 −0.6 −0.5 −0.4 −0.3 −0.2 −0.1 0
平衡三進制 T.010T T.1TT1 T.10T0 T.11TT 0.T or T.1 0.TT11 0.T010 0.T11T 0.0T01 0
十進制 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0
平衡三進制 1.0T01 1.T11T 1.T010 1.TT11 0.1 or 1.T 0.11TT 0.10T0 0.1TT1 0.010T 0

在平衡三進制中,四捨五入和截位的操作是等效的。

分數的小數化

[編輯]

平衡三進制可以像十進制一樣,可以用小數來表示分數,例如=0.1bal3

十進制分數 平衡三進制 十進制分數 平衡三進制
1/1 1 1/11 0.01T11
1/2 0.1 1.T 1/12 0.01T
1/3 0.1 1/13 0.01T
1/4 0.1T 1/14 0.01T0T1
1/5 0.1TT1 1/15 0.01TT1
1/6 0.01 0.1T 1/16 0.01TT
1/7 0.0110TT 1/17 0.01TTT10T0T111T01
1/8 0.01 1/18 0.001 0.01T
1/9 0.01 1/19 0.00111T10100TTT1T0T
1/10 0.010T 1/20 0.0011
十進制分數 平衡三進制 十進制分數 平衡三進制
0/1 0 10/11 1.0T1TT
1/2 0.1 1.T 11/12 1.0T1
2/3 0.1 12/13 1.0T1
3/4 0.1T 13/14 1.0T101T
4/5 0.1TT1 14/15 1.0T11T
5/6 1.0T 1.T1 15/16 1.0T11
6/7 1.0TT011 16/17 1.0T111T0101TTT10T
7/8 1.0T 17/18 1.00T 1.0T1
8/9 1.0T 18/19 1.00TTT1T0T00111T101
9/10 1.0T01 19/20 1.00TT

與十進制、二進制類似,部分分數有兩種表達形式。在十進制、二進制中,最小的數位是0,因此小數點後最右邊無限迴圈的0可以省略掉,從而變成一個整數或有限小數;而在平衡三進制中,小數點後最右邊無限迴圈的T不能省略,因而不能變成整數或有限小數。

無理數

[編輯]

無論對於十進制、平衡三進制還是其他以有理數為底數的記數系統,所有的無理數都只能表示成無限不循環小數。下表列出了一些代數無理數超越無理數的十進制與平衡三進制的表示。

代數數 十進制 平衡三進制
1.41421356237309... (≈ 1.414) 1.11T1TT00T00T01T0T00T00T01T...
1.73205080756887... (≈ 1.732) 1T.T1TT10T0000TT1100T0TTT011T...
2.2360679774997... (≈ 2.236) 1T.1T0101010TTT1TT11010TTT01T...
φ(黃金分割, 1.6180339887498... (≈ 1.618) 1T.T0TT01TT0T10TT11T0011T1001...
超越無理數 十進制 平衡三進制
π(圓周率) 3.1415926535897932384626433...(≈ 3.1416) 10.011T111T000T011T1101T11111...
e(自然對數的底) 2.718281828459045... (≈ 2.718) 10.T0111TT0T0T111T0111T000T11...


下面是另一個重要常數歐拉-馬斯刻若尼常數在十進制與平衡三進制中的表示(現在仍無法確定其是有理數還是無理數):

十進制 平衡三進制
γ(歐拉-馬歇羅尼常數) 0.57721566490153... (≈ 0.577) 1.TT1TT1T1010001T0T00111TTT0...

十進制到平衡三進制的轉換

[編輯]

十進制轉化為平衡三進制,可參照下述方法,先圓整後,再分別對整數部分和小數部分進行連除法和連乘法即可。

-25.4

        -25.4,圆整#为-25;  ‡                       余,-0.4;♦
   -25÷3=-8⅓, 圆整为- 8;余,-1↑;  ‡   -0.4×3=-1.2,  圆整为-1|;余,-0.2;
   - 8÷3=-2⅔, 圆整为- 3;余, 1|;   ‡   -0.2×3=-0.6,  圆整为-1 (原为0,底下进T,则为T)|;余, -0.6;
   - 3÷3=-1 ,  圆整为- 1;余, 0|;   ‡   -0.6×3= -1.8, 圆整为1  (原为-1,底下进T,为-2再改为1,再向上进T)|;余, -0.8;
   - 1÷3=- ⅓, 圆整为  0;余,-1|;   ‡   -0.8×3= -2.4, 圆整为1  (原为-2,-2改为1,向上进T)↓;余,-0.4;跳入循环
       -25.410=T01T.TT113

#圓整到最近的整數

當然,也可以採用另一種方法。

     -25.410=-(1T*1011+1TT*1010+11*101T)
                      =-(1T*101+1TT+11/101)
                      =-10T1.11TT
                      =T01T.TT11

三進制電腦中數的表示

[編輯]

計算機的初期發展過程中,蘇聯有一些實驗性質的計算機,是以平衡三進制而不是二進制來設計製造的,其中最著名的是由尼古拉·布魯金索夫和謝爾蓋·索博列夫建造的 Сетунь。 與現在通行的二進制相比,平衡三進制的實驗性設計具有許多計算科學上的優勢。 特別是,正負一致性可以加快多位乘法中的進位速率,而捨入截斷當量則會減少對分數做捨入的進位次數。 在平衡三進制中,單一位數的乘法表不需用到進位,而加法表只會有兩個對稱進位而不是三個。

註:以下部分以「'」為十進制數萬位分隔符

基本概念

[編輯]

位(trit):對稱三進制的數位;

位元組(tryte):莫斯科大學的Сетунь以6位為1個位元組,單位元組整數的表示範圍為:-364~+364;

字(word):參照二進制,以2個位元組為1個字,單字整數的表示範圍為:-26'5720~+26'5720;

整數

[編輯]

紐約州立大學在1973年開發的測試機Ternac,採用24位元表示一個整數,表示範圍為-1412'1476'8240~+1412'1476'8240

定點數

[編輯]

定點數的表示方法和整數一樣。只是會預先指定小數點的位置。

比如採用48位元表示一個實數,整數部分、小數部分各24位元。則,表示範圍為-1412'1476'8240.5~+1412'1476'8240.5,精度為3-24(3.54*10-12

浮點數

[編輯]

Ternac,採用48位元表示一個實數,其中尾數42位,指數6位。

參照IEEE754的浮點數表示法,對稱三進制的表示法如下:

1個符號位(整數部分)+尾數體41位(小數部分)+指數體6位

整數部分為1是正的規因數。表示範圍為0.5*3-364+0.5*3-405~0.5*3365-0.5*3323

整數部分為0的是零附近的數,是非規因數。非規因數的指數固定為-364,指數體併入尾數。表示範圍為0.5*3-411-0.5*3-364~0.5*3-364-0.5*3-411,精度為0.5*3-411

邏輯常數

[編輯]
平衡三進制 邏輯狀態 標準三進制
1 True 2
0 Unknown 1
T False 0

三進制電腦,以三值邏輯為基礎,有三個邏輯狀態值——真、假、未知。我們用 表示真、 表示未知,而 則表示假。

三進制電腦中資訊的表示

[編輯]

三進制電腦中,以平衡三進制為資訊進行編碼。

我們可以以12位元為單位,對文字進行編碼作為標準資訊交換碼(STUCII,Standard Ternary Unified Code for Information Interchange)。其容量為53'1441個字元,約是16bits容量的8.1倍。

運算

[編輯]

加減乘除四則運算

[編輯]

平衡三進制和二進制一樣,乘法運算等效於移位疊加運算。

單雙位平衡三進制加法表、乘法表、除法表

[編輯]
加法
+ TT T0 T1 T 0 1 1T 10 11
11 0 1 1T 10 11 1TT 1T0 1T1 10T
10 T 0 1 1T 10 11 1TT 1T0
1T T1 T 0 1 1T 10 11
1 T0 T1 T 0 1 1T
0 TT T0 T1 T 0 1
T T11 TT T0 T1 T 0
T1 T10 T11 TT
T0 T1T T10
TT T01
乘法
× TT T0 T1 T 0 1 1T 10 11
11 T11T TT0 T01 TT 0 11 10T 110 1TT1
10 TT0 T00 T10 T0 0 10 1T0 100
1T T01 T10 TT 1 0 IT 11
1 TT T0 T1 T 0 1
0 0 0 0 0 0 0
T 11 10 1T 1 0 T
T1 10T 1T0 11
T0 110 100
TT 1TT1
減法
- TT T0 T1 T 0 1 1T 10 11
TT 0 T T1 T0 TT T11 T10 T1T T01
T0 1 0 T T1 T0 TT T11 T10 T1T
T1 1T 1 0 T T1 T0 TT T11 T10
T 10 1T 1 0 T T1 T0 TT T11
0 11 10 1T 1 0 T T1 T0 TT
1 1TT 11 10 1T 1 0 T T1 T0
1T 1T0 1TT 11 10 1T 1 0 T T1
10 1T1 1T0 1TT 11 10 1T 1 0 T
11 10T 1T1 1T0 1TT 11 10 1T 1 0
除法
÷ TT T0 T1 T 0 1 1T 10 11
TT 1 1.1 1T 11 -∞ TT T1 T.T T
T0 1.T1 1 1.1 10 -∞ T0 T.T T T.1T
T1 1.T 1.T 1 1T -∞ T1 T T.1 T.1
T 0.1T 0.1 0.1 1 -∞ T 0.T 0.T 0.T1
0 0 0 0 0 NaN 0 0 0 0
1 0.T1 0.T 0.T T +∞ 1 0.1 0.1 0.1T
1T T.1 T.1 T T1 +∞ 1T 1 1.T 1.T
10 T.1T T T.T T0 +∞ 10 1.1 1 1.T1
11 T T.T T1 TT +∞ 11 1T 1.1 1

註:減法是左列減去頂行,除法是左列除以頂行


1從上表中可以看出,雙位數相加可能會變成單位數,雙位數相減可能會變成三位數,雙位數相乘可能可能仍是雙位數。這種情況在十進制和二進制中不會發生。

多位數的加減法

[編輯]

就是逐位做加減法。 減法,亦可以逐位取反後,換做加法 比如

     1TT1TT.1TT1       1TT1TT.1TT1      1TT1TT.1TT1     1TT1TT.1TT1
    +  11T1.T        -   11T1.T         - 11T1.T -> +     TT1T.1
    ------------     --------------                ---------------
     1T0T10.0TT1       1T1001.TTT1                      1T1001.TTT1
    +  1T            +  T  T1                        +   T  T1
    ------------     ----------------               ----------------
     1T1110.0TT1       1110TT.TTT1                      1110TT.TTT1
    +  T             + T   1                         +  T   1
    ------------     ----------------                ----------------
     1T0110.0TT1       01100T.TTT1                      01100T.TTT1

乘法

[編輯]

可以採用類似於十進制的各種方法。 比如

     1TT1.TT
 ×   T11T.1
 ------------
      1TT.1TT
     T11T.11
    1TT1T.T
   1TT1TT
 +T11T11
 ------------
  0T0000T.10T

除法

[編輯]

平衡三進制的除法和十進制的除法類似。

但是,大家已經知道,0.5在平衡三進制中有0.11111…和1.TTTT…兩種表達式,也就是說,如果被除數超過除數的一半,商的當前位就要置1或T。

                1TT1.TT
            -------------        
    T11T.1  ) T0000T.10T        
             T11T1
            --------
              1T1T0
              1TT1T
             --------
                111T
               1TT1T
              ---------
                 T00.1
                T11T.1
               ---------
                 1T1.00
                 1TT.1T
                ---------
                  1T.T1T
                  1T.T1T
                 --------
                       0

開平方

[編輯]

平衡三進制開平方和十進制、二進制類似。但和除法一樣,要比較的是半除數。例如:

                             1. 1 1 T 1 T T 0 0 ...
                            ------------------------
                           √1T                          1<1T<11, 置 1
                             1
                            -----
                       10    1.0T                       1.0T>0.10, 置 1
                      1T0    1.T0
                            --------
                        110    1T0T                     1T0T>110, 置 1
                       10T0    10T0
                              --------
                        1110    T1T0T                   T1T0T<TTT0, 置 T
                       100T0    T0010
                               ---------
                        111T0    1TTT0T                 1TTT0T>111T0, 置 1
                       10T110    10T110
                                ----------
                        111T10    TT1TT0T               TT1TT0T<TTT1T0, 置 T
                       100TTT0    T001110
                                 -----------
                        111T1T0    T001TT0T             T001TT0T<TTT1T10, 置 T
                       10T11110    T01TTTT0
                                  ------------
                          111T1TT0    T001T0T           TTT1T110<T001T0T<111T1TT0, 置 0
                                            T
                                     -----------
                         111T1TT00    T001T000T         TTT1T1100<T001T000T<111T1TT00, 置 0
                                              T
                                     -------------
                        111T1TT000    T001T00000T
                                              ...

邏輯運算

[編輯]

以下是平衡三進制邏輯運算真值表。

邏輯與
T 0 1
T T T T
0 T 0 0
1 T 0 1
邏輯或
T 0 1
T T 0 1
0 0 0 1
1 1 1 1
邏輯與非
T 0 1
T 1 1 1
0 1 0 0
1 1 0 T
邏輯或非
T 0 1
T 1 0 T
0 0 0 T
1 T T T
邏輯互斥或
T 0 1
T T 0 1
0 0 0 0
1 1 0 T
邏輯合意
T 0 1
T T 0 0
0 0 0 0
1 0 0 1
邏輯調和
T 0 1
T T T 0
0 T 0 1
1 0 1 1
邏輯非
¬ T 0 1
1 0 T

另見

[編輯]

參考文獻

[編輯]
  1. ^ Hayes, Brian, Third base (PDF), American Scientist, 2001, 89 (6): 490–494, doi:10.1511/2001.40.3268 . Reprinted in Hayes, Brian, Group Theory in the Bedroom, and Other Mathematical Diversions, Farrar, Straus and Giroux: 179–200, 2008 [2019-04-22], ISBN 9781429938570, (原始內容存檔於2019-05-16) 
  2. ^ 2.0 2.1 N.A.Krinitsky; G.A.Mironov; G.D.Frolov. Chapter 10. Program-controlled machine Setun. M.R.Shura-Bura (編). Programming. Moscow. 1963 (俄語). 
  3. ^ Stifel, Michael, Arithmetica integra: 38, 1544 (拉丁語) .

外部連結

[編輯]