Как сравнить рациональные числа?

Question

Это домашнее задание. Для данного класса «Rational» с двумя целочисленными полями, числителем и знаменателем, напишите функцию для сравнения двух экземпляров «Rational». Пусть r1 = a/b и r2 = c/d. Тривиальным решением является сравнение a*d и b*c. Можем ли мы сделать лучше?

Answer 1

Если вы хотите сложное решение, преобразуйте каждую из двух дробей в непрерывную дробь (используя вариант алгоритма GCD). Этот простой алгоритм генерирует одно целое число за раз. Сравните каждую пару целых чисел из двух частичных цепных дробей. Если они разные, выход. В противном случае создайте следующую пару и продолжайте, пока их больше. Для рациональных чисел последовательность конечна, поэтому она скоро завершится. Я считаю, что это лучший метод, когда a, b, c, d большие.

Доказано, что непрерывные разложения дробей для всех иррациональных чисел с квадратными корнями повторяются. Таким образом, вы можете использовать это также для сравнения этих иррациональных чисел, даже если их двоичные компьютерные представления в противном случае дали бы вам неправильный результат (из-за усечения). Это означает, что как только вы обнаружите повторение в шаблоне, вы можете прекратить работу, доказав равенство двух иррациональных чисел.

Answer 2

В общем случае нет. Если вы ожидаете много сравнений, то на этапе предварительной обработки можно позаботиться о нормализации всего (путем деления числителя и знаменателя на их gcd и создания положительного знаменателя), чтобы сравнения равенства сравнивали a = c и b = d, но вычисление a * d = b * c, безусловно, не является запретительным способом.

Answer 3

Обычно стоимость ветки больше, чем стоимость умножения, поэтому не стоит пытаться быть умным, кроме этого. Если под целыми числами вы подразумеваете int32, то переходите к int64 для выполнения умножения; если вы имеете в виду большие целые числа, вам нужно управлять умножением, используя обычные механизмы, после чего предположения о ветвях могут быть признаны недействительными.

Answer 4

С моей точки зрения, тривиальное решение неверно, если допустимы отрицательные числа:

Как насчет r1=1/3 и b=1/(-3), которые должны быть правильными рациональными числами.и, конечно, математически он считает, что: 1 / (- 3) <1/3 </p>

Однако предлагаемое решение дает 1*3 > 1*(-3), что приводит к неверному решению, которое 1/3 < 1/(-3).

Я только столкнулся с этой проблемой во время моего курса Scala :-) Тем не менее, у меня нет хорошего решения по этому вопросу.

Может быть, как это часто бывает, это помогает заглянуть в BOOST-библиотеку: там написано:

Операция сравнения с рациональной операцией выполняет две операции GCD двойного размера, два дополнительных сложения и уменьшения и три сравнения в худшем случае.(Операции GCD имеют двойной размер, потому что они выполняются по частям, а временные коэффициенты сохраняются и сравниваются, тогда как прямая функция GCD сохраняет и сравнивает только остатки.)

http://www.boost.org/doc/libs/1_55_0/libs/rational/rational.html

До сих пор у меня не было возможности исследовать этот код.

Приветствия, Феликс

Тем временем я изучал код Boost, и он делает то же самое, что описывает Либерийв своем ответе выше.https://stackoverflow.com/a/4288890/2682209 Так что это определенно «правильный» (но громоздкий) путь.

Answer 5

Мне не нравится решение a*d b*c, поскольку оно может привести к ненужному переполнению целых чисел, если некоторые из числителей и знаменателей большиеХотя у меня нет лучшего решения.

Answer 6

Если вы используете Java, то вы можете использовать класс java.math.BigInteger, если и когда вы столкнетесь с переполнением;в противном случае вы можете реализовать свои собственные массивы байтов.