分形/數學/二進位制

離散動力系統理論中的二進位制分數（數字轉換和小數的二進位制展開）

記號

一般數學記號

二進位制分數是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://wikibook.tw/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的二進位制數字影片