复底数进制

複底数进制是指底數虛數複數进位制系統。 其中,底數為虛數的进位制系統最早由高德纳於1955年提出[1][2];底數為複數的进位制系統於1964年由所羅門·I·赫梅利尼克(Solomon I. Khmelnik)[3]和1965年由沃爾特·F·彭尼(Walter F. Penney)提出[4][5][6]

概述

 整环  (阿基米德)绝对赋值

 进位制系統中可以表示為:

 

其中

  底數,並滿足 
  指數,代表各個位數,
  是进制中每個位數,來自有限的位數數碼集合 ,通常滿足 

 稱為分解程度(level of decomposition)

进位制系統或編碼系統是一對二元組:

 

包括了其底數 和位數數碼集合 。通常會將有 個位數數碼的位數數碼集合表示為:

 

理想的进位制系統或編碼系統具有以下特性:

  • 任何在环 內的數如整數 高斯整數 或环 的整數可以表達為為唯一的編碼,並可能帶有正負號±。
  • 任何在分式環 內的數,或者再取完備化 度量的意義下)所得的  內的數,皆可以表示為在 下,於 收斂的無窮級數 ,且不只一種表示方式之數的集合测度為0。後者要求集合 最小,即對於實數 、對於複數 

實數

在這種表示法中,一般常見的標準十进制表示為:

 

標準二进制系統表示為:

 

負二进制系統表示為:

 

平衡三進位系統表示為[2]

 

上述這幾個进位制系統在  中都具有上述的特性。後兩個不需要使用正負號。

複數

較廣為人知的複底数进位制系統包括下列幾個进位制系統(其中 表示虛數單位):

  •  ,例如  [1] 进制)和
 [2],即2i进制,由高德纳於1995年提出。
  •  
 [3][5](參見下方−1 ± i进制一節)
  •  ,其中   是一個正整數,在給定的 可以取多個值[7]。 比如  是指
 进位制系統。( 进制)
  •  [8]
  •  ,其中,集合 由複數 組成,且數 ,例如
 [8]
  •  ,其中  [9]

二元系統

複數的二元系統是僅使用兩個數碼——0和1的进位制系統,即位數數碼集合為 进位制系統,這類記數系統具有較實際的用途[9]。 下表列出了一些 进位制系統(皆為上述进位制系統的特例),並用其表達−1, 2, −2, i。 同時也列出標準的二进制(下表的第一列)和「負二进制」(下表的第二列)供比較。這兩個进位制無法真正地表達出虛數單位i

部分的进位制系統和一些數的表達[10]
底數 –1 ← 2 ← –2 ← i 多種表示形式的數
2 −1 10 −10 i 1 ← 0.1 = 1.0
–2 11 110 10 i 1/3 0.01 = 1.10
  101 10100 100 10.101010100...[註 1]   0.0011 = 11.1100
  111 1010 110 11.110001100...[註 1]   1.011 = 11.101 = 11100.110
  101 10100 100 10 1/3 + 1/3i 0.0011 = 11.1100
–1+i 11101 1100 11100 11 1/5 + 3/5i 0.010 = 11.001 = 1110.100
2i 103 2 102 10.2 1/5 + 2/5i 0.0033 = 1.3003 = 10.0330 = 11.3300

與所有具有阿基米德绝对赋值进位制系統一樣,有些數字具有多種表示形式。此類數字的範例顯示在表格的右欄中。這些數都是循環小數,其循環節以上標水平線標記。

进制轉換

若要將一高斯整數 轉換為一個以高斯整數 底數进位制 可以將分成一個可被底數整除的高斯整數和一個位於位數數碼集合內的數,並將可被底數整除的高斯整數部分除以底數當作商,位於位數數碼集合內的數當作餘數,並用商數繼續計算,並重複以上步驟,直到商為零,一系列的餘數部分即為轉換完成的結果。[11]:41

 
 
 
 
 

其中,   …… 為高斯整數,   …… 為位於位數數碼集合內的數,

 

以5+12i轉換成-2+i进制( )為例:[11]:42

     
     
     
     

故5+12i(10)轉換成-2+i进制為2324(−2+i)

−1 ± i进制

 
−1+i進位制系統中整數部分全為零的複數

較常被討論的複底数进制是2i进制−1 ± i进制(−1 + i进制−1 − i进制),因為其皆可不使用正負號有限地表達所有高斯整數

−1 ± i进制以0和1为基本數碼,其於1964年由所羅門·I·赫梅利尼克(Solomon I. Khmelnik)[3]和1965年由沃爾特·F·彭尼(Walter F. Penney)提出[4][6]

−1±i進制與相關進制比較
十進制 二進制 2i進制 −1+i進制 −1−i進制
0 0 0 0 0
1 1 1 1 1
2 10 2 1100 1100
−1 −1 103 11101 11101
−2 −10 102 11100 11100
i i 10.2 11 111
2i 10i 10 1110100 100
3i 11i 20.2 1110111 110011
i i 0.2 111 11
−2i −10i 1030 100 1110100
−3i −11i 1030.2 110011 1110111
1+i 1+i 11.2 1110 111010
1−i 1−i 1.2 111010 1110
−1+i −1+i 113.2 10 110
−1−i −1−i 103.2 110 10

與twindragon關聯

整數的捨入區域——即在這系統表達之下,共用整數部分的複數(非整數)集合 ——在複平面中具有分形:twindragon。根據定義,集合 的所有點可以計為 ,其中  可以分解成16塊 。注意到,若 逆時針旋轉135°,則會得到兩個與 相等的相鄰集合,因為 。中心的矩形 R 在以下點逆時針地與坐標軸相交:    。因此,S 包含所有絕對值≤ 1/15的複數[2]:206

由此,複矩形

 

透過单射

 

映入實數區間 ,其中 [註 2]

此外,還有兩個映射

 

 

兩者皆满射,也就是產生了一個滿射(空間填充)的映射

 

然而,其並不連續,因此不是空間填充曲線。但是一個類似的曲線——戴維斯-高德納龍(Davis-Knuth dragon),是連續的空間填充曲線。

註釋

  1. ^ 1.0 1.1 無限不循環小數
  2. ^ 不能取底數 ,因為  。 然而, 不等於 

參考文獻

  1. ^ 1.0 1.1 Knuth, D.E. An Imaginary Number System. Communications of the ACM. 1960, 3 (4): 245–247. S2CID 16513137. doi:10.1145/367177.367233. 
  2. ^ 2.0 2.1 2.2 2.3 Knuth, Donald. Positional Number Systems. The art of computer programming 2 3rd. Boston: Addison-Wesley. 1998: 205. ISBN 0-201-89684-2. OCLC 48246681. 
  3. ^ 3.0 3.1 3.2 Khmelnik, S.I. Specialized digital computer for operations with complex numbers. Questions of Radio Electronics (In Russian). 1964, XII (2). 
  4. ^ 4.0 4.1 W. Penney, A "binary" system for complex numbers, JACM 12 (1965) 247-248.
  5. ^ 5.0 5.1 Jamil, T. The complex binary number system. IEEE Potentials. 2002, 20 (5): 39–41. doi:10.1109/45.983342. 
  6. ^ 6.0 6.1 Duda, Jarek. Complex base numeral systems. 2008-02-24. arXiv:0712.1309  [math.DS]. 
  7. ^ Khmelnik, S.I. Positional coding of complex numbers. Questions of Radio Electronics (In Russian). 1966, XII (9). 
  8. ^ 8.0 8.1 Khmelnik, S.I. Coding of Complex Numbers and Vectors (in Russian) (PDF). Israel: Mathematics in Computer. 2004 [2022-11-03]. ISBN 978-0-557-74692-7. (原始内容存档 (PDF)于2022-11-10). 
  9. ^ 9.0 9.1 Khmelnik, S.I. Method and system for processing complex numbers. Patent USA, US2003154226 (A1). 2001 [2022-11-03]. (原始内容存档于2023-01-09). 
  10. ^ William J. Gilbert. Arithmetic in Complex Bases (PDF). Mathematics Magazine. 1984-03,. Vol. 57 (No. 2) [2022-11-03]. (原始内容存档 (PDF)于2022-11-03). 
  11. ^ 11.0 11.1 Piché, Daniel Guy, Complex Bases, Number Systems and Their Application to Fractal-Wavelet Image Coding (PDF), University of Waterloo, 2002 [2022-11-03], (原始内容存档 (PDF)于2022-11-10)