Самый точный способ вычисления числителя и знаменателя двойного

Question

Я внедрил 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_» являются переменными членами.

Благодаря

Answer 1

Стандартная библиотека содержит функцию для получения мантиссу и экспоненту, frexp.

Просто умножьте значение, чтобы получить все биты перед десятичной точкой и установить соответствующий знаменатель. Просто не забывайте, что значение нормализуется в пределах от 0,5 до 1 (я бы рассмотрел от 1 до 2 более естественных, но что бы то ни было) и что у него есть 53 значащих бита для IEEE double (практически нет используемых платформ, которые использовали бы различные плавающие точечный формат).

Answer 2

Я не уверен на 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 не поддерживает двойников, то вы будете ограничивать себя в терминах значений, которые можно импортировать в качестве двойников. Попробуйте любое число> INT64_MAX, и функция GCD может не работать.