黃金進制
黃金進制(英語:Golden ratio base)是使用黃金比φ作為底數的進位制,其中 是一個無理數。在英語中,黃金進制也叫做base-φ、golden mean base、phi-base、phinary。在黃金進制下,任何非負整數都約定使用0和1表示,並且不連續使用兩個1,這叫做黃金進制的標準形。任何黃金進制的數凡是出現11,就一定可以根據黃金比φ的性質 φ+1=φ2 表示成標準形。例如,11φ = 100φ。
雖然黃金進制使用無理數作為基底,任何非負整數在黃金進制下都可以表示成有限小數。所有有理數則都可以表示成循環小數。所有數的有限表示都是唯一的,但和十進制一樣,整數和有限小數都可以寫成無限小數的形式,如十進制中的 1 = 0.99999…。
舉例
編輯十進制數 | 用φ的冪表示 | φ進制數 |
---|---|---|
1 | φ0 | 1 |
2 | φ1 + φ−2 | 10.01 |
3 | φ2 + φ−2 | 100.01 |
4 | φ2 + φ0 + φ−2 | 101.01 |
5 | φ3 + φ−1 + φ−4 | 1000.1001 |
6 | φ3 + φ1 + φ−4 | 1010.0001 |
7 | φ4 + φ−4 | 10000.0001 |
8 | φ4 + φ0 + φ−4 | 10001.0001 |
9 | φ4 + φ1 + φ−2 + φ−4 | 10010.0101 |
10 | φ4 + φ2 + φ−2 + φ−4 | 10100.0101 |
轉化到標準形
編輯211.01φ是φ進制數,但並非標準形,因為它含有「11」和「2」,以及1=-1。我們可以根據以下公式將它轉化到標準形:
- 011φ = 100φ
- 0200φ = 1001φ
- 010φ = 101φ
公式的代換過程對結果沒有影響。具體過程如下:
211.01φ 300.01φ 011φ → 100φ 1101.01φ 0200φ → 1001φ 10001.01φ 011φ → 100φ (again) 10001.101φ 010φ → 101φ 10000.011φ 010φ → 101φ (again) 10000.1φ 011φ → 100φ (again)
任意非標準形正數都可以唯一地標準化。這樣處理之後如果第一位是負數,此時需要將每一位數都變成相反數,重新標準化並加上負號。例如:
- 101φ = -101φ = -110.1φ = -1.1φ = -10φ
整數的黃金進制表示
編輯通常所說的整數在黃金進制下是有限小數。例如,整數5轉化成黃金進制的過程如下所示:
- 5以下φ的最高次冪是 φ3 = 1 + 2φ ≈ 4.236;
- 與5求差為5 - (1 + 2φ) = 4 - 2φ ≈ 0.763;
- 0.763以下最大的φ的冪是 φ-1 = -1 + 1φ ≈ 0.618;
- 再次求差,4 - 2φ - (-1 + 1φ) = 5 - 3φ ≈ 0.145
- 0.145以下最大的φ的冪是 φ-4 = 5 - 3φ ≈ 0.145;
- 再次求差得到0
- 於是: 5 = φ3 + φ-1 + φ-4
5用φ進制表示就是1000.1001φ。
這裏其實利用了以下事實:凡φ的冪都可以用整數a、b表示成 a + b φ 的形式。因為 φ2 = φ + 1 、φ-1 = -1 + φ 。如此一來,數之間比大小就容易了。實際上,a + bφ > c + dφ 和 2(a - c) - (d - b) > (d - b) × √5 等價。只需將 φ = (1+√5)/2 代入,稍作處理就可得到這一結果。
數的表示不唯一
編輯和其他進位制相同,黃金進制中也可以用多種形式表示同一個數。就像10進制中0.999...=1,φ進制中0.1010101…φ=1。
- 使用非標準形變換:1 = 0.11φ = 0.1011φ = 0.101011φ = … = 0.10101010…φ
- 使用等比級數展開:1.0101010…φ 等於
- 錯項相減:φ2 x - x = 10.101010…φ - 0.101010…φ = 10φ = φ 所以 x = φ/(φ2 - 1) = 1
這種不唯一是進位制的特徵,1.0000和0.101010…都是標準形。一般地,φ進位制中數最後的1用01循環代替即可得到另一標準形。
有理數的黃金進制表示
編輯在黃金進制中,可以用有限小數或者循環小數表示任意非負有理數,以及從有理數和√5生成的域Q[√5]中的非負元素。其中
相反地,黃金進制中的有限/循環小數都是Q[√5] 中的非負元素。例如:
- 1/2 ≈ 0.010 010 010 010 ... φ
- 1/3 ≈ 0.00101000 00101000 00101000... φ
- √5 = 10.1φ
- 2+(1/13)√5 ≈ 10.010 1000100010101000100010000000 1000100010101000100010000000 1000100010101000100010000000 ...φ
對這一點的證明與十進制中類似。在黃金進制下進行長除法。因為其餘數的可能值是有限個,所以必定會出現循環。例如 1/2 = 1/10.01φ = 100φ/1001φ 進行長除法如下:
.0 1 0 0 1 ________________________ 1 0 0 1 ) 1 0 0.0 0 0 0 0 0 0 0 1 0 0 1 代换 10000 = 1100 = 1011 _______ 于是 10000-1001 = 1011-1001 = 10 1 0 0 0 0 1 0 0 1 _______ etc.
反之,黃金進制中的循環小數都屬於Q[√5]。因為循環部分形成了等比級數,對它求和即可得到Q[√5]的元素。
無理數的黃金進制表示
編輯常見無理數的黃金進制表示如下:
四則運算
編輯在黃金進制中可以和其它進制一樣進行四則運算。加法、減法、乘法的計算方法如下:
加、減、乘
編輯- 先計算,後轉化
- 即先對每一位按十進制數的方法計算,但不進行進位、借位,計算完再轉化為標準形。例如:
- 2+3 = 10.01 + 100.01 = 110.02 = 110.1001 = 1000.1001
- 2×3 = 10.01 × 100.01 = 1000.1 + 1.0001 = 1001.1001 = 1010.0001
- 7-2 = 10000.0001 - 10.01 = 10010.0101 = 1110.0101 = 1001.0101 = 1000.1001
- 避免0和1以外的數
- 更加自然的做法是將數轉化為非標準形,以避免出現需要進位和借位的 1+1 或 0-1 。例如:
- 2+3 = 10.01 + 100.01 = 10.01 + 100.0011 = 110.0111 = 1000.1001
- 7-2 = 10000.0001 - 10.01 = 1100.0001 - 10.01 = 1011.0001 - 10.01 = 1010.1101 - 10.01 = 1000.1001
除法
編輯除了整數以外,所有有理數都不能用有限位φ進制數表示。也就是說,黃金進制中能用有限小數表示的數只有整數或者域Q[√5]中的無理數。兩個整數相除得到有理數的情況已經在上文說明了。
斐波那契進制
編輯斐波那契進制(Fibonaccimal Base)是與黃金進制關係緊密的計數系統。它只用0和1表示數,每個數位的位值對應斐波那契數[1]。和黃金進制一樣,其標準形也不連續使用兩個1。如:
- 30 = 1×21 + 0×13 + 1×8 + 0×5 + 0×3 + 0×2 + 1×1 + 0×1 = 10100010fib.
參見
編輯外部連結
編輯參考資料
編輯- ^ 1.0 1.1 Fibonaccimal Base. onlinejudge.org. [2022-10-06]. (原始內容存檔於2022-10-09).
- ^ Sloane, N.J.A. (編). Sequence A014417 (Representation of n in base of Fibonacci numbers (the Zeckendorf representation of n)). The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.
- Bergman, George, A Number System with an Irrational Base, Mathematics Magazine, 1957, 31 (2): 98–110 [2011-01-13], doi:10.2307/3029218, (原始內容存檔於2015-11-07)
- Plojhar, Jozef, the Good~natured Rabbit~breeder, Manifold, 1971, 11: 26–30