查看“︁非整数进位制”︁的源代码

'''非整数进位制'''是指[[底数 (进制)|底数]]不是[[正整數]]的[[进位制]]。對於一個非正整數的底數β > 1，以下的數值:
<math>x=d_n\dots d_2d_1d_0.d_{-1}d_{-2}\dots d_{-m}</math>
為
:<math>x=\beta^nd_n + \cdots + \beta^2d_2 + \beta d_1 + d_0 + \beta^{-1}d_{-1} + \beta^{-2}d_{-2} + \cdots + \beta^{-m}d_{-m}.</math>
而數字''d''<sub>''i''</sub>為小於β的非負整數。此進位制可以配合所使用β，稱為'''β进制'''或'''β展開'''，後者的名稱是數學家Rényi在1957年開始使用<ref>{{Citation | last1=Rényi | first1=Alfréd | title=Representations for real numbers and their ergodic properties | mr=0097374 | doi=10.1007/BF02020331 | hdl=10338.dmlcz/102491 | year=1957 | journal=Acta Mathematica Academiae Scientiarum Hungaricae | issn=0001-5954 | volume=8 | issue=3–4 | pages=477–493| s2cid=122635654 | hdl-access=free }}</ref>，而數學家Parry在1960年第一個進行相關的研究<ref>{{Citation | last1=Parry | first1=W. | title=On the β-expansions of real numbers | mr=0142719 | year=1960 | journal=Acta Mathematica Academiae Scientiarum Hungaricae | issn=0001-5954 | volume=11 | issue=3–4 | pages=401–416 | doi=10.1007/bf02020954| hdl=10338.dmlcz/120535 | s2cid=116417864 | hdl-access=free }}</ref>。每一個實數至少有一個β进位制的表示方式（也可能是無限多個）。

β进制可以應用在[[编码理论]]<ref>{{Citation | last1=Kautz | first1=William H. | title=Fibonacci codes for synchronization control | mr=0191744 | year=1965 | journal=Institute of Electrical and Electronics Engineers. Transactions on Information Theory | issn=0018-9448 | volume=IT-11 | issue=2 | pages=284–292| doi=10.1109/TIT.1965.1053772 }}</ref>及[[準晶體]]模型的描述<ref>{{Citation | last1=Burdik | first1=Č. | last2=Frougny | first2=Ch. | last3=Gazeau | first3=J. P. | last4=Krejcar | first4=R. | title=Beta-integers as natural counting systems for quasicrystals | doi=10.1088/0305-4470/31/30/011 | bibcode=1998JPhA...31.6449B | mr=1644115 | year=1998 | journal=Journal of Physics A: Mathematical and General | issn=0305-4470 | volume=31 | issue=30 | pages=6449–6472| citeseerx=10.1.1.30.5106 }}</ref><ref>{{Citation | last1=Thurston | first1=W.P. | title=Groups, tilings and finite state automata |journal=AMS Colloquium Lectures | year=1989}}</ref>。<!--{{harv|Burdik|Frougny|Gazeau|Krejcar|1998}}-->
==建構==
β进制是[[十進制]]的延伸。十進制的表示法不唯一（例如，1.000... = [[0.999...]]），不過所有有限位數的十進制表示法是唯一的。有限位數β进制就不一定有此特性，例如，在''β'' = ''φ''（[[黃金比例]]）時，''φ'' + 1 = ''φ''。

針對特定實數，選擇其β进制各位數的方式，可以用以下的[[贪心算法]]產生，本質上是來自{{harvtxt|Rényi|1957}}，此處的公式則來自{{harvtxt|Frougny|1992}}。

令{{math|''β'' > 1}}是底數，''x''為非負的實數。令{{math|⌊''x''⌋}}是''x''的[[取整函数]]（小於等於''x''的最大整數），令{{math|1={{mset|''x''}} = ''x'' − ⌊''x''⌋}}是''x''的小數部份。[[存在量化|存在]]一整數''k''使得{{math|''β''<sup>''k''</sup> ≤ ''x'' < ''β''<sup>''k''+1</sup>}}。令
:<math>d_k = \lfloor x/\beta^k\rfloor</math>
且
:<math>r_k = \{x/\beta^k\}.\,</math>
針對{{math|''k'' − 1 ≥ &thinsp;''j'' > −∞}}，定義
:<math>d_j = \lfloor\beta r_{j+1}\rfloor, \quad r_j = \{\beta r_{j+1}\}.</math>

換句話說，''x''的正規''β''進制表示法可以用以下方式得到：先選擇最大的''d''<sub>''k''</sub>，使得{{math|''β''<sup>''k''</sup>''d''<sub>''k''</sub> ≤ ''x''}}，再選擇最大的''d''<sub>''k''−1</sub>，使得{{math|''β''<sup>''k''</sup>''d''<sub>''k''</sub> + β<sup>''k''−1</sup>''d''<sub>''k''−1</sub> ≤ ''x''}}，以此類推。此作法會選擇可以表示''x''，[[字典序]]最大的字串。

若是整數進位制，以上方式會產生一般整數進位制下的數值。因此此建構方式將一般的演算法推廣到非整數的基底''β''。

== 參考文獻 ==
{{Reflist}}

==相關條目==
*[[小数|小數展開式]]
*[[幂级数]]
*[[黄金进制]]：底數為[[黄金比]]φ的进位制
* [[广义的进制系统]]
* {{link-en|Beta編碼器|Beta encoder}}
* {{link-en|奧斯特洛夫斯基記數系統|Ostrowski numeration}}

{{pns}}

[[Category:进位制]]
[[Category:非标准进制系统]]