必要にせまられて小数から分数が欲しくなったので
調べてみたけれどなんだか良くわからなかったのでフィーリングで書いてみました。
途中わんこのおやつを作ったりしつつ延べ１０分で完成！
その後のテストに１～２時間かかりました。
考え方
とりあえずintにしてみてその誤差を桁を合わせながら削っていく。
それだけです。
数学的にはもっと賢くかけるのかもしれませんが。
桁の合わせ方は分母と誤差を掛けて逆数をとったものを分数へ掛けると
分子の値で誤差を表現できるようになります。
桁があったら誤差と分母を掛けたものを分子へ足す。
桁が溢れないよう注意しつつこれを繰り返す。
試してみた結果
とりあえず目的の精度には十分になりました。
もう少し攻めることもできそうだけれど条件がややこしいので放棄。
ループ回数は乱数を食わせてみたところ０と４～９くらいが多く最悪で２４回。
(float)0xffffff / 0x1000000 とか食わせると桁合わせが１ビット毎に発生するので。
コード
c++ですが今時の書き方はわかりません。
gcd部分は分数の簡略化なので省略。
static void float2fraction(float f, std::int32_t& num, std::int32_t& den)
{
constexpr std::int32_t min = std::numeric_limits<std::int32_t>::min();
constexpr std::int32_t max = std::numeric_limits<std::int32_t>::max();
if (f == 0)
{
num = 0;
den = 1;
return;
}
if (f <= (float)min)
{
num = min;
den = 1;
return;
}
if (f >= (float)max)
{
num = max;
den = 1;
return;
}
auto nv = (std::int32_t)f;
auto dv = 1;
for (;;)
{
auto vv = (float)nv / dv;
auto dt = f - vv;
auto at = std::abs(dt);
if (dt == 0)
{
break;
}
auto x = std::ceil(1.0f / (dv * at));
if ((x <= 1) || (x >= (float)max))
{
break;
}
auto s = (std::int64_t)x;
auto ns = nv * s;
auto ds = dv * s;
if ((ns <= min) || (ns >= max) || (ds > max))
{
break;
}
nv = (std::int32_t)ns;
dv = (std::int32_t)ds;
auto dd = dv * dt;
auto id = (std::int32_t)dd;
if (id == 0)
{
break;
}
nv += id;
}
auto gx = gcd(nv, dv);
if (gx > 1)
{
nv /= gx;
dv /= gx;
}
num = nv;
den = dv;
}
ちょっとびっくり
intの最大値を超えるfloatをintへキャストしたら何故か＋がーになった。
理屈は想像できるけれど気が付かないと見つけにくいバグになりますね。
コンパイルオプションでも変わりそう。
あとwindows環境でうっかりNOMINMAXとか付け忘れるとコンパイル通らないので注意。