分形/数学/二进制

离散动力系统理论中的二进制分数（数字转换和小数的二进制展开）

记号

一般数学记号

二进制分数是2的负幂的和

$b_{0}.b_{1}b_{2}b_{3}\dots .=\sum _{i=0}^{\infty }b_{i}2^{-i}=b_{0}2^{0}+b_{1}2^{-1}+b_{2}2^{-2}+b_{3}2^{-3}+\dots$

$b_{i}2^{-i}={\frac {b_{i}}{2^{i}}}$

下标数字表示数制（位值记数系统的基数）

$0.1_{2}=0.5_{10}$

$0.1_{10}=(0.0{\overline {0011}})_{2}$

有时使用圆括号以提高清晰度

$(0.1)_{10}=0.1_{10}$

二进制展开的**无限重复**部分用以下表示：

• 圆括号
• 上划线

无限序列用省略号（= 3个点）表示

$0.10(00101010)=0.10{\overline {00101010}}=0.10001010100010101000101010001010100010101000101010\dots$

指数（上标）带或不带括号

• 表示系列重复的次数
• 将用于指示要**重复有限次**的符号（或符号组）

$0.11(11101010)=0.11(11(10)^{3})$

$0.((001)^{88}010)_{2}=0.(001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001010)$

$0.(01^{3})=0.(0111)$

有时会省略开头的零

$.1=0.1$

小数点（一个小点 .）右边的尾随零不影响数字的值，这里将被省略

$0.1(0)=0.1$

特殊记号

程序中使用的特殊记号

• Mandel 程序 使用：0p01，在一般的数学记号中为 0.0(01)。通常 apb = 0.a(b)
• Book 程序 使用：.0(01)，在一般的数学记号中为 0.0(01)。通常 .a(b) = 0.a(b)

前周期和周期

前周期有两个含义

• T = 临界点的周期$z_{cr}=0$
• t = 临界值的周期$z_{cv}=c$

请注意

$t=T-1$

周期 p 对临界值和临界点是相同的

前周期

• 临界值的前周期
  • Wolf Jung 使用：“...通常的约定是使用临界值的前周期。这样做的好处是，在倍增下，临界值的角具有与该点相同的前周期，并且在参数平面中发现了相同的角。”
• 临界点的前周期
  • Pastor 使用临界点的前周期：“所有 Misiurewicz 点在其前周期中都增加了一个单位，因此该 $M_{2,1}$ 给定为 $M_{3,1}$”
  • Demidov
  • Claude Heiland-Allen

关键词

• 周期
  • 二进制展开式（二进制序列）周期部分的最短长度
  • 角度在倍增映射下的轨道长度（十进制比率）= 倍增映射下的周期
• 前周期
  • 二进制展开式（二进制序列）前周期部分的最短长度

二进制展开式的类型

二进制展开式可以是

• 有限的 - 分母为 2 的幂的十进制比率数。请注意，它也具有相等的无限前周期表示
• 无限的
  • 周期性的：前周期 = 0，周期 > 0，分母为奇数且不是 2 的幂的有理数
  • 前周期性的（= 最终周期性的）：前周期 > 0，周期 > 0，分母为偶数的有理数
  • 非周期性的：前周期 = 0，周期 = 0（或无穷大），无理数

如果十进制数是有理数，请检查其形式。它是否处于最简形式（不可约 = 化简 = 分子和分母互质）？

如何找到展开式的类型

/*
 gcc i.c -Wall -Wextra -lm

 https://stackoverflow.com/questions/108318/how-can-i-test-whether-a-number-is-a-power-of-2
 (n>0 && ((n & (n-1)) == 0))

 https://stackoverflow.com/questions/160930/how-do-i-check-if-an-integer-is-even-or-odd
if (x % 2) {  } //  x is odd 
 An integer is even if it is a multiple of two, power of 2, true if num is perfectly divisible by 2 :  mod(24,2) = 0
 and odd if it is not.

*/


#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <assert.h>




int main(void)
{
	int n = 1;
	int d = 4; // 
	// boolean flag
	int is_odd = 0;
	int is_POT = 0;
	//int type; 
	
	//
	assert( n > 0); 
	assert( d > 0);
	assert( n < d); // proper fraction
	
	
	if (d % 2) 
		{	// d % 2 > 0  	
			fprintf(stdout, "denominator %d is odd\n", d); // parzysty
			is_odd = 1;
		
		}
		else { // d % 2  = 0 
			fprintf(stdout, "denominator %d is even\n", d); // nieparzysty
			is_odd = 0;
		}
		
	if (d>0 && ((d & (d-1)) == 0))
		{ 
			fprintf(stdout, "denominator %d is power of 2 ( POT) = 2^%d\n", d, (int) log2(d));
			is_POT = 1;}
		else { 
			fprintf(stdout, "denominator %d is not the power of 2\n", d);
			is_POT = 0;}
	
	// https://wikibooks.cn/wiki/Fractals/Mathematics/binary#preperiod_and_period
	if ( is_odd == 0 && is_POT == 1)
		{
			fprintf(stdout, "Binary expansion of %d/%d is finite and has equal infinite representation\n", n,d);
			fprintf(stdout, "denominator is even and POT\n");
			}
	
	// preperiodic ( = eventually periodic) : preperiod > 0, period > 0, rational number with even denominator
	if (is_odd == 0 && is_POT == 0) 
		{
			fprintf(stdout, "Binary expansion of %d/%d is preperiodic\n", n,d);
			fprintf(stdout, "denominator is even and not POT\n");
		}
	
	// periodic : preperiod = 0, period > 0, rational number with odd denominator which is not a power of 2
	if (is_odd == 1 && is_POT == 0) 
		{
			fprintf(stdout, "Binary expansion of %d/%d is periodic\n", n,d);
			fprintf(stdout, "denominator is not even (odd) and not POT\n");
		}	
		
		
	return 0;
}

描述

有限的

当且仅当十进制比率 m/n 可以写成分母 n 为 2 的幂（也是偶数）的分数时，它才具有有限的二进制表示。

${\frac {m}{n}}={\frac {m}{2^{t}}}$

其中m为整数，t为非负整数。

换句话说

• 二进制算术中的分数只有当分母中唯一的素因子为2时才会终止，即二进分数。
• 二进分数恰好是那些具有有限二进制展开式的数。

这是因为二进制分数的构造方式

$r=b_{0}.b_{1}b_{2}b_{3}\dots .=\sum _{i=0}^{\infty }{\frac {b_{i}}{2^{i}}}={\frac {b_{0}}{2^{0}}}+{\frac {b_{1}}{2^{1}}}+{\frac {b_{2}}{2^{2}}}+{\frac {b_{3}}{2^{3}}}+\dots$

单位分数的二进制展开式

$r={\frac {1}{2^{t}}}=0.\overbrace {b...b} ^{t-1}1=0.0^{t-1}1$

单位分数1/(2^t)的二进制展开式

t	${\frac {1}{2^{t}}}$	二进制展开式 = $0.0^{t-1}1$
0	1/1	1.0
1	1/2	0.1
2	1/4	0.01
3	1/8	0.001
4	1/16	0.0001
5	1/32	0.00001
6	1/64	0.000001
7	1/128	0.0000001
8	1/256	0.00000001
9	1/512	0.000000001
10	1/1024	0.0000000001
34	1/17179869184	0.0000000000000000000000000000000001

这种有限的二进制展开式具有第二个相等的表示：无限且前周期！因为这两种表示具有不同的前周期和周期，所以在离散动力系统理论中最好使用无限版本。

没有异常精确的二进分数近似的实数。红色圆圈包围了在误差${\tfrac {1}{6}}/2^{i}$内被形式为$n/2^{i}$的二进分数近似的实数。对于圆圈外的康托尔集中的数，所有二进分数近似都具有更大的误差。

无限的

• 周期性：前周期 = 0，周期 > 0
• 前周期性：前周期 > 0，周期 > 0
• 非周期性：前周期 = 0，周期 = 0

周期性

这里十进制数是有理数，其分母为奇数。

有两种可能的类型（完整分类）

• 分母是奇素数（除了2以外的素数）
• 分母是奇合数

有一个特殊情况，它不属于前两种情况：分母是比2的幂小1的整数。

$r={\frac {1}{2^{p}-1}}=0.((0)^{p-1}1)$

因此二进制分数具有

• 周期 = p
• 前周期 = 0

二进制分数1/(2^p-1)在二进制展开式中的形式与分数1/(2^p)相同，但它是重复的。

例如1/(2^5)=0.00001和1/(2^5-1)=0.(00001)

单位分数1/(2^p -1)的二进制展开式。素数分母为绿色，合数分母为黑色。

p	${\frac {1}{2^{p}-1}}$	factors(denominator)	二进制展开式 = $0.((0)^{p-1}1)$
2	1/3	3	0.(01)
3	1/7	7	0.(001)
4	1/15	3*5	0.(0001)
5	1/31	31	0.(00001)
6	1/63	3*3*7	0.(000001)
7	1/127	127	0.(0000001)
8	1/255	3*5*17	0.(00000001)
9	1/511	7*73	0.(000000001)
10	1/1023	3*11*31	0.(0000000001)
34	1/17179869183	3*43691*131071	0.(0000000000000000000000000000000001)

分母为奇素数

分母为奇素数（除2以外的素数）的有理数

约化后的有理分数 m/n 的二进制展开式的周期 等于 2 模 n 的乘法阶

$k=Period_{2}(m/n)={ord}_{n}(2)$

最长的可能周期 k 为

$k=n-1$

当 2 是分母 n 的原根时

在 Maxima CAS 中，可以使用

• ifactors(n)
• zn_order(2,n)
• zn_primroot_p(2,n)

分母为素数的单位分数。最长可能周期为红色

${\frac {m}{n}}$	二进制展开式	$k={period}_{2}$
1/3	0.(01)	2
1/5	0.(0011)	4
1/7	0.(001)	3
1/11	0.(0001011101)	10
1/13	0.(000100111011)	12
1/17	0.(00001111)	8
1/23	0.(00001011001)	11
1/29	0.(0000100011010011110111001011)	28
1/31	0.(00001)	5
1/37	0.(000001101110101100111110010001010011)	36
1/41	0.(00000110001111100111)	20
1/43	0.(00000101111101)	14
1/47	0.(00000101011100100110001)	23
1/53	0.(0000010011010100100001110011111011001010110111100011)	52
1/59	0.(0000010001010110110001111001011111011101010010011100001101)	58
1/61	0.(000001000011001001011100010100111110111100110110100011101011)	60
1/67	0.(000000111101001000100110001101010111111000010110111011001110010101)	66
1/71	0.(00000011100110110000101011010001001)	35
1/73	0.(000000111)	9
1/79	0.(000000110011110110010001110100101010001)	39
1/83	0.(000000110001010110010111001000011110110101111110011101010011010 0011011110000100101)	82
1/89	0.(00000010111)	11
1/97	0.(000000101010001110100000111111010101110001011111)	48
1/9949	0.()	9948

使用knowledgedoor 计算器：convert_a_ratio_of_integers计算的 1/9949（它允许在新数字中计算最多 100000 个小数位）

 1/9949 = 0.(0.000000000000011010010110010100100110010000110010100010010100000 000011000101100111011010011110111101111011000001010110000010111001 010000111100110101000010000011010101010000101010101101101011111001 000001101101111011000111111011101000000010110101001001011101100111 000011011011011011111001100010101001110100110111110000100111001101 101110001001111100011111001101100100010001100100110000110111010001 010100101101010000101110000000011110011101110011110100001111011010 011011101011001000011100100011111100100100111110011100110001111100 011011111010110001101100110010101010100010111110110100101010001011 000110100101111111011111111000110010111001010111100010011010001011 100111100001111001001111101101110010000100010000100010111001000011 110001101010101110111010111011111111100000101101011111100010100100 000011111111010000001111100010101010101001100100011001110011101111 010011001110100100011111111110111110001000001100100000010110000001 101010001101111111000010001111101011101110010100101001100011100101 000111000110000110101100111111011011010110111101010110110010101001 101110010010001011011101101001100001100001010111011111000111011001 000010101111110010111011011011010010000001001010111011011110100100 110011101111101101100100111001000110001111110000101010100000100000 101110101110100101100001110110110001100111110110011110101011110011 101011001011101111010110100001010111000100110001000100011100011111 000000011001000111010001101000011110000000001010101101000100010111 100010110100100001111100001000001010000010010000000110000100101001 001111110100010111101001011010000111000101101100010110101010110101 000110001010110100011110101001010101100101010000001001110001110010 001001001100101110110000001110111011001001001010101011000000100111 111011110101001101111111011100100110000000010100100101011100000101 111001000111011110110011101000010011010011000110010101100001100011 000000111000011001110010000101111001111100001011011100110100110100 111000001010111101100010010100011010101111000001100001100100101010 010001101100001011001001000100000101011011011110010111101000100101 011010011100011111110101000101110000011110001010000011000100110010 101101110101110001011001011100010001011010111000011111100010111110 011010010011110110100000010101001100111101100100110010100000101010 100111000110010011111000001001101110011111010110100111111100101001 111010101000101001000111100101011001001101011100110111010010111110 000110100011000111000011101000100111000011110101110010001110001000 111010100111011010000100100111100110011011000101010000010110111100 111100011100010101001000000001011000111011010101100001001000101010 100011110011100001010011010111101000001011000100000111111001100100 010011001110001010001001101010010111110111011001111110000010000001 010001100001000011101110010111111100010110001001111001001100011010 111111011111011110011100100100110001010001100111101001010011100001 100000100010110010011110001100100001001010101110010011011010100000 100111010100010011101111000110000011011010001100110110100100110111 000010100000001001101011001100100100000011001010100011100110010110 001001000100011111110001110010111101111001010111111100110000100000 001101110010101011110010000001110010011100111101011110001100111011 100001000010111001101011010011001001101000010100000111110010111110 101110000100100101111101000001110010110111010011110010110011001100 010011100101001101101011101011110110100011100111111111100010010110 111000110100111101000111001001011001011111100100001101011101010001 101001010010101100110011111001100101111100100111011100100010101101 100010000000101001111111100100110100111110110000100010101011111000 100111010111100110100001101010110101100000100001001001000100111010 001000000111100100001010001010011111000100100000100110011111100111 000101111001100001110101001000001110100100000101101000101001100001 111011101101110011101101101001110101010010000110111011110011111110 111100011110110011001101111100111110100000000100101111000000101100 111000000001000101001010100110000100011100000100101010000100100001 000000110101111011101100001010010100010111011100001110111100110010 100011111101011001101011000101111110011110000000111111011001101101 100100000100011001100110100100001000111011011100000110101101110100 001000000000001001111000010111101110010110010010111100110111100000 001001010000110110001111011100111001110001000100000010001000101011 110010110110011111000110001001111111110010000000001001000011101011 000101001001110001010111110010111000001000011111011100011000110101 001010010010010011101100100111111101011110100111010001110101101001 001010011101110101011101101000101100110100101110010010100101110011 111110000111110010001010000001011011011001011011011100101110001111 010011000001011001010101101011110101101110111011010110010101110101 010011110000010101000110010111111111101000111100011101111110100001 010011110001111110011111101010011000101100000110100111001110100010 110110100101101011101111001001010110001100110001101000101011001011 010101000000001100110000110011111110100010001000011110100111101100 001011111101110000101110100111111111111100101101001101011011001101 111001101011101101011111111100111010011000100101100001000010000100 111110101001111101000110101111000011001010111101111100101010101111 010101010010010100000110111110010010000100111000000100010111111101 001010110110100010011000111100100100100100000110011101010110001011 001000001111011000110010010001110110000011100000110010011011101110 011011001111001000101110101011010010101111010001111111100001100010 001100001011110000100101100100010100110111100011011100000011011011 000001100011001110000011100100000101001110010011001101010101011101 000001001011010101110100111001011010000000100000000111001101000110 101000011101100101110100011000011110000110110000010010001101111011 101111011101000110111100001110010101010001000101000100000000011111 010010100000011101011011111100000000101111110000011101010101010110 011011100110001100010000101100110001011011100000000001000001110111 110011011111101001111110010101110010000000111101110000010100010001 101011010110011100011010111000111001111001010011000000100100101001 000010101001001101010110010001101101110100100010010110011110011110 101000100000111000100110111101010000001101000100100100101101111110 110101000100100001011011001100010000010010011011000110111001110000 001111010101011111011111010001010001011010011110001001001110011000 001001100001010100001100010100110100010000101001011110101000111011 001110111011100011100000111111100110111000101110010111100001111111 110101010010111011101000011101001011011110000011110111110101111101 101111111001111011010110110000001011101000010110100101111000111010 010011101001010101001010111001110101001011100001010110101010011010 101111110110001110001101110110110011010001001111110001000100110110 110101010100111111011000000100001010110010000000100011011001111111 101011011010100011111010000110111000100001001100010111101100101100 111001101010011110011100111111000111100110001101111010000110000011 110100100011001011001011000111110101000010011101101011100101010000 111110011110011011010101101110010011110100110110111011111010100100 100001101000010111011010100101100011100000001010111010001111100001 110101111100111011001101010010001010001110100110100011101110100101 000111100000011101000001100101101100001001011111101010110011000010 011011001101011111010101011000111001101100000111110110010001100000 101001011000000011010110000101010111010110111000011010100110110010 100011001000101101000001111001011100111000111100010111011000111100 001010001101110001110111000101011000100101111011011000011001100100 111010101111101001000011000011100011101010110111111110100111000100 101010011110110111010101011100001100011110101100101000010111110100 111011111000000110011011101100110001110101110110010101101000001000 100110000001111101111110101110011110111100010001101000000011101001 110110000110110011100101000000100000100001100011011011001110101110 011000010110101100011110011111011101001101100001110011011110110101 010001101100100101011111011000101011101100010000111001111100100101 110011001001011011001000111101011111110110010100110011011011111100 110101011100011001101001110110111011100000001110001101000010000110 101000000011001111011111110010001101010100001101111110001101100011 000010100001110011000100011110111101000110010100101100110110010111 101011111000001101000001010001111011011010000010111110001101001000 101100001101001100110011101100011010110010010100010100001001011100 011000000000011101101001000111001011000010111000110110100110100000 011011110010100010101110010110101101010011001100000110011010000011 011000100011011101010010011101111111010110000000011011001011000001 001111011101010100000111011000101000011001011110010101001010011111 011110110110111011000101110111111000011011110101110101100000111011 011111011001100000011000111010000110011110001010110111110001011011 111010010111010110011110000100010010001100010010010110001010101101 111001000100001100000001000011100001001100110010000011000001011111 111011010000111111010011000111111110111010110101011001111011100011 111011010101111011011110111111001010000100010011110101101011101000 100011110001000011001101011100000010100110010100111010000001100001 111111000000100110010010011011111011100110011001011011110111000100 100011111001010010001011110111111111110110000111101000010001101001 101101000011001000011111110110101111001001110000100011000110001110 111011111101110111010100001101001001100000111001110110000000001101 111111110110111100010100111010110110001110101000001101000111110111 100000100011100111001010110101101101101100010011011000000010100001 011000101110001010010110110101100010001010100010010111010011001011 010001101101011010001100000001111000001101110101111110100100100110 100100100011010001110000101100111110100110101010010100001010010001 000100101001101010001010101100001111101010111001101000000000010111 000011100010000001011110101100001110000001100000010101100111010011 111001011000110001011101001001011010010100010000110110101001110011 001110010111010100110100101010111111110011001111001100000001011101 110111100001011000010011110100000010001111010001011)

非单位分数（分子大于 1）具有：

• 相同的周期 k（周期部分的长度）
• 如果$k=\phi (n)$
  • 则周期部分相对于对应的单位分数循环移位
  • 否则存在$\phi (n)/k$ 个不同的循环（周期部分），所有循环的长度均为 k

其中

• $\phi$ 是欧拉函数。在 Maxima CAS 中，它是 totient(n)

分母是奇合数

分母为合数

${\frac {m}{n}}$	factors(n)	二进制展开式	${period}_{2}$
1/9	3*3	0.(000111)	6
1/15	3*5	0.(0001)	4
1/21	3*7	0.(000011)	6
1/33	3*11	0.(0000011111)	10
1/39	3*13	0.(000001101001)	12
1/81	3^4	0.(000000110010100100010110000111111001101011011101001111)	54
1/267	3*89	0.(0000000011110101011101)	22
1/4369	17*257	0.(0000000000001111)	16

${\frac {m}{n}}$ 的二进制展开式的周期 = 倍增映射下角度 ${\frac {m}{n}}$ 的周期

困难案例：1/99007599 = 1 / (3*33002533)，写成二进制分数，具有近 5000 万个 0 和 1 的周期

测试

• knowledgedoor 计算器 - “新数字中有超过 100000 个小数位。很抱歉，我们不得不中止计算以控制服务器上的负载。”
• 在 Maxima CAS 中：zn_order(2,99007599) = 33002532

前周期

这里分数 r 的分母 n

$r={\frac {m}{n}}$

是偶数

$n=2^{t}q$

且 q 为奇数。

按前周期和周期分类

$\{t,p\}$ 其中t为前周期，p为周期

• $\{1,1\}=0.0(1)=1/2=0.5$
• $\{1,2\}$
  • $0.0(01)=1/6=2/12=0.1666666666666667$
  • $0.0(10)=1/3=4/12=0.3333333333333333$
  • $0.1(01)=2/3=8/12=0.6666666666666667$
  • $0.1(10)=5/6=10/12=0.8333333333333333$
• $\{2,1\}$
  • $0.00(1)=1/4=0.25$
  • $0.10(1)=3/4=0.75$
• $\{2,2\}$
  • $0.00(01)=1/12=0.0833333333333333$
  • $0.01(10)=5/12=0.4166666666666667$
  • $0.10(01)=7/12=0.5833333333333333$
• $\{4,4\}$
  • $0.0110(1001)=99/240=0.4125$
  • $0.1001(0110)=141/240=0.5875$
• $\{5,2\}$
  • $0.01101(10)=41/96=0,42708333333333333$

根据q的类型分类

• q = 1，二进分数。它与无限等价表示的有限二进制分数相等。参见下表中的黑色行
• q是素数，参见下表中的绿色行
  • q = 2^p - 1 则周期 = p
  • 如果q不是一个整数，则周期p =（重复部分的最小长度）$p=\phi (q)$
• q是合数，周期p“与分母q相同。它要么是Phi(q)，要么是Phi(q)的真因子。当您反复将1/q加倍直到得到1/q时，您可以用数值方法确定它。”（Wolf Jung）。参见下表中的红色行

具有偶数分母的分数的二进制展开 1/(2n)

k	${\frac {1}{2k}}$	factors(2k) = q*2^t	无限二进制展开 $=0.\overbrace {b...b} ^{t}(\overbrace {b...b} ^{p})$	前周期，周期
1	1/2	2	0.0(1)	1,1
2	1/4	2^2	0.00(1)	2,1
3	1/6	2*3	0.0(01)	1,2
4	1/8	2^3	0.000(1)	3,1
5	1/10	2*5	0.0(0011)	1,4
6	1/12	2*2*3	0.00(01)	2,2
7	1/14	2*7	0.0(001)	1,3
8	1/16	2^4	0.0000(1)
9	1/18	2*9	0.0(000111)	1,6
10	1/20	2*2*5	0.00(0011)	2,4
11	1/22	2*11	0.0(0001011101)	1,10
15	1/30	2*3*5	0.0(0001)	1,4
21	1/42	2*3*7	0.0(000011)	1,6
27	1/54	2*3*9	0.0(000010010111101101)	1,18
33	1/66	2*3*11	0.0(0000011111)	1,10
54	1/108	2*2*3*9	0.00(000010010111101101)	2,18
66	1/132	2*2*3*11	0.00(0000011111)	2,10

q是比2的幂小1的整数

如果q是比2的幂小1的整数（偶数）

$q=2^{p}-1$

则分数r具有以下形式

$r={\frac {m}{n}}={\frac {m}{2^{t}(2^{p}-1)}}=0.\overbrace {b...b} ^{t}(\overbrace {b...b} ^{p})$

具有

• 周期（重复部分的最小长度）$p$
• 前周期（非重复部分的长度）= t

示例

${\frac {1}{6}}={\frac {1}{2*3}}={\frac {1}{2(2^{2}-1)}}={0.0(01)}_{2}$

${\frac {7}{24}}={\frac {7}{2^{3}*3}}={\frac {7}{2^{3}(2^{2}-1)}}={0.010(01)}_{2}$

${\frac {9}{56}}={\frac {9}{2^{3}*7}}={\frac {9}{2^{3}(2^{3}-1)}}={0.001(010)}_{2}$

如何检查q是否为比2的幂小1的整数

$q=2^{k}-1$

$q+1=2^{k}$

$k={log}_{2}(q+1)$

在Maxima中可以使用函数

   Give_k(q):=float(log(q+1)/log(2));

如果k接近整数（小数部分为0或接近0）

• 那么 $q=2^{k}-1$ 并使用上述方法
• 否则使用以下方法

q是一个素数

如果 $q\neq 2^{k}-1$那么分数r

$r={\frac {m}{n}}={\frac {m}{2^{t}q}}=0.\overbrace {b...b} ^{t}(\overbrace {b...b} ^{k})$

其中 

• q为奇数
• $\phi$ 是欧拉函数。在 Maxima CAS 中，它是 totient(n)

具有

• 周期（重复部分的最小长度） $k=\phi (q)$
• 前周期（非重复部分的长度）= t

示例

${\frac {9}{20}}={\frac {9}{2^{2}5}}={0.01(1100)}_{2}$ 这里周期 $=\phi (5)=4$ 且前周期t = 1

${\displaystyle {0.1416}_{10}={\frac {1416}{10000}}={\frac {117}{1250}}={\frac {117}{2(5^{4})}}={0.0(00101111111011000101011011010101110011111010101011001101100111101000001111100100001001011010111011100110001100011111100010100000100100000010110111100000000011010001101101110001011101011000111000100001100101100101001010111101001111000011011000010001001101000000010011101010010010101000110000010101010011001001100001011111000001101111011010010100010001100111001110000001110101111101101111110100100001111111110010111001001000111010001010011100011101111001101001101011010100001011000011110010011110111011)}_{2}}">$

这里

• 周期 $=\phi (5^{4})=500$
• 前周期 = 1

非周期性

如果展开式为

• 无限的
• 非周期性（周期 = 0 或无穷大）

那么它是一个无理数。

无理数特征（非完整分类）

• 正规性 - 维基百科中的正规数 / 非正规数（序列）
• 线性化: 不可线性化 / 可线性化，检查Brjuno条件
• 超越数（非代数数）/代数数

应用

• 内角

正规

随机序列

• 伪随机
• 真随机

来自随机数生成器的示例

• 10字节：10001000111010111111001111010111101000110001010110010010011111100101110101011001
• 15字节：100110100001100101010100001010100110110000100111001100110001101100101111100001001111101001011011101011110100011011000000
• 20字节：1010100101110110001100111101101001001100001011111011001010000100100110010000001010110000101100100111111111011000001001110110000110111011100001101110001000101110

二进制Champernowne常数 C2 = 110111001011101111000100110101011110011011110111110000100011001010011101001010110110101111

非正规

二进制刘维尔常数（二进制刘维尔数）

$L=\sum _{n=1}^{\infty }2^{-n!}={\frac {1}{2^{1!}}}+{\frac {1}{2^{2!}}}+\cdots +{\frac {1}{2^{n!}}}+\cdots ={\frac {1}{2}}+{\frac {1}{2^{2}}}+{\frac {1}{2^{6}}}+\cdots +{\frac {1}{2^{n!}}}+\cdots =0.11000100000000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001\ldots$

其中

• ! 表示阶乘
• $\sum$ 表示无限级数的和

因此，位置上的二进制数字

$1,2,6,24,120,720,5040,40320,362880,39916800,479001600\ldots$

为1，其他为0。

Thue-Morse序列 = Prouhet-Thue-Morse常数的二进制展开

$\tau =\sum _{i=0}^{\infty }{\frac {t_{i}}{2^{i+1}}}={0.01101001100101101001011001101001\ldots }_{2}$

其中

• $t_{i}$ 是Prouhet-Thue-Morse序列的第i个元素

它是通过以0开头，然后连续附加到目前为止获得的序列的布尔补码来获得的。

按如下方式定义0和1的字符串序列：

$t_{0}=0$

$t_{n+1}=t_{n}{\overline {t_{n}}}$

其中

• ${\overline {t}}$ 表示将x中的所有0更改为1，反之亦然

前5个序列

$t_{0}=0$

$t_{1}=01$

$t_{2}=0110$

$t_{3}=01101001$

$t_{4}=0110100110010110$

兔子常数（兔子序列的极限）由连分数给出

$R=[0,2^{F_{0}},2^{F_{1}},2^{F_{2}},2^{F_{3}},...]=0.1011010110110...$

其中

• $F_{n}$ 是斐波那契数，其中 $F_{0}$ 取为 0

多种表示

这些表示

• 在一般意义上是相等的，因为它们给出相同的十进制小数
• 此处不相等，因为二进制分数具有不同的周期/前周期，因此描述了不同的动力系统

周期性

周期性角度有多种可能的写法，其中一种具有最短周期的写法是特殊的

$1/3=.0101010101010101...=.(01)=.(0101)=.(010101)=...$

所以“周期”实际上是指最小可能的周期

在倍增映射下1/3的轨道是周期性的{1/3 , 2/3 }

前周期

前周期性角度有多种可能的写法（无限种形式），其中一种具有最短前周期的写法是特殊的

${\frac {1}{6}}=0.0(01)=0.00(10)=0.001(01)=...$

${\frac {3}{14}}=0.0(011)=0.00(110)$

${\frac {1}{5}}=0.0{\overline {0110}}=0.{\overline {0011}}$

有限的

• 每个非零的有限二进制数（= 分母为奇数且为2的幂的rational number）具有两个相等的表示
• 二进制定点小数的表示不是唯一的；除了0之外，每个二进制定点小数都有一个有限表示和一个无限表示（忽略末尾的0）。例如，0.11₂ = 0.10111...₂，给出了3/4的两种不同的表示。二进制定点小数是唯一其二进制展开式不唯一的数。

$0.0^{t-1}1_{2}=0.0^{t}(1)_{2}$

单位分数1/(2^p)的二进制展开

t	十进制 ${\frac {1}{2^{t}}}$	二进制有限 = $0.0^{t-1}1$	二进制无限 = $0.0^{t}(1)$
0	1/1	1.0	0.(1)
1	1/2	0.1	0.0(1)
2	1/4	0.01	0.00(1)
3	1/8	0.001	0.000(1)
4	1/16	0.0001	0.0000(1)
5	1/32	0.00001	0.00000(1)
6	1/64	0.000001	0.000000(1)
7	1/128	0.0000001	0.0000000(1)
8	1/256	0.00000001	0.00000000(1)
9	1/512	0.000000001	0.000000000(1)
10	1/1024	0.0000000001	0.0000000000(1)
34	1/17179869184	0.0000000000000000000000000000000001	0.0000000000000000000000000000000000(1)

示例

• 来自程序Mandel的“角度1/4或01具有前周期=2和周期=1”。此处使用有限版本

二进制数与动力系统之间的关系

映射

• 二进制小数，倍增映射 = 左移 = 伯努利移位
• 复数，复二次映射

倍增映射

“映射$\lambda :\mathbb {R} /\mathbb {Z} \to J_{c}$称为Caratheodory半共轭，其关联恒等式为$\lambda (2*t)=f_{c}(\lambda (t))$（在2次情况下）。此恒等式使我们能够轻松跟踪外部射线的正向迭代及其在$J_{c}$中的着陆点，方法是将它们相关联的外部射线的角度加倍模1。” Mary Wilkerson

分数在倍增映射下的轨道，用于

• 十进制有理分数
  • 分母为奇数的分数是周期性的
  • 分母为偶数的分数是前周期性的
• 十进制无理分数是非周期性的且稠密的

外部角与二次多项式的二进制分解渲染之间的关系

• 移除第一个比特等同于模1加倍

当追踪外部射线并穿过驻留带（逃逸时间水平集的边界）时

• 向内（朝向Julia/Mandelbrot集）：在末尾添加比特
• 向外（朝向无穷远点）：在开头添加比特

外部角的二进制展开式

• 
  向外收集比特
• 
  展开圆平面的二进制分解
• 
  f(z) = z^2的动态平面的二进制分解

外部角

有两种有理角（十进制分数）

• 当分母为奇数时，二进制数字序列将为周期性，并且该角度在倍增下是周期性的。具有此角度的动态射线落在Julia集的周期点上。参数射线落在双曲分量的根上。
• 当分母为偶数时，二进制数字序列将为前周期性，并且该角度在倍增下是前周期性的。动态射线落在Julia集的前周期点上，参数射线落在Misiurewicz点上。

点与外部角之间的关系？

在白色时添加0，在黑色时添加1。

使用二进制分解

• 从图像开始未知位置并找到外部角
• 从角度开始并找到匹配的位置

落在z = −0.15255 + 1.03294i处的射线的外部参数为：

$(\theta _{20}^{-},\theta _{20}^{+})=(0.{\overline {00110011001100110100}},0.{\overline {00110011001101000011}})$

其中

$\theta _{20}^{-}=0.{\overline {00110011001100110100}}_{2}=0.{\overline {20000095367522590181913549340772}}_{10}={\frac {209716}{1048575}}={\frac {209716}{2^{20}-1}}$

收集比特

收集比特当在Mandelbrot/Julia集外部的二进制分解上追踪外部射线时，外部角的二进制展开式。

射线的外部角：图像显示了如何收集外部角二进制展开式的比特。当向外追踪射线时：在开头添加比特

另请参阅

• 二进制分解
  • 参数平面
  • 动态平面
• 从二进制分解中读取比特 = 收集外部角二进制展开式的比特

模式

模式在缩放（特别是深度缩放）时，被雕刻在Mandelbrot集边界的复杂形状中。缩放反映在复杂动力学中，特别是在每个子Mandelbrot集副本的尖端上着陆的外部射线对的二进制展开式中，每个副本的中心都是一个阶段。

转换

• 将二进制分数转换为十进制比率
• 将十进制分数转换为二进制
• knowledgedoor计算器

所有十进制分数都可以精确转换为二进制吗？

并非全部。只有分母为2的幂（有限）的那些具有精确的十进制表示。“在其他所有情况下，表示中都会存在误差。误差的大小取决于用于表示它的位数。”

十进制到二进制

#include <stdio.h>
#include <stdlib.h> // malloc
#include <limits.h> // INT_MAX
#include <assert.h>
#include <math.h>

/* 

 gcc d.c -Wall -Wextra -lm
 
 
 example input fractions in wikibooks
 /Fractals/Mathematics/binary
 
*/

int nMax;

/*
https://stackoverflow.com/questions/19738919/gcd-function-for-c
The GCD function uses Euclid's Algorithm. 
It computes A mod B, then swaps A and B with an XOR swap.
*/
int gcd(int a, int b)
{
    int temp;
    while (b != 0)
    {
        temp = a % b;

        a = b;
        b = temp;
    }
    return a;
}


/*
 n/d -> n_new/d_new
 
*/

int give_reduced_fraction(const int n, const int d, int * n_new, int *d_new){


	int divisor = gcd(n,d);
	if (divisor != 1) {
		*n_new = n / divisor;
		*d_new = d / divisor;}
		
		else {
			*n_new = n;
         		*d_new = d;
		}
	return 0;
}
/*
Binary expansion can be :
* finite - decimal ratio number with even denominator which is a power of 2. Note that it has also equal infinite preperiodic representation
* infinite
** periodic : preperiod = 0, period > 0, rational number with odd denominator which is not a power of 2
** preperiodic ( = eventually periodic) : preperiod > 0, period > 0, rational number with even denominator
** aperiodic : preperiod = 0, period = 0 ( or infinity), irrational number

input is a rational number t = n/d so 
here  are only 2 types of result:
* 0 = preperiodic ( = eventually periodic) : preperiod > 0, period > 0, rational number with even denominator
* 1 = periodic : preperiod = 0, period > 0, rational number with odd denominator which is not a power of 2
*/

int give_dynamic_type(const int n, const int d){

	// boolean flag
	int is_odd = 0;
	int is_POT = 0;
	
	if (d % 2) 
		{	// d % 2 > 0  	
			fprintf(stdout, "denominator %d is odd\n", d); // parzysty
			is_odd = 1;
		
		}
		else { // d % 2  = 0 
			fprintf(stdout, "denominator %d is even\n", d); // nieparzysty
			is_odd = 0;
		}
		
	if (d>0 && ((d & (d-1)) == 0))
		{ 
			fprintf(stdout, "denominator %d is power of 2 ( POT) = 2^%d\n", d, (int) log2(d));
			is_POT = 1;}
		else { 
			fprintf(stdout, "denominator %d is not the power of 2\n", d);
			is_POT = 0;}
	
	//  wikibooks: Fractals/Mathematics/binary#preperiod_and_period
	if ( is_odd == 0 && is_POT == 1)
		{
			fprintf(stdout, "Binary expansion of %d/%d is finite and has equal infinite preperiodic representation\n", n,d);
			//fprintf(stdout, "denominator is even and POT\n");
			return 0;
			}
	
	// preperiodic ( = eventually periodic) : preperiod > 0, period > 0, rational number with even denominator
	if (is_odd == 0 && is_POT == 0) 
		{
			fprintf(stdout, "Binary expansion of %d/%d is preperiodic\n", n,d);
			//fprintf(stdout, "denominator is even and not POT\n");
			return 0;
		}
	
	// periodic : preperiod = 0, period > 0, rational number with odd denominator which is not a power of 2
	if (is_odd == 1 && is_POT == 0) 
		{
			fprintf(stdout, "Binary expansion of %d/%d is periodic\n", n,d);
			//fprintf(stdout, "denominator is not even (odd) and not POT\n");
			return 1;
		}
		
		
	return 0;
}




int give_period(const int n0, const int d0){

	int n = n0;
	int d = d0;
	
	int i;
	int iMax = 20; // period_max 
	
	int period = 0;

	// printf(" i\t numerator/denominator \n"); // header 

	for ( i=0 ; i< iMax; i++){
		// printf("%3d:\t %3d / %3d \n", i, n, d);
     
     
		// check signed integer overflow before it will happen
		if ( n > nMax ) 
		{printf(" signed integer overflow will happen = wrap; use extended precision \n"); return 1;}
                               
		// angle doubling map modulo 1 
		n = 2*n;
		n = n % d;   
		 // 
		if (n == n0) {
			period = i+1; 
			// printf(" preperiod = 0 and period of fraction under doubling map is %d\n", period); 
			return period;}
	
	}
	return 0; // period not found, maybe period > iMax
}

int give_periodic_orbit(const int period, int n, int d,  int orbit[]){
	
	int i;
	int iMax = period; // 
	for ( i=0 ; i< iMax; i++){
		orbit[i] = n;
     
     
		// check signed integer overflow before it will happen
		if ( n > nMax ) 
		{printf(" signed integer overflow will happen = wrap; use extended precision \n"); return 1;}
                               
		// angle doubling map modulo 1 
		n = 2*n;
		n = n % d;   
		 
	}
	return 0;


}

int give_preperiod(const int period, const int n0, const int d0,  int orbit[]){

	int n = n0;
	int d = d0;
	
	int i;
	int iMax = period; // 
	for ( i=0 ; i< iMax; i++){
		if (orbit[i] == n) return i;
		// angle doubling map modulo 1 
		n = 2*n;
		n = n % d; }
		
	return 0;

}




/*
input : reduced proper rational fraction in t = n0/d0
output
* perperiod as a result
* period as a pointer

*/
int give_preperiod_and_period(const int n0, const int d0, int *period){
	
	int n = n0;
	int d = d0;
	
	*period = 0;
	int preperiod = 0;
	int preperiod_max = 1000; 
	if ( preperiod_max > INT_MAX  - *period ){printf("give_preperiod_and_period error: preperiod_max > INT_MAX  - period, signed integer overflow will happen = ; use extended precision \n"); return -1;}
	
	
	int i;
	int iMax = preperiod_max; // preperiod_max 
	
	// go thru preperiodic part to periodic part
	for ( i=0 ; i< iMax; i++){
		//printf("%3d:\t %3d / %3d \n", i, n, d);
     
     
		// check signed integer overflow before it will happen
		if ( n > nMax ) 
		{printf("give_preperiod_and_period error: signed integer overflow will happen = wrap; use extended precision \n"); return 1;}
                               
		// angle doubling map modulo 1 
		n = 2*n;
		n = n % d; }
	
	// now it should be periodic part 
	
	*period = give_period (n,d);
	
	// periodic orbit
	int *orbit; // only numerators
	orbit = (int *) malloc( *period * sizeof(* orbit)); 
	give_periodic_orbit(*period, n, d, orbit);
	
	
	preperiod = give_preperiod( *period, n0, d0,  orbit);
	
	
	
	
	free(orbit);
	
	return preperiod;
}


void give_orbit(const int n0, const int d0, const int preperiod, const int period){

	int n = n0;
	int d = d0;

	int i;
	int iMax = preperiod+period; // preperiod_max 
	
	
	
	for ( i=0 ; i< iMax; i++){
		if ( i < preperiod) 
			{ printf("%3d:\t %3d / %3d \t preperiodic part \n", i, n, d);}
			else {printf("%3d:\t %3d / %3d \t periodic part \n", i, n, d);}
			

		// angle doubling map modulo 1 
		n = 2*n;
		n = n % d; }
		
		
	
}



/*
Algorithm:[36]

Multiply the input decimal fraction by two
from above result
take integer part as the binary digit
take the fractional part as the starting point for the next step
repeat until you either get to 0 or a periodic number
read the number starting from the top - the first binary digit is the first digit after the comma

*/
void print_binary_expansion(const int n0, const int d0, const int preperiod, const int period){

	int n = n0;
	int d = d0;
	
	int i_max = preperiod+period;
	int i;
	double t = (double) n/d;
	double t_fractional;
    	double t_integer;
    	
    	int binary_digit;

    	
	printf("formated infinite binary expansion of %d/%d is 0.",  n0,d0);
	for (i = 0; i < i_max; ++i){
	
		// doubling map
		t *= 2.0; 
				
		// split 
		t_fractional = modf(t, &t_integer);
	
		//
		binary_digit = (int) t_integer;
		
		if (i== preperiod) {printf("(");}
		printf("%d", binary_digit);
		
		// take the fractional part as the starting point for the next step
		t = t_fractional;
		
		
		
	
	}
	printf(")\n");



}


int describe_fraction(const int n0, const int d0){

	// proper decimal fraction
	// t = n/d 
	//int n0 = 1; // 
	//int d0 = 66; // 
	
	// tr = n0r/d0r = t after reduction
	int n0r ; // 
	int d0r ; // 

	int n;
	int d;
	
	
	int period = 0;  
	int preperiod = 0;

	
	assert(n0 > 0);
	assert(d0 > 1);
	assert(n0 < d0);  // proper fraction



	// ------------ 	Reducing Fractions to Lowest Terms -------------------------------
	//  ----------- wikipedia Irreducible_fraction ----------------------------
	give_reduced_fraction(n0, d0, &n0r, &d0r);
	
	if (n0 == n0r && d0 ==d0r )
		{printf(" fraction = %d/%d\t is irreducible = in lowest terms \n", n0, d0 ); }
		else {printf(" fraction = %d/%d\t after reduction is %d/%d \n", n0, d0, n0r,d0r); }
	
	
	n = n0r;
	d = d0r;

	assert(n > 0);
	assert(d > 1);
	assert(n < d);

	int type = give_dynamic_type(n,d);
	
	
	// ------------------compute preperiod and period under doubling map -------------------------
	printf("fraction %d/%d under doubling map has: \n", n0r, d0r);
	if (type ==0 ){
		
		preperiod = give_preperiod_and_period( n0r, d0r, &period);
		
		if (preperiod > 0) {
			printf("\t preperiod = %d and period  = %d\n", preperiod, period);
			if (period == 0 )
				{printf("period = 0 means period NOT  FOUND !!!\n\t  maybe period > iMax in give_period \n\tor maybe preperiod_max in give_preperiod_and_period is to big \n");}}}
			
		 // --------------
		
		else { 
			period = give_period(n,d);
			if (period > 0)
				{printf(" preperiod = 0 and period = %d\n", period); }
				else {printf(" preperiod = 0 and period of fraction under doubling map > 0 but  period NOT  FOUND !!!  maybe period > iMax in give_period \n");}}
	// -------------------------------------------------
	
	
	give_orbit( n0, d0, preperiod, period);
	
	// ----------formated infinite binary expansion ---------------------
	print_binary_expansion( n0r, d0r, preperiod, period);
	return 0;

}

int main(void) {

	nMax = INT_MAX / 2; // signed integer 
	
	describe_fraction(1,22);


		

	return 0; 
}

另请参阅

• 维基百科中的比特编号
• 维基百科中的比特操作
• John Walker编写的C语言伪随机数序列测试程序ENT A
• 实数的连分数表示

参考文献

• YouTube上Jamie King的二进制数字视频