DouKaku?beta

Comment detail

分数を小数に展開 (Nested Flatten)

This comment is reply for 567 こう。: かなり奥深いですね。 数学的に解いてみ...(分数を小数に展開). Go to thread root.

一応、循環小数についての考察結果を載せておきます。 これを元に考えたらこうなりました^^;; 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
分数n/mの非循環時30桁、循環時m-1桁、非循環部29桁の証明。
まずA mod Bが必ず0になる条件はAがBの倍数の場合。
次に((A mod B)*10)mod Bを考える。これはA/Bで小数点以下一位を求めた時の余りであり、
これが必ず0になるのは前条件の通りBが2または5の場合。

これより必ず割り切れる非循環小数になるn/mはn'/(2^x*5^y)と書ける。
(n'はnを、nとmの公約数で割ったものになる。)

これを変形すると
n/m=n*5^(x-y)/10^x=n*2^(y-x)/10^y

これより非循環小数で小数点以下の最長桁数はMAX(x,y)になることがわかる。
今、m<2^31であるのでxまたはyが最大になるmは2^30であり、最長桁数は30桁になる。

純循環小数になるn/mはmの素因数に2,5を含まない。
x mod mを考えると取り得る値は０～m-1。しかし、0の場合は割り切れて循環しないという
ことになるので1～m-1のm-1個。よって最大でもm-1しか循環しません。

では非循環部を持たない循環小数はというとここまでで出てこなかったもの
n/m=n/(m'*2^x*5^y)　※m'は2,5を素因数に含まない。
となる。

これは変形して n/m=n1/m'+n2/(2^x*5^y)と書け、純循環小数+非循環小数の形になる。
つまり、非循環部は非循環小数の長さとなり、循環部の長さはm'-1より短くなる。
今、m<2^31であるのでxまたはyが最大になるmを考えると、m'は最小の3、その場合のxは29と
なり、非循環部の最長桁数は29桁になる。
多分、この辺がベストかな？表示以外にはほとんど時間はかからないはず。関数名は考えるのまんどくなったｗ 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include <stdio.h>
#include <stdlib.h>

//小数の表示
void put_decimal(int a,int b,int loop_start_pos){
	int i;
	long long mod;
	long long loop_start_mod;

	printf("%d/%d=%d.",a,b,a/b);
	mod=(long long)(a%b)*10;
	
	//循環節までを表示
	for(i=0;i<loop_start_pos;i++){
		putchar('0'+(int)(mod/b));
		mod=(mod%b)*10;
		if(mod==0){
			putchar('\n');
			return;
		}
	}
	loop_start_mod=mod;
	//循環節を表示
	putchar('{');
	do{
		putchar('0'+(int)(mod/b));
		mod=(mod%b)*10;
		i++;
	}while(mod!=loop_start_mod);
	puts("}");
}

void put_decimals4(int a,int b){
	long long i,j;
	long long mod_buf[31];	//循環開始位置チェック用のバッファ
	long long mod;	//余り
	int num_2,num_5;		//素因数分解の結果：2の乗数、5の乗数
	long long nonloop_max;	//非循環部の最大桁数
	long long loop_max;		//循環部の最大桁数
	int denom;			//計算用分母
	
	if(a%b==0){
		printf("%d/%d=%d\n",a,b,a/b);
		return;
	}
	
	denom=b;
	
	//bの２，５についての素因数分解
	num_2=0;
	num_5=0;
	
	while(denom%2==0){
		denom/=2;
		num_2++;
	}
	
	while(denom%5==0){
		denom/=5;
		num_5++;
	}
	
	nonloop_max=max(num_2,num_5);
	loop_max=denom;
	
	//素因数に2,5を含まなければ純循環関数
	if(nonloop_max==0){
		//純循環小数なので表示
		put_decimal(a,b,0);
		return;
	}
	
	//もし分子がdenomの倍数なら約分できる。
	//分母が2^x*5^yであるなら非循環小数
	if(loop_max==1&&a%denom==0){
		//非循環関数なので表示
		put_decimal(a,b,nonloop_max);
		return;
	}
	
	//循環節ありの循環小数
	mod=a%b*10;
	mod_buf[0]=mod;
	
	//循環節の開始位置を探す。
	for(i=1;i<loop_max+nonloop_max;i++){
		mod=(mod%b)*10;
		//非循環候補の取り込み
		if(i<=nonloop_max){
			mod_buf[i]=mod;
		}
		//バッファ内との循環チェック
		for(j=0;j<=min(i,nonloop_max);j++){
			if(mod==mod_buf[j]){
				//循環開始位置がわかったら表示
				put_decimal(a,b,j);
				return;
			}
		}
	}
	
	//必ず非循環か循環のはずなのでここに来ることはない。
	return;
}

int main(){
	put_decimals4(         3,        30);
	put_decimals4(         3,         8);
	put_decimals4(         3,        14);
	put_decimals4(         1,         3);
	put_decimals4(         9,         3);
	put_decimals4(         1,        11);
	put_decimals4(        31,       701);
	put_decimals4(       101,      1999);
	put_decimals4(         1,2097152000);	//最小の非循環小数？
	put_decimals4(1073741823,1073741824);	//最長の非循環小数？
	put_decimals4(  21474836,2147483629);	//最長の循環小数？

	return 0;
}
やっぱちょっと修正。 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
//小数の表示
void put_decimal(int a,int b,int non_loop_size){
	int i;
	long long mod;
	long long loop_start_mod;

	printf("%d/%d=%d.",a,b,a/b);
	mod=(long long)(a%b)*10;
	
	//循環節までを表示
	for(i=0;i<non_loop_size;i++){
		putchar('0'+(int)(mod/b));
		mod=(mod%b)*10;
		if(mod==0){
			putchar('\n');
			return;
		}
	}
	loop_start_mod=mod;
	//循環節を表示
	putchar('{');
	do{
		putchar('0'+(int)(mod/b));
		mod=(mod%b)*10;
		i++;
	}while(mod!=loop_start_mod);
	puts("}");
}

void put_decimals4(int a,int b){
	long long i,j;
	long long mod_buf[31];
	long long mod;
	int num_2,num_5;		//素因数分解の結果：2の乗数、5の乗数
	long long nonloop_max;	//非循環部の最大桁数
	long long loop_max;		//循環部の最大桁数
	int num,denom;			//判別計算用分子、分母
	
	if(a%b==0){
		printf("%d/%d=%d\n",a,b,a/b);
		return;
	}

	num=a;
	denom=b;
	//２，５で約分
	while(num%2==0&&denom%2==0){
		num/=2;
		denom/=2;
	}
	while(num%5==0&&denom%5==0){
		num/=5;
		denom/=5;
	}
	
	//分母の２，５についての素因数分解
	num_2=0;
	num_5=0;
	
	while(denom%2==0){
		denom/=2;
		num_2++;
	}
	
	while(denom%5==0){
		denom/=5;
		num_5++;
	}
	
	nonloop_max=max(num_2,num_5);
	loop_max=denom;
	
	//素因数に2,5を含まなければ純循環関数
	if(nonloop_max==0){
		//純循環小数なので表示
		put_decimal(a,b,0);
		return;
	}
	
	//もし分子がdenomの倍数なら約分できる。
	//分母が2^x*5^yであるなら非循環小数
	if(loop_max==1&&a%denom==0){
		//非循環関数なので表示
		put_decimal(a,b,nonloop_max);
		return;
	}
	
	//循環節ありの循環小数
	mod=a%b*10;
	mod_buf[0]=mod;
	
	//循環節の開始位置を探す。
	for(i=1;i<loop_max+nonloop_max;i++){
		mod=(mod%b)*10;
		//非循環候補の取り込み
		if(i<=nonloop_max){
			mod_buf[i]=mod;
		}
		//バッファ内との循環チェック
		for(j=0;j<=min(i,nonloop_max);j++){
			if(mod==mod_buf[j]){
				//循環開始位置がわかったら表示
				put_decimal(a,b,j);
				return;
			}
		}
	}
	
	//必ず非循環か循環のはずなのでここに来ることはない。
	return;
}
さらにミス発見orz 
1
2
3
4
×
for(j=0;j<=min(i,nonloop_max);j++){
○
for(j=0;j<=min(i-1,nonloop_max);j++){
結局のところ、これでよさげ。 もう少し計算したらloop_maxじゃなく、実際の循環部の長さも求められそうなんだけど、どうなんだろ？ 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
void put_decimals5(int a,int b){
	long long i;
	long long mod;
	int num_2,num_5;		//素因数分解の結果：2の乗数、5の乗数
	long long nonloop_max;	//非循環部の最大桁数
//	long long loop_max;		//循環部の最大桁数
	long long loop_start_mod;	//循環節開始時の余り
	int num,denom;			//計算用分母
	
	printf("%d/%d=%d",a,b,a/b);
	if(a%b==0){
		putchar('\n');
		return;
	}
	a%=b;
	
	num=a;
	denom=b;
	//２，５で約分
	while(num%2==0&&denom%2==0){
		num/=2;
		denom/=2;
	}
	while(num%5==0&&denom%5==0){
		num/=5;
		denom/=5;
	}
	
	//分母の２，５についての素因数分解
	num_2=0;
	num_5=0;
	
	while(denom%2==0){
		denom/=2;
		num_2++;
	}
	
	while(denom%5==0){
		denom/=5;
		num_5++;
	}
	
	nonloop_max=max(num_2,num_5);
//	loop_max=denom;

	putchar('.');
	mod=(long long)(a%b)*10;
	
	//非循環部を表示
	for(i=0;i<nonloop_max;i++){
		putchar('0'+(int)(mod/b));
		mod=(mod%b)*10;
	}
	if(mod){
		//循環節を表示
		loop_start_mod=mod;
		putchar('{');
		do{
			putchar('0'+(int)(mod/b));
			mod=(mod%b)*10;
		}while(mod!=loop_start_mod);
		putchar('}');
	}
	putchar('\n');
	return;
}

#312です。
Cだと商と剰余をいっぺんに取る関数ありませんでしたっけ？
ループ中に割り算が半分になるので速くなると思います。

あと速度にはあまり影響なさそうですけど約分は既約分数を求めるとかでしょうか。
ものすごく興ざめな話ですが、循環小数の指数については『数論入門 / 北村泰一著』あたりをどうぞ。
それはそれでありですけど、「どう書く？」っていうのがここの趣旨だと思います。 読んで（知った上で）または、読まずに（知らないなりに）、どう書くかが問われるのでは？
だからものすごく興ざめな話なわけです。(^^;A

Index

Feed

Other

Link

Pathtraq

loading...
Creative Commons License このサイトの内容は、 クリエイティブ・コモンズ・ライセンスの下でライセンスされています。 [詳細]