Skip to content

fraction.hpp

SECTIONMath INCLUDEnoya/math/fraction.hpp

提供规范化的 64 位有理数四则与比较；适合必须精确保存分数、不能用浮点的题目。

\[ \displaystyle x = p/q \]

Complexity: Time: O(log max(|num|,den)) normalization; arithmetic itself is O(1). Space: O(1).

跳到代码 · GitHub ↗

Implementation

当前头文件，省略 include guard；依赖见 #include。

/// @complexity Time: O(log max(|num|,den)) normalization; arithmetic itself is O(1).
/// Space: O(1).

#include <cassert>
#include <compare>
#include <cstdint>
#include <limits>
#include <numeric>

namespace noya {

/// @brief Normalized signed 64-bit rational number; arithmetic results must fit
/// int64, while comparison and intermediate products use signed 128-bit.
struct fraction {
  std::int64_t num = 0;
  std::int64_t den = 1;

  fraction() = default;
  fraction(std::int64_t nx, std::int64_t dx = 1) : num(nx), den(dx) {
    normalize();
  }

  void normalize() {
    *this = from_wide(num, den);
  }

  friend bool operator==(const fraction &, const fraction &) = default;
  friend std::strong_ordering operator<=>(const fraction &a,
                                          const fraction &b) {
    __int128 l = __int128(a.num) * b.den;
    __int128 r = __int128(b.num) * a.den;
    return l < r   ? std::strong_ordering::less
           : l > r ? std::strong_ordering::greater
                   : std::strong_ordering::equal;
  }
  friend fraction operator+(const fraction &a, const fraction &b) {
    std::int64_t div = std::gcd(a.den, b.den);
    __int128 num =
        __int128(a.num) * (b.den / div) + __int128(b.num) * (a.den / div);
    __int128 den = __int128(a.den / div) * b.den;
    return from_wide(num, den);
  }
  friend fraction operator-(const fraction &a, const fraction &b) {
    return from_wide(__int128(a.num) * b.den - __int128(b.num) * a.den,
                     __int128(a.den) * b.den);
  }
  friend fraction operator*(fraction a, fraction b) {
    return from_wide(__int128(a.num) * b.num, __int128(a.den) * b.den);
  }
  friend fraction operator/(const fraction &a, const fraction &b) {
    assert(b.num != 0);
    return from_wide(__int128(a.num) * b.den, __int128(a.den) * b.num);
  }
  friend fraction operator-(const fraction &val) {
    return from_wide(-__int128(val.num), val.den);
  }

private:
  // Reduce before narrowing: an intermediate numerator or denominator may
  // exceed int64 even when the normalized result is representable.
  static fraction from_wide(__int128 n, __int128 d) {
    assert(d != 0);
    if (d < 0) {
      n = -n;
      d = -d;
    }
    __int128 a = n < 0 ? -n : n, b = d;
    while (b != 0) {
      __int128 rem = a % b;
      a = b;
      b = rem;
    }
    n /= a;
    d /= a;
    assert(n >= std::numeric_limits<std::int64_t>::lowest() &&
           n <= std::numeric_limits<std::int64_t>::max() &&
           d <= std::numeric_limits<std::int64_t>::max());
    fraction res;
    res.num = std::int64_t(n);
    res.den = std::int64_t(d);
    return res;
  }
};

} // namespace noya

 // NOYA_FRACTION_HPP

#ifndef NOYA_FRACTION_HPP
#define NOYA_FRACTION_HPP 1

/// @complexity Time: O(log max(|num|,den)) normalization; arithmetic itself is O(1).
/// Space: O(1).

#include <cassert>
#include <compare>
#include <cstdint>
#include <limits>
#include <numeric>

namespace noya {

/// @brief Normalized signed 64-bit rational number; arithmetic results must fit
/// int64, while comparison and intermediate products use signed 128-bit.
struct fraction {
  std::int64_t num = 0;
  std::int64_t den = 1;

  fraction() = default;
  fraction(std::int64_t nx, std::int64_t dx = 1) : num(nx), den(dx) {
    normalize();
  }

  void normalize() {
    *this = from_wide(num, den);
  }

  friend bool operator==(const fraction &, const fraction &) = default;
  friend std::strong_ordering operator<=>(const fraction &a,
                                          const fraction &b) {
    __int128 l = __int128(a.num) * b.den;
    __int128 r = __int128(b.num) * a.den;
    return l < r   ? std::strong_ordering::less
           : l > r ? std::strong_ordering::greater
                   : std::strong_ordering::equal;
  }
  friend fraction operator+(const fraction &a, const fraction &b) {
    std::int64_t div = std::gcd(a.den, b.den);
    __int128 num =
        __int128(a.num) * (b.den / div) + __int128(b.num) * (a.den / div);
    __int128 den = __int128(a.den / div) * b.den;
    return from_wide(num, den);
  }
  friend fraction operator-(const fraction &a, const fraction &b) {
    return from_wide(__int128(a.num) * b.den - __int128(b.num) * a.den,
                     __int128(a.den) * b.den);
  }
  friend fraction operator*(fraction a, fraction b) {
    return from_wide(__int128(a.num) * b.num, __int128(a.den) * b.den);
  }
  friend fraction operator/(const fraction &a, const fraction &b) {
    assert(b.num != 0);
    return from_wide(__int128(a.num) * b.den, __int128(a.den) * b.num);
  }
  friend fraction operator-(const fraction &val) {
    return from_wide(-__int128(val.num), val.den);
  }

private:
  // Reduce before narrowing: an intermediate numerator or denominator may
  // exceed int64 even when the normalized result is representable.
  static fraction from_wide(__int128 n, __int128 d) {
    assert(d != 0);
    if (d < 0) {
      n = -n;
      d = -d;
    }
    __int128 a = n < 0 ? -n : n, b = d;
    while (b != 0) {
      __int128 rem = a % b;
      a = b;
      b = rem;
    }
    n /= a;
    d /= a;
    assert(n >= std::numeric_limits<std::int64_t>::lowest() &&
           n <= std::numeric_limits<std::int64_t>::max() &&
           d <= std::numeric_limits<std::int64_t>::max());
    fraction res;
    res.num = std::int64_t(n);
    res.den = std::int64_t(d);
    return res;
  }
};

} // namespace noya

#endif // NOYA_FRACTION_HPP

/// @complexity Time: O(log max(|num|,den)) normalization; arithmetic itself is O(1).
/// Space: O(1).

#include <cassert>
#include <compare>
#include <cstdint>
#include <limits>
#include <numeric>

namespace noya {

/// @brief Normalized signed 64-bit rational number; arithmetic results must fit
/// int64, while comparison and intermediate products use signed 128-bit.
struct fraction {
  std::int64_t num = 0;
  std::int64_t den = 1;

  fraction() = default;
  fraction(std::int64_t nx, std::int64_t dx = 1) : num(nx), den(dx) {
    normalize();
  }

  void normalize() {
    *this = from_wide(num, den);
  }

  friend bool operator==(const fraction &, const fraction &) = default;
  friend std::strong_ordering operator<=>(const fraction &a,
                                          const fraction &b) {
    __int128 l = __int128(a.num) * b.den;
    __int128 r = __int128(b.num) * a.den;
    return l < r   ? std::strong_ordering::less
           : l > r ? std::strong_ordering::greater
                   : std::strong_ordering::equal;
  }
  friend fraction operator+(const fraction &a, const fraction &b) {
    std::int64_t div = std::gcd(a.den, b.den);
    __int128 num =
        __int128(a.num) * (b.den / div) + __int128(b.num) * (a.den / div);
    __int128 den = __int128(a.den / div) * b.den;
    return from_wide(num, den);
  }
  friend fraction operator-(const fraction &a, const fraction &b) {
    return from_wide(__int128(a.num) * b.den - __int128(b.num) * a.den,
                     __int128(a.den) * b.den);
  }
  friend fraction operator*(fraction a, fraction b) {
    return from_wide(__int128(a.num) * b.num, __int128(a.den) * b.den);
  }
  friend fraction operator/(const fraction &a, const fraction &b) {
    assert(b.num != 0);
    return from_wide(__int128(a.num) * b.den, __int128(a.den) * b.num);
  }
  friend fraction operator-(const fraction &val) {
    return from_wide(-__int128(val.num), val.den);
  }

private:
  // Reduce before narrowing: an intermediate numerator or denominator may
  // exceed int64 even when the normalized result is representable.
  static fraction from_wide(__int128 n, __int128 d) {
    assert(d != 0);
    if (d < 0) {
      n = -n;
      d = -d;
    }
    __int128 a = n < 0 ? -n : n, b = d;
    while (b != 0) {
      __int128 rem = a % b;
      a = b;
      b = rem;
    }
    n /= a;
    d /= a;
    assert(n >= std::numeric_limits<std::int64_t>::lowest() &&
           n <= std::numeric_limits<std::int64_t>::max() &&
           d <= std::numeric_limits<std::int64_t>::max());
    fraction res;
    res.num = std::int64_t(n);
    res.den = std::int64_t(d);
    return res;
  }
};

} // namespace noya

 // NOYA_FRACTION_HPP