frexp と ldexp で浮動小数点数を分数へ変換するアルゴリズム
倍精度浮動小数点数のおさらいから。
フォーマット
| 符号 | 指数部 | 仮数部 |
|---|---|---|
| 1 | 11 | 52 |
\[ val = (-1)^{s} \cdot (1 + f \cdot 2^{-52}) \cdot 2^{e - 1023} \]
例: 0.75
\[ 0.75 = (-1)^{0_{(2)}} \cdot (1 + 1000000000000000000000000000000000000000000000000000_{(2)} * 2^{-52}) \cdot 2^{01111110_{(2)} - 1023} \]
| 符号 | 指数部 | 仮数部 |
|---|---|---|
| 0 | 011 1111 1110 | 1000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 |
frexp
#include <math.h> // C++ の場合 // double std::frexp(double val, int* 仮数部){ double frexp(double val, int* 指数部){ return 仮数部; }
仮数部
\[ 仮 数部 = (-1)^{s} \cdot (1 + f \cdot 2^{-52}) \cdot \frac{1}{2}\,\,\,\,(0.5 \leqq return < 1) \]
指数部
\[ 指数部 = e - 1022 \]
ldexp
$x * 2^{exp}$を計算する。
浮動小数点数から分数へ
frexp() で取得した仮数部を ldexp() のxにし、exp = 53 とすると、(53は__DBL_MANT_DIG__)
\[ ldexp = (1 + f\cdot 2^{-52})\cdot \frac{1}{2} \cdot 2^{53}\\ = 2^{52} + f\\ = 分子 \]
数 = 分子 / 分母 なので、
\[ 分母 = \frac{分子}{浮動 小数点数} \]
これで、分母と分子が求まった。
約分
分母と分子の最大公約数gcd(分子, 分母)で約分する。
\[ 最大公約 数 = gcd(分子, 分母);\\ 分子 = 分子 / 最大公約数;\\ 分母 = 分母 / 最大公約数; \]
