Как перевести float и double в обычную дробь?
Как перевести например 3.5 в 7/2. Чтобы и числитель и знаменатель были int-ами.
Ответы (3 шт):
Сперва я решу задачу просто, затем сложнее и правильнее.
Простое решение
x = 0.3 в формате float будет сохранено как x = 1.001100110011001100110102×2-2. Левый множитель - мантисса. Она записана как двоичная дробь. Правый множитель - экспонента в виде степени двойки. Запишем x как дробь: x = x/1. Теперь числитель и знаменатель этой дроби домножим на такой целый коэффициент, что числитель станет целым:
x/1 = 1.001100110011001100110102×2-2/1 = 0.01001100110011001100110102/1 =
= (225×0.01001100110011001100110102)/(225×1) = 1001100110011001100110102/225
Последнее выражение - обыкновенная дробь 10066330/33554432, что упрощается до 5033165/16777216.
Хотелось получить 3/10, но это число нельзя сохранить в формате float точно. При записи оно чуть-чуть меняется и получается 5033165/16777216.
NB Программа использует вещественный тип для представления числителя и знаменателя дроби. Тем не менее все промежуточные значения целые и арифметика точная.
#include <cmath>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <utility>
template<typename T>
std::pair<T, T> ratio(T x) {
int e = std::max(
std::numeric_limits<T>::digits - static_cast<int>(std::logb(x)) - 1,
0
);
auto n = std::ldexp(x, e);
for (; e > 0 && std::fmod(n, T(2)) == 0; --e, n /= 2) {
}
auto d = std::ldexp(T(1), e);
return {n, d};
}
int main() {
double x;
std::cin >> x;
auto r = ratio(x);
std::cout << std::fixed << std::setprecision(0);
std::cout << r.first << '/' << r.second << '\n';
}
Цепные дроби
Предыдущее решение точное. В том смысле, что оно печатает дробь, которая точно равна вещественному числу в памяти компьютера. Но, как ни странно, есть решение лучше точного.
Есть много пар целых чисел, которые будучи поделены, дадут нужное нам число x в вещественном формате. Например, x = 0.3 может быть получено и как 5033165/16777216 и как 2516581/8388603 и как 3/10. В реальной арифметике это разные числа. В машинной арифметике они равны.
Переформулируем задачу: требуется отыскать такую пару натуральных чисел, которые при делении в машинной арифметике дадут x. Инструмент для поиска - цепные дроби.
Чтобы построить цепную дробь для машинного представления x, выразим x в виде точной дроби. Например 0.3 хранится как 5033165/16777216.
Делим числитель на знаменатель с остатком и переворачиваем дробь в правой части:
5033165/16777216 = 0 + 5033165/16777216 = 0 + (16777216/5033165)-1.
Повторим для новой дроби:
16777216/5033165 = 3 + 1677721/5033165 = 3 + (5033165/1677721)-1
И ещё два раза:
5033165/1677721 = 3 + 2/1677721 = 3 + (1677721/2)-1
1677721/2 = 838860 + 1/2 = 838860 + (2/1)-1
Останавливаемся, в последнем выражении в знаменателе единица. В нотации цепных дробей
5033165/16777216 = [0; 3, 3, 838860, 2] = 0 + (3 + (3 + (838860 + 2-1)-1)-1)-1.
Будем считать дроби для частичных цепных дробей:
[0;] = 0 = 0
[0; 3] = 0 + 3-1 = 1/3
[0; 3, 3] = 0 + (3 + 3-1)-1 = 3/10
[0; 3, 3, 838860] = 0 + (3 + (3 + 838860-1)-1)-1 = 2516581/8388603
[0; 3, 3, 838860, 2] = 0 + (3 + (3 + (838860 + 2-1)-1)-1)-1 = 5033165/16777216
Каждый раз когда получена дробь в виде пары целых чисел, эти числа переводятся в вещественный формат и выполняется машинное деление. Если результат деления совпадает с исходным x в машинном представлении, задача решена.
#include <cmath>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <utility>
#include <vector>
template<typename T>
std::pair<T, T> bin_ratio(T x) {
int e = std::max(
std::numeric_limits<T>::digits - static_cast<int>(std::logb(x)) - 1,
0
);
auto n = std::ldexp(x, e);
for (; e > 0 && std::fmod(n, T(2)) == 0; --e, n /= 2) {
}
auto d = std::ldexp(T(1), e);
return {n, d};
}
template<typename T>
void cf(T n, T d, std::vector<T> &a) {
while (d != 0) {
a.push_back(std::floor(n / d));
auto tmp = d;
d = std::fmod(n, d);
n = tmp;
}
}
template<typename T>
std::pair<T, T> ratio(T x) {
auto r = bin_ratio(x);
std::vector<T> a;
cf(r.first, r.second, a);
auto m = a.size();
for (unsigned i = 1; i <= m; ++i) {
T n = 1;
T d = 0;
for (int j = i - 1; j >= 0; --j) {
auto tmp = n;
n = a[j] * n + d;
d = tmp;
}
if (n / d == x) {
return {n, d};
}
}
return r;
}
int main() {
double x;
std::cin >> x;
auto r = ratio(x);
std::cout << std::fixed << std::setprecision(0);
std::cout << r.first << '/' << r.second << '\n';
}
$ g++ -std=c++17 -pedantic -Wall -Wextra -Werror -Wwrite-strings -Wconversion fraction.cpp $ echo 0.3 | ./a.out 3/10 $ echo 3.5 | ./a.out 7/2 $ echo 200.1 | ./a.out 2001/10 $ echo 0.00000000001 | ./a.out 1/100000000000
P.S. Следующий раз когда вам кто-то скажет что вещественные числа нельзя сравнивать с помощью ==, покажите им эту программу. Она работает потому что так делать можно, когда знаешь что делаешь.
Учитывая то, как в компьютере представляются вещественные числа, это делается умножением на 2 до тех пор, пока не получится целое число. Это всегда можно сделать без потери точности, а си и си++ даже не попытаются округлить значение при выводе (как это сделают другие языки).
Но есть нюанс. Компьютер не хранит десятичное число точно, поэтому может оказаться так, что то число, которое хранит компьютер, - это не то число, которое мы хотим увидеть. Надо ещё как-то "сократить" дробь, но под "сокращением" тут понимается округление до более красивого результата с несильной потерей точности. Как это сделать - надо ещё подумать.
function toFraction(x) {
var den = 1
while (x % 1) {
x *= 2
den *= 2
}
return x + "/" + den
}
for (var x of [200, 1, 0, 3.5, 124.375, .5, .75, .3, 1/3]) {
console.log(x, toFraction(x))
}.as-console-wrapper.as-console-wrapper { max-height: 100vh }Для получения более красивой дроби можно сделать как-то так (насколько я вижу, работает, но не уверен в константе .125). Вместо BigInt можно использовать int64 (просто в js его нет).
UPDATE: Не всегда работает: 200.1 не может красиво вывести.
function gcd(x, y) {
if (!x) return y ? y : 1
if (!y) return x
while (1) {
if (!(x %= y)) return y
if (!(y %= x)) return x
}
}
function toFraction(x) {
var den = 1, d = .5
while (x + d !== x) {
d /= 2
}
while (x % 1) {
x *= 2
den *= 2
}
var bestnom = x, bestden = den
if (d * den > .125) {
var x8 = BigInt(x)*8n, den8 = BigInt(den)*8n
for (var y = x8 - 7n; y < x8 + 8n; ++y) {
for (var z = den8 - 7n; z < den8 + 8n; ++z) {
var g = gcd(y, z)
if (bestden > z/g) {
bestnom = y/g
bestden = z/g
}
}
}
}
return {
exact: x + "/" + den,
optimal: bestnom + "/" + bestden,
}
}
for (var x of [200, 1, 0, 3.5, 124.375, .5, .75, .3, 1/3, 200.1]) {
var { exact, optimal } = toFraction(x)
console.log(x, "=", exact, "~", optimal)
}.as-console-wrapper.as-console-wrapper { max-height: 100vh }Как дополнение... С цепными дробями я как-то игрался полтора года назад, было интересно. Поскольку эти дроби росли мгновенно до неимоверных значений, взял boost/multiprecision. Переписывать не хочется, просто как есть - тут, если процесс не останавливается на точном значении, до 80 таких дробей.
Вот что валяется на диске:
#include <vector>
#include <string>
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cmath>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/multiprecision/cpp_bin_float.hpp>
#include <boost/math/ccmath/floor.hpp>
using namespace std;
using namespace boost::multiprecision;
using Double = boost::multiprecision::cpp_bin_float_100;
using Integer = boost::multiprecision::cpp_int;
vector<Integer> chain(Double x)
{
vector<Integer> a;
Integer v = x.convert_to<Integer>();
a.push_back(v);
x = x - Double(v);
for(int i = 0;x != 0 && i < 80;++i)
{
x = 1.0/x;
if ((v = x.convert_to<Integer>()) == 0) break;
a.push_back(v);
x = x - Double(v);
}
return a;
}
vector<pair<Integer,Integer>> suitable(const vector<Integer>& a)
{
vector<pair<Integer,Integer>> v;
Integer p_1 = 1, q_1 = 0;
Integer p0 = a[0], q0 = 1;
v.emplace_back(p0,q0);
for(int i = 1; i < a.size(); ++i)
{
Integer p = a[i]*p0 + p_1;
Integer q = a[i]*q0 + q_1;
v.emplace_back(p,q);
p_1 = p0; q_1 = q0;
p0 = p; q0 = q;
}
return v;
}
int main(int argc, char * argv[])
{
const char* e = "2.7182818284590452353602874713526624977572470936999595749669676277240766303535475945713821785251664274"
"2746639193200305992181741359662904357290033429526059563073813232862794349076323382988075319525101901";
const char * pi = "3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679"
"821480865132823066470938446095505822317253594081284811174502841027019385211055596446229489549303819644288109756659334461284756482337867831652712019091";
Double x("200.1");
auto z = chain(x);
for(auto q: z) cout << q << " ";
cout << "\n\n";
auto y = suitable(z);
for(auto w: y)
{
cout << w.first << "/" << w.second << " ";
Double p = w.first.convert_to<Double>();
Double q = w.second.convert_to<Double>();
cout << setprecision(30) << p/q << endl;
}
}
А вот что получается для 200.1:
200/1 200
2001/10 200.1
6838576094204385719795901494472438050112018798777059508262448411603618674059298784953515417536140721/34175792574734561318320347298712833833643272357706444319152665725155515612490248800367393390985211 200.1
и 0.3:
0/1 0
1/3 0.333333333333333333333333333333
2/7 0.285714285714285714285714285714
3/10 0.3
4374501449566023848745004454235242730706338861786424872851541212819905998398751846447026354046107648/14581671498553412829150014847450809102354462872621416242838470709399686661329172821490087846820358827 0.3
Или для "пи":
3/1 3
22/7 3.14285714285714285714285714286
333/106 3.14150943396226415094339622642
355/113 3.14159292035398230088495575221
103993/33102 3.14159265301190260407226149477
104348/33215 3.14159265392142104470871594159
208341/66317 3.14159265346743670552045478535
312689/99532 3.14159265361893662339750030141
833719/265381 3.14159265358107777120441930658
Вот о точности из Википедии:
Подходящая дробь pn/qn является наилучшим приближением исходного числа среди всех дробей, знаменатель которых не превосходит qn.
Так что, наверное, надо просто задаваться точностью представления, и обрывать ее где надо...