Сравнение рациональных чисел

Я создал следующий класс рациональных чисел C++ со всеми общими арифметическими функциями (+, -, *, /, == и !=).

template <class T>
struct rationalNumber
{
    static_assert(!std::numeric_limits<T>::is_signed, "ERROR: Type T must be unsigned");
    static_assert(std::is_integral<T>::value, "ERROR: Type T must be integral");

    T numerator;
    T denominator;
    bool sign;

    rationalNumber(const int n = 0) : numerator(std::abs(n)), denominator(1), sign(std::signbit(n)) {}
    rationalNumber(const T n, const T d, const bool s = false) : numerator(n), denominator(d), sign(s) {}
    rationalNumber(const rationalNumber&) = default;
    rationalNumber& operator=(const rationalNumber&) = default;

    rationalNumber operator-() const
    {
        return rationalNumber(numerator, denominator, !sign);
    }

    void reduce()
    {
        T divisor = gcd(numerator, denominator);
        if (divisor != 1)
        {
            numerator /= divisor;
            denominator /= divisor;
        }
        else if (numerator == 0)
        {
            denominator = 1;
            sign = false;
        }

        assert(denominator != 0);
    }
};

using RN = rationalNumber<unsigned long long>;

Возможно ли реализовать оставшиеся операторы отношений (<, >, <=, >=) с использованием арифметики с плавающей запятой, или это приведет к результатам, подверженным ошибкам?

Обратите внимание, что я рассматривал только числа с плавающей запятой, так как перекрестное умножение во многих случаях может привести к целочисленному переполнению.


person Jonas    schedule 16.02.2015    source источник
comment
Что ж, если мы скажем, что T равно int64_t, у нас будет до 19 цифр, а double подойдет для 15 или 16... так что ясно, что иногда у вас могут быть проблемы.   -  person Tony Delroy    schedule 16.02.2015


Ответы (1)


Да, можно реализовать тест на неравенство, используя операции с плавающей запятой. И, да, это потенциально может дать «результаты, подверженные ошибкам» из-за конечной точности с плавающей запятой.

На самом деле нет необходимости использовать плавающую точку вообще. Математически тест "a/b > c/d" (при условии, что a,b,c,d положительны) эквивалентен тесту "ad > bc". С беззнаковыми переменными вам также нужно будет учитывать (или обойти) эффекты арифметики по модулю (я оставлю это в качестве упражнения), но вполне реально реализовать тест точно без использования плавающей запятой вообще.

person Rob    schedule 16.02.2015
comment
Я думаю, что упомянутая вами арифметика по модулю (я полагаю, вы имеете в виду возможные переполнения?) Это именно то, чего ОП пытается избежать с помощью FP. Тривиальное сравнение ad с bc явно некорректно — как бы вы поступили в этом упражнении? - person Peter - Reinstate Monica; 16.02.2015
comment
Да, проблема в эффектах арифметики по модулю. Однако мне все еще любопытно, как ad › bc должен обрабатывать отрицательные числа. - person Jonas; 16.02.2015
comment
@Jonas: с отрицательными числами довольно просто обращаться - если только одна из сторон отрицательна, то она явно меньше другой: если они обе отрицательны, вы можете вернуть сравнение абсолютных / положительных значений. Например, x < y, где оба отрицательные -> |x| > |y|. - person Tony Delroy; 16.02.2015
comment
Отвратительно, но, возможно, зависает вместе: проблема заключается в переполнении a * d и b * c, тогда (double)a * d и double(b) * c близки (в пределах значения эпсилон друг от друга), поэтому затем вернитесь к продуктам uint64_t, известным как модуль-2^64: они не должны отличаются слишком сильно, поэтому, если одна сторона близка к 2 ^ 64, а другая близка к 0, считайте, что близкая к 0 больше. - person Tony Delroy; 16.02.2015
comment
Как бы я получил об упражнении? Существует множество алгоритмов для (беззнакового) целочисленного умножения, которые дают потенциальный результат за пределами диапазона умножаемых значений (например, умножение двух 64-битных целых чисел без знака может дать 128-битный результат). Однако обычно это не однострочные решения. - person Rob; 16.02.2015
comment
Альтернативой сравнению ad < bc является использование существующего оператора вычитания, а затем использование знака результата. Опять же, это зависит от наличия достаточного диапазона типов числителя и знаменателя. - person Toby Speight; 15.08.2017
comment
Нет особого смысла в библиотеке рациональных чисел, которая не связана с арифметикой, состоящей из нескольких слов. Рационалы слишком быстро становятся слишком большими, чтобы делать что-то интересное в long long int. Таким образом, у вас, как правило, уже есть умножение произвольной ширины. - person Sneftel; 01.05.2018