比較したい2つの分数があります。これらは次のように保存されます。
struct fraction {
int64_t numerator;
int64_t denominator;
};
現在、私はそれらを次のように比較します：
bool fraction_le(struct fraction a, struct fraction b)
{
return a.numerator * b.denominator < b.numerator * a.denominator;
}
(64 bit value) * (64 bit value) = (128 bit value)これは、ゼロから離れすぎている分子と分母に対してオーバーフローすることを意味することを除いて、正常に機能します。
ばかげた分数であっても、比較を常に機能させるにはどうすればよいですか？
ちなみに、分数は常に簡略化されて保存され、分子のみが負になる可能性があります。たぶん、その入力制約はいくつかのアルゴリズムを可能にします...
Boostがそれを実装する方法は次のとおりです。コードはよくコメントされています。
template <typename IntType>
bool rational<IntType>::operator< (const rational<IntType>& r) const
{
// Avoid repeated construction
int_type const zero( 0 );
// This should really be a class-wide invariant. The reason for these
// checks is that for 2's complement systems, INT_MIN has no corresponding
// positive, so negating it during normalization keeps it INT_MIN, which
// is bad for later calculations that assume a positive denominator.
BOOST_ASSERT( this->den > zero );
BOOST_ASSERT( r.den > zero );
// Determine relative order by expanding each value to its simple continued
// fraction representation using the Euclidian GCD algorithm.
struct { int_type n, d, q, r; } ts = { this->num, this->den, this->num /
this->den, this->num % this->den }, rs = { r.num, r.den, r.num / r.den,
r.num % r.den };
unsigned reverse = 0u;
// Normalize negative moduli by repeatedly adding the (positive) denominator
// and decrementing the quotient. Later cycles should have all positive
// values, so this only has to be done for the first cycle. (The rules of
// C++ require a nonnegative quotient & remainder for a nonnegative dividend
// & positive divisor.)
while ( ts.r < zero ) { ts.r += ts.d; --ts.q; }
while ( rs.r < zero ) { rs.r += rs.d; --rs.q; }
// Loop through and compare each variable's continued-fraction components
while ( true )
{
// The quotients of the current cycle are the continued-fraction
// components. Comparing two c.f. is comparing their sequences,
// stopping at the first difference.
if ( ts.q != rs.q )
{
// Since reciprocation changes the relative order of two variables,
// and c.f. use reciprocals, the less/greater-than test reverses
// after each index. (Start w/ non-reversed @ whole-number place.)
return reverse ? ts.q > rs.q : ts.q < rs.q;
}
// Prepare the next cycle
reverse ^= 1u;
if ( (ts.r == zero) || (rs.r == zero) )
{
// At least one variable's c.f. expansion has ended
break;
}
ts.n = ts.d; ts.d = ts.r;
ts.q = ts.n / ts.d; ts.r = ts.n % ts.d;
rs.n = rs.d; rs.d = rs.r;
rs.q = rs.n / rs.d; rs.r = rs.n % rs.d;
}
// Compare infinity-valued components for otherwise equal sequences
if ( ts.r == rs.r )
{
// Both remainders are zero, so the next (and subsequent) c.f.
// components for both sequences are infinity. Therefore, the sequences
// and their corresponding values are equal.
return false;
}
else
{
// Exactly one of the remainders is zero, so all following c.f.
// components of that variable are infinity, while the other variable
// has a finite next c.f. component. So that other variable has the
// lesser value (modulo the reversal flag!).
return ( ts.r != zero ) != static_cast<bool>( reverse );
}
}
GCCを使用している場合は、__int128を使用できます。
Kosの回答のコードがわからなかったので、これは単にそれを複製しているだけかもしれません。
他の人が言及しているように、いくつかの簡単な特殊なケースがb/c > -e/fあり-b/c > -e/fますe/f > b/c。したがって、正の分数の場合が残ります。
これらを混合数、すなわちa b/cとに変換しd e/fます。些細なケースがa != dあるので、を仮定しa == dます。次に、b <c、e<fと比較b/cします。e/fまあ。b/c > e/f_ f/e > c/bこれらは両方とも1より大きいため、整数の部分が異なるまで混合数テストを繰り返すことができます。
ケースは私に興味をそそられたので、ここにニールの答えの実装があります、おそらくバグがあります:)
#include <stdint.h>
#include <stdlib.h>
typedef struct {
int64_t num, den;
} frac;
int cmp(frac a, frac b) {
if (a.num < 0) {
if (b.num < 0) {
a.num = -a.num;
b.num = -b.num;
return !cmpUnsigned(a, b);
}
else return 1;
}
else if (0 <= b.num) return cmpUnsigned(a, b);
else return 0;
}
#define swap(a, b) { int64_t c = a; a = b; b = c; }
int cmpUnsigned(frac a, frac b) {
int64_t c = a.num / a.den, d = b.num / b.den;
if (c != d) return c < d;
a.num = a.num % a.den;
swap(a.num, a.den);
b.num = b.num % b.den;
swap(b.num, b.den);
return !cmpUnsigned(a, b);
}
main() {
frac a = { INT64_MAX - 1, INT64_MAX }, b = { INT64_MAX - 3, INT64_MAX };
printf("%i\n", cmp(a, b));
}
了解しました。分子だけが署名されています。
特殊なケース：
a.numeratorが負で、b.numeratorが正の場合、bはaより大きくなります。b.numeratorが負で、a.numeratorが正の場合、aはbより大きくなります。
さもないと：
両方の分子は同じ符号（+/-）を持っています。ロジックコードまたはビット操作を追加して削除し、uint64_tとの乗算を使用してそれらを比較します。両方の分子が負の場合、比較の結果を否定する必要があることに注意してください。
それらを浮動小数点数として直接比較してみませんか？
bool fraction_le(struct fraction a, struct fraction b)
{
return (double)a.numerator / a.denominator < (double)b.numerator / b.denominator;
}