非整数进位制
非整数进位制是指底数不是正整數的进位制。對於一個非正整數的底數β > 1,以下的數值: 為
而數字di為小於β的非負整數。此進位制可以配合所使用β,稱為β进制或β展開,後者的名稱是數學家Rényi在1957年開始使用[1],而數學家Parry在1960年第一個進行相關的研究[2]。每一個實數至少有一個β进位制的表示方式(也可能是無限多個)。
建構
β进制是十進制的延伸。十進制的表示法不唯一(例如,1.000... = 0.999...),不過所有有限位數的十進制表示法是唯一的。有限位數β进制就不一定有此特性,例如,在β = φ(黃金比例)時,φ + 1 = φ。
針對特定實數,選擇其β进制各位數的方式,可以用以下的贪心算法產生,本質上是來自Rényi (1957),此處的公式則來自Frougny (1992) 。
令β > 1是底數,x為非負的實數。令⌊x⌋是x的取整函数(小於等於x的最大整數),令{x} = x − ⌊x⌋是x的小數部份。存在一整數k使得βk ≤ x < βk+1。令
且
針對k − 1 ≥ j > −∞,定義
換句話說,x的正規β進制表示法可以用以下方式得到:先選擇最大的dk,使得βkdk ≤ x,再選擇最大的dk−1,使得βkdk + βk−1dk−1 ≤ x,以此類推。此作法會選擇可以表示x,字典序最大的字串。
若是整數進位制,以上方式會產生一般整數進位制下的數值。因此此建構方式將一般的演算法推廣到非整數的基底β。
參考文獻
- ^ Rényi, Alfréd, Representations for real numbers and their ergodic properties, Acta Mathematica Academiae Scientiarum Hungaricae, 1957, 8 (3–4): 477–493, ISSN 0001-5954, MR 0097374, S2CID 122635654, doi:10.1007/BF02020331, hdl:10338.dmlcz/102491
- ^ Parry, W., On the β-expansions of real numbers, Acta Mathematica Academiae Scientiarum Hungaricae, 1960, 11 (3–4): 401–416, ISSN 0001-5954, MR 0142719, S2CID 116417864, doi:10.1007/bf02020954, hdl:10338.dmlcz/120535
- ^ Kautz, William H., Fibonacci codes for synchronization control, Institute of Electrical and Electronics Engineers. Transactions on Information Theory, 1965, IT–11 (2): 284–292, ISSN 0018-9448, MR 0191744, doi:10.1109/TIT.1965.1053772
- ^ Burdik, Č.; Frougny, Ch.; Gazeau, J. P.; Krejcar, R., Beta-integers as natural counting systems for quasicrystals, Journal of Physics A: Mathematical and General, 1998, 31 (30): 6449–6472, Bibcode:1998JPhA...31.6449B, CiteSeerX 10.1.1.30.5106 , ISSN 0305-4470, MR 1644115, doi:10.1088/0305-4470/31/30/011
- ^ Thurston, W.P., Groups, tilings and finite state automata, AMS Colloquium Lectures, 1989
相關條目