fork(4) download
copy 
  1. #include <stdio.h>
  2. #include <stdint.h>
  3. #include <math.h>
  4. #include <assert.h>
  5.  
  6. typedef int64_t rtnum_t;
  7. typedef int64_t rtden_t;
  8.  
  9. static bool get_rational(double x, rtnum_t& num, rtden_t& den)
  10. {
  11. 	// 出力パラメータ初期化
  12. 	num = (rtnum_t)0;
  13. 	den = (rtden_t)0;
  14.  
  15. 	// 負号保存
  16. 	const bool bNeg = (x < 0.0);
  17. 	x = fabs(x);
  18.  
  19. 	// 指数部取得
  20. 	int exp;
  21. 	(void)frexp(x, &exp);
  22. 	const int IEEE754_exp = exp - 1;
  23.  
  24. 	// 誤差の指数取得
  25. 	// これは仮数部最下位bitが2の何乗かを表す。
  26. 	// 倍精度浮動小数点数の仮数部(小数部のみ表現)のビット数は52なので、52を引く。
  27. 	int err_exp = IEEE754_exp - 52;
  28. 	if (err_exp < -1022) {
  29. 		// 倍精度浮動小数点数で表現可能な指数の下限が精度の下限。
  30. 		// (2^(-1022)未満は非正規化数)
  31. 		err_exp = -1022;
  32. 	}
  33.  
  34. 	// 誤差取得
  35. 	// これは仮数部最下位bitが表す数にあたる。取得にあたり、
  36. 	// pow()は中で多項式近似しているかもしれないので信用しないことにする。
  37. 	double err = 1.0;
  38. 	if (err_exp >= 0) {
  39. 		for (int i = 0; i < err_exp; i++) {
  40. 			err *= 2.0;		// 2のべきなので計算誤差0。
  41. 		}
  42. 	}
  43. 	else {
  44. 		for (int i = 0; i < -err_exp; i++) {
  45. 			err /= 2.0;		// 2のべきなので計算誤差0。
  46. 		}
  47. 	}
  48. 	// (とは言いつつ、実は一致するらしい。)
  49. 	assert(err == pow(2.0, err_exp));
  50.  
  51. 	// 誤差が1の位より大きいケースには対応しない。
  52. 	if (err > 1.0) {
  53. 		assert(0);
  54. 		return false;
  55. 	}
  56.  
  57. 	// 分子取得
  58. 	// max(0, x)∈[ 10^exp10, 10^(exp10 + 1) )となるexp10を求める。
  59. 	double base10 = 1.0;
  60. 	int exp10 = 0;
  61. 	while (base10 <= x) {
  62. 		base10 *= 10.0;		// 整数倍なので計算誤差0。
  63. 		exp10++;
  64. 	}
  65. 	while (base10 > x && exp10 > 0) {
  66. 		assert(base10 > 0.0 && fmod(base10, 10.0) == 0.0);
  67. 		base10 /= 10.0;		// 10の倍数を10で割るので計算誤差0。
  68. 		exp10--;
  69. 	}
  70. 	// 整数部出力
  71. 	// 上の桁から求めていく。
  72. 	while (base10 > err && exp10 > 0) {
  73. 		const double tmp = x / base10;
  74. 		const double intpart = floor(tmp);
  75. 		const rtnum_t digit = (rtnum_t)intpart % 10;
  76. 		num *= 10;
  77. 		num += digit;
  78. 		assert(base10 > 0.0 && fmod(base10, 10.0) == 0.0);
  79. 		base10 /= 10.0;		// 10の倍数を10で割るので計算誤差0。
  80. 		exp10--;
  81. 	}
  82. 	// 1の桁
  83. 	{
  84. 		const double tmp = x / base10;
  85. 		const double intpart = floor(tmp);
  86. 		const rtnum_t digit = (rtnum_t)intpart % 10;
  87. 		num *= 10;
  88. 		num += digit;
  89. 		exp10--;
  90. 	}
  91. 	// 小数部出力
  92. 	// 上の桁から求めていく。
  93. 	double x_frac = x - floor(x);
  94. 	err *= 10.0;			// 整数倍なので計算誤差0。
  95. 	while (err < 1.0) {
  96. 		x_frac *= 10.0;		// 整数倍なので計算誤差0。
  97. 		const double intpart = floor(x_frac);
  98. 		const rtnum_t digit = (rtnum_t)intpart % 10;
  99. 		num *= 10;
  100. 		num += digit;
  101. 		exp10--;
  102. 		err *= 10.0;		// 整数倍なので計算誤差0。
  103. 	}
  104.  
  105. 	// この時点でexp10は10進数表記したときの誤差の桁を指しており、
  106. 	// 誤差±10^(exp10)の10進数表記が得られたことになる。
  107.  
  108. 	// 余分な0または9を削除
  109. 	exp10++;
  110. 	if (num % 10 == 9) {
  111. 		// 余分な9を削除。
  112. 		// 2進数のIEEE 754形式xから10進数表現numに直したとき
  113. 		// 運悪く9の循環小数になったときここに来る。
  114. 		// 削除といっても+1するだけで、後続の「0」削除処理が仕事をしてくれる。
  115. 		num++;
  116. 	}
  117. 	// 余分な0を削除
  118. 	while (num % 10 == 0) {
  119. 		num /= 10;
  120. 		exp10++;
  121. 	}
  122.  
  123.  
  124. 	// exp10 > 0のケースには対応しない。
  125. 	if (exp10 > 0) {
  126. 		assert(0);
  127. 		return false;
  128. 	}
  129.  
  130. 	// 負号復元
  131. 	if (bNeg) {
  132. 		num = -num;
  133. 	}
  134.  
  135. 	// 分母確定
  136. 	den = (rtden_t)1;
  137. 	for (int i = 0; i < -exp10; i++) {
  138. 		den *= 10;
  139. 	}
  140.  
  141. 	return true;
  142. }
  143.  
  144. void RationalTest()
  145. {
  146. 	// 有理数化テスト
  147. 	{
  148. 		const char* x_str = "0.1";
  149. 		const double x = 0.1;
  150. 		rtnum_t num;
  151. 		rtden_t den;
  152. 		get_rational(x, num, den);
  153. 		printf("x=%s: rt=%lld/%lld\n", x_str, num, den);
  154. 	}
  155. 	{
  156. 		const char* x_str = "0.11";
  157. 		const double x = 0.11;
  158. 		rtnum_t num;
  159. 		rtden_t den;
  160. 		get_rational(x, num, den);
  161. 		printf("x=%s: rt=%lld/%lld\n", x_str, num, den);
  162. 	}
  163. 	{
  164. 		const char* x_str = "0.111";
  165. 		const double x = 0.111;
  166. 		rtnum_t num;
  167. 		rtden_t den;
  168. 		get_rational(x, num, den);
  169. 		printf("x=%s: rt=%lld/%lld\n", x_str, num, den);
  170. 	}
  171. 	{
  172. 		const char* x_str = "0.1111";
  173. 		const double x = 0.1111;
  174. 		rtnum_t num;
  175. 		rtden_t den;
  176. 		get_rational(x, num, den);
  177. 		printf("x=%s: rt=%lld/%lld\n", x_str, num, den);
  178. 	}
  179. 	{
  180. 		const char* x_str = "0.9";
  181. 		const double x = 0.9;
  182. 		rtnum_t num;
  183. 		rtden_t den;
  184. 		get_rational(x, num, den);
  185. 		printf("x=%s: rt=%lld/%lld\n", x_str, num, den);
  186. 	}
  187. 	{
  188. 		const char* x_str = "0.99";
  189. 		const double x = 0.99;
  190. 		rtnum_t num;
  191. 		rtden_t den;
  192. 		get_rational(x, num, den);
  193. 		printf("x=%s: rt=%lld/%lld\n", x_str, num, den);
  194. 	}
  195. 	{
  196. 		const char* x_str = "0.999";
  197. 		const double x = 0.999;
  198. 		rtnum_t num;
  199. 		rtden_t den;
  200. 		get_rational(x, num, den);
  201. 		printf("x=%s: rt=%lld/%lld\n", x_str, num, den);
  202. 	}
  203. 	{
  204. 		const char* x_str = "0.9999";
  205. 		const double x = 0.9999;
  206. 		rtnum_t num;
  207. 		rtden_t den;
  208. 		get_rational(x, num, den);
  209. 		printf("x=%s: rt=%lld/%lld\n", x_str, num, den);
  210. 	}
  211. 	{
  212. 		const char* x_str = "0.33333";
  213. 		const double x = 0.33333;
  214. 		rtnum_t num;
  215. 		rtden_t den;
  216. 		get_rational(x, num, den);
  217. 		printf("x=%s: rt=%lld/%lld\n", x_str, num, den);
  218. 	}
  219. 	{
  220. 		const char* x_str = "123.34567";
  221. 		const double x = 123.34567;
  222. 		rtnum_t num;
  223. 		rtden_t den;
  224. 		get_rational(x, num, den);
  225. 		printf("x=%s: rt=%lld/%lld\n", x_str, num, den);
  226. 	}
  227. 	{
  228. 		const char* x_str = "123.345678";
  229. 		const double x = 123.345678;
  230. 		rtnum_t num;
  231. 		rtden_t den;
  232. 		get_rational(x, num, den);
  233. 		printf("x=%s: rt=%lld/%lld\n", x_str, num, den);
  234. 	}
  235. 	{
  236. 		const char* x_str = "123.3456789";
  237. 		const double x = 123.3456789;
  238. 		rtnum_t num;
  239. 		rtden_t den;
  240. 		get_rational(x, num, den);
  241. 		printf("x=%s: rt=%lld/%lld\n", x_str, num, den);
  242. 	}
  243. 	{
  244. 		const char* x_str = "123.345699999999";
  245. 		const double x = 123.345699999999;
  246. 		rtnum_t num;
  247. 		rtden_t den;
  248. 		get_rational(x, num, den);
  249. 		printf("x=%s: rt=%lld/%lld\n", x_str, num, den);
  250. 	}
  251. 	{
  252. 		const char* x_str = "12.34567";
  253. 		const double x = 12.34567;
  254. 		rtnum_t num;
  255. 		rtden_t den;
  256. 		get_rational(x, num, den);
  257. 		printf("x=%s: rt=%lld/%lld\n", x_str, num, den);
  258. 	}
  259. 	{
  260. 		const char* x_str = "12";
  261. 		const double x = 12;
  262. 		rtnum_t num;
  263. 		rtden_t den;
  264. 		get_rational(x, num, den);
  265. 		printf("x=%s: rt=%lld/%lld\n", x_str, num, den);
  266. 	}
  267. 	{
  268. 		const char* x_str = "123E-5";
  269. 		const double x = 123E-5;
  270. 		rtnum_t num;
  271. 		rtden_t den;
  272. 		get_rational(x, num, den);
  273. 		printf("x=%s: rt=%lld/%lld\n", x_str, num, den);
  274. 	}
  275. }
  276.  
  277. int main()
  278. {
  279. 	RationalTest();
  280. }
  281.  
Success #stdin #stdout 0s 4388KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
x=0.1: rt=1/10
x=0.11: rt=11/100
x=0.111: rt=111/1000
x=0.1111: rt=1111/10000
x=0.9: rt=9/10
x=0.99: rt=99/100
x=0.999: rt=999/1000
x=0.9999: rt=9999/10000
x=0.33333: rt=33333/100000
x=123.34567: rt=12334567/100000
x=123.345678: rt=123345678/1000000
x=123.3456789: rt=1233456789/10000000
x=123.345699999999: rt=123345699999999/1000000000000
x=12.34567: rt=1234567/100000
x=12: rt=12/1
x=123E-5: rt=123/100000
https://ideone.com/EKHKWG
language:
C++ (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!