fraction.hpp

SECTIONMath INCLUDEnoya/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

ReferenceSourceExpanded

当前头文件，省略 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 <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() {
    assert(den != 0);
    if (den < 0) {
      num = -num;
      den = -den;
    }
    std::int64_t div = std::gcd(num, den);
    num /= div;
    den /= div;
  }

  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 {std::int64_t(num), std::int64_t(den)};
  }
  friend fraction operator-(const fraction &a, const fraction &b) {
    return a + fraction(-b.num, b.den);
  }
  friend fraction operator*(fraction a, fraction b) {
    std::int64_t g1 = std::gcd(a.num < 0 ? -a.num : a.num, b.den);
    std::int64_t g2 = std::gcd(b.num < 0 ? -b.num : b.num, a.den);
    a.num /= g1;
    b.den /= g1;
    b.num /= g2;
    a.den /= g2;
    return {std::int64_t(__int128(a.num) * b.num),
            std::int64_t(__int128(a.den) * b.den)};
  }
  friend fraction operator/(const fraction &a, const fraction &b) {
    assert(b.num != 0);
    return a * fraction(b.den, b.num);
  }
  friend fraction operator-(const fraction &val) { return {-val.num, val.den}; }
};

} // namespace noya

#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 <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() {
    assert(den != 0);
    if (den < 0) {
      num = -num;
      den = -den;
    }
    std::int64_t div = std::gcd(num, den);
    num /= div;
    den /= div;
  }

  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 {std::int64_t(num), std::int64_t(den)};
  }
  friend fraction operator-(const fraction &a, const fraction &b) {
    return a + fraction(-b.num, b.den);
  }
  friend fraction operator*(fraction a, fraction b) {
    std::int64_t g1 = std::gcd(a.num < 0 ? -a.num : a.num, b.den);
    std::int64_t g2 = std::gcd(b.num < 0 ? -b.num : b.num, a.den);
    a.num /= g1;
    b.den /= g1;
    b.num /= g2;
    a.den /= g2;
    return {std::int64_t(__int128(a.num) * b.num),
            std::int64_t(__int128(a.den) * b.den)};
  }
  friend fraction operator/(const fraction &a, const fraction &b) {
    assert(b.num != 0);
    return a * fraction(b.den, b.num);
  }
  friend fraction operator-(const fraction &val) { return {-val.num, val.den}; }
};

} // namespace noya

#endif // NOYA_FRACTION_HPP

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

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

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() {
    assert(den != 0);
    if (den < 0) {
      num = -num;
      den = -den;
    }
    std::int64_t div = std::gcd(num, den);
    num /= div;
    den /= div;
  }

  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 {std::int64_t(num), std::int64_t(den)};
  }
  friend fraction operator-(const fraction &a, const fraction &b) {
    return a + fraction(-b.num, b.den);
  }
  friend fraction operator*(fraction a, fraction b) {
    std::int64_t g1 = std::gcd(a.num < 0 ? -a.num : a.num, b.den);
    std::int64_t g2 = std::gcd(b.num < 0 ? -b.num : b.num, a.den);
    a.num /= g1;
    b.den /= g1;
    b.num /= g2;
    a.den /= g2;
    return {std::int64_t(__int128(a.num) * b.num),
            std::int64_t(__int128(a.den) * b.den)};
  }
  friend fraction operator/(const fraction &a, const fraction &b) {
    assert(b.num != 0);
    return a * fraction(b.den, b.num);
  }
  friend fraction operator-(const fraction &val) { return {-val.num, val.den}; }
};

} // namespace noya