Самый точный способ рассчитать числитель и знаменатель двойного
Я реализовал class NaturalNum для представления натурального числа «бесконечного» размера (до 4 ГБ).
Я также реализовал class RationalNum для представления рационального числа с бесконечной точностью. Он хранит числитель и знаменатель рационального числа, оба из которых NaturalNum экземпляры и опирается на них при выполнении любых арифметических операций, выданных пользователем.
Единственное место, где точность «опускается на определенную степень», это после печати, поскольку существует ограничение (предоставленное пользователем) на количество цифр, которые появляются после десятичной (или недесятичной) точки.
Мой вопрос касается одного из конструкторов class RationalNum, А именно, конструктор, который принимает double значение и вычисляет соответствующий числитель и знаменатель.
Мой код приведен ниже, и я хотел бы знать, видит ли кто-нибудь более точный способ их вычисления:
RationalNum::RationalNum(double value)
{
if (value == value+1)
throw "Infinite Value";
if (value != value)
throw "Undefined Value";
m_sign = false;
m_numerator = 0;
m_denominator = 1;
if (value < 0)
{
m_sign = true;
value = -value;
}
// Here is the actual computation
while (value > 0)
{
unsigned int floor = (unsigned int)value;
value -= floor;
m_numerator += floor;
value *= 2;
m_numerator *= 2;
m_denominator *= 2;
}
NaturalNum gcd = GCD(m_numerator,m_denominator);
m_numerator /= gcd;
m_denominator /= gcd;
}
Примечание: переменные, начинающиеся с ‘m_’, являются переменными-членами.
Спасибо
Решение
Стандартная библиотека содержит функцию для получения значения и показателя степени, frexp.
Просто умножьте значение и выведите все биты до десятичной точки и установите соответствующий знаменатель. Только не забывайте, что значение и нормализовано, чтобы быть между 0,5 и 1 (я бы посчитал от 1 до 2 более естественным, но безотносительно), и что у него есть 53 значащих бита для двойного IEEE (нет практически используемых платформ, которые использовали бы различные плавающие формат точки).
Другие решения
Я не уверен на 100% в математике, которая у вас есть для реальных вычислений, только потому, что я на самом деле не проверял ее, но я думаю, что приведенный ниже метод устраняет необходимость использования функции GCD, которая может привести к некоторому ненужному времени выполнения.
Вот класс, который я придумал. У меня нет от корки до корки проверил его, но я произвел пару миллиардов случайных двойных значений, и подтверждения никогда не выполнялись, поэтому я достаточно уверен в его удобстве и простоте использования, но я бы все-таки еще немного протестировал крайние случаи вокруг INT64_MAX.
Если я не ошибаюсь, сложность времени выполнения этого алгоритма линейна относительно размера в битах ввода.
#include <iostream>
#include <cmath>
#include <cassert>
#include <limits>
class Real;
namespace std {
inline bool isnan(const Real& r);
inline bool isinf(const Real& r);
}
class Real {
public:
Real(double val)
: _val(val)
{
if (std::isnan(val)) { return; }
if (std::isinf(val)) { return; }
double d;
if (modf(val, &d) == 0) {
// already a whole number
_num = val;
_den = 1.0;
return;
}
int exponent;
double significand = frexp(val, &exponent); // val = significand * 2^exponent
double numerator = val;
double denominator = 1;
// 0.5 <= significand < 1.0
// significand is a fraction, multiply it by two until it's a whole number
// subtract exponent appropriately to maintain val = significand * 2^exponent
do {
significand *= 2;
--exponent;
assert(std::ldexp(significand, exponent) == val);
} while (modf(significand, &d) != 0);
assert(exponent <= 0);
// significand is now a whole number
_num = significand;
_den = 1.0 / std::ldexp(1.0, exponent);
assert(_val == _num / _den);
}
friend std::ostream& operator<<(std::ostream &os, const Real& rhs);
friend bool std::isnan(const Real& r);
friend bool std::isinf(const Real& r);
private:
double _val = 0;
double _num = 0;
double _den = 0;
};
std::ostream& operator<<(std::ostream &os, const Real& rhs) {
if (std::isnan(rhs) || std::isinf(rhs)) {
return os << rhs._val;
}
if (rhs._den == 1.0) {
return os << rhs._num;
}
return os << rhs._num << " / " << rhs._den;
}
namespace std {
inline bool isnan(const Real& r) { return std::isnan(r._val); }
inline bool isinf(const Real& r) { return std::isinf(r._val); }
}
#include <iomanip>
int main () {
#define PRINT_REAL(num) \
std::cout << std::setprecision(100) << #num << " = " << num << " = " << Real(num) << std::endl
PRINT_REAL(1.5);
PRINT_REAL(123.875);
PRINT_REAL(0.125);
// double precision issues
PRINT_REAL(-10000000000000023.219238745);
PRINT_REAL(-100000000000000000000000000000000000000000.5);
return 0;
}
Если вы посмотрите на ваш код немного подробнее, то, по крайней мере, возникнет проблема с тестированием бесконечных значений. Обратите внимание на следующую программу:
#include <numeric>
#include <cassert>
#include <cmath>
int main() {
{
double d = std::numeric_limits<double>::max(); // about 1.7976931348623e+308
assert(!std::isnan(d));
assert(!std::isinf(d));
// assert(d != d + 1); // fires
}
{
double d = std::ldexp(1.0, 500); // 2 ^ 700
assert(!std::isnan(d));
assert(!std::isinf(d));
// assert(d != d + 1); // fires
}
}
В дополнение к этому, если ваша функция GCD не поддерживает double, то вы будете ограничивать себя в значениях, которые вы можете импортировать как double. Попробуйте любое число> INT64_MAX, и функция GCD может не работать.