跳转到内容

平衡三進位

本页使用了标题或全文手工转换
维基百科,自由的百科全书

平衡三进制(英語: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 (拉丁语) .

外部链接