黄金进制
黄金进制(英語:)是使用黄金比φ作为底数的进位制,其中 φ = 1 + √52 ≈ 1.61803399... 是一个无理数。在英语中,黄金进制也叫做base-φ、golden mean base、phi-base、phinary。在黄金进制下,任何非负整数都约定使用0和1表示,并且不连续使用两个1,这叫做黄金进制的标准形。任何黄金进制的数凡是出现11,就一定可以根据黄金比φ的性质 φ+1=φ2 表示成标准形。例如,11φ = 100φ。
记数系统 | |
---|---|
印度-阿拉伯数字系统 | |
西方阿拉伯数字 阿拉伯文数字 高棉數字 |
印度數字 波羅米數字 泰语数字 |
汉字文化圈記數系統 | |
中文数字 閩南語數字 越南语数字 算筹 |
日語數字 朝鲜文数字 苏州码子 |
字母記數系統 | |
阿拉伯字母數字 亞美尼亞數字 西里爾數字 吉茲數字 |
希伯來數字 希腊数字 阿利耶波多數字 |
其它記數系統 | |
雅典數字 巴比倫數字 古埃及數字 伊特拉斯坎數字 |
玛雅数字 罗马数字 |
依底数区分的进位制系统 | |
1 2 3 4 5 6 7 8 9 10 11 12 15 16 18 20 24 30 32 36 60 64 | |
虽然黄金进制使用无理数作为基底,任何非负整数在黄金进制下都可以表示成有限小数。所有有理数则都可以表示成循环小数。所有数的有限表示都是唯一的,但和十进制一样,整数和有限小数都可以写成无限小数的形式,如十进制中的 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
斐波那契编码
斐波那契编码是与黄金进制关系紧密的计数系统。它只用0和1表示数,每个数位的位值对应斐波那契数。和黄金进制一样,其标准形也不使用“11”。如:
- 30 = 1×21 + 0×13 + 1×8 + 0×5 + 0×3 + 0×2 + 1×1 + 0×1 = 10100010fib.
参见
参考资料
- Bergman, George, , Mathematics Magazine, 1957, 31 (2): 98–110 [2011-01-13], doi:10.2307/3029218, (原始内容存档于2015-11-07)
- Plojhar, Jozef, , Manifold, 1971, 11: 26–30