平衡三進位(英語:balanced ternary)是一種非標準的計數進位制,它是一種基數為的進位制系統,其中用於計數的符碼為,與標準基數 3 進位系統對比:其中的計數符號為。以平衡三進位所記錄的數字可以表達出全部整數,由於的引入,而且對負數不必使用額外的負號;應用在於解決秤重問題[1],或在一些早期的計算機中使用[2]。
此條目需要補充更多來源。 (2016年5月13日) |
有些地方使用不同符碼來表示平衡三進位中的三個數符。本文中以 T(連在 1 上方的負號)表示 ,而 和 表示自身。其他約定包括使用 '-' 和 '+'分別表示 和 ,或使用希臘字母 Θ(於圓圈中的負號)來表示 。在 Setun計算機中 表示為倒轉的阿拉伯數字一:「1」[2]。
平衡三進位在 Michael Stifel(1544)的書《Arithmetica Integra》中出現過[3]。它也曾出現在 Kepler和 LéonLalanne 的作品中。對負數不必使用額外的負號這一點,使得平衡三進位在四則運算的加、減、乘法效率,會比二進位高。美國著名電腦學家高德納在《編程的藝術》一書中指出,「也許最美的進位是平衡三進位」。
“ | Perhaps the prettiest number system of all... is the balanced ternary notation | ” |
——Donald Knuth, The Art of Programming |
數的表示方法
平衡三進位和其他進位一樣,各位的數字和位權相乘然後疊加起來,就是該數的數值。數字下標 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倍。
運算
平衡三進位和二進位一樣,乘法運算等效於移位疊加運算。
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
註:減法是左列減去頂行,除法是左列除以頂行
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 ...
以下是平衡三進位邏輯運算真值表。
|
|
|
|
|
|
|
|
另見
參考文獻
外部連結
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.