有理数（Fraction）

math/fraction.hpp · GitHub で見る

共通ページ

#include "lib/math/fraction.hpp"
#include <cassert>

int main() {
	using F = Fraction<>;
	F a(2, -6), b(5, 6);
	auto sum = a + b;
	auto n = sum.numerator();
	auto d = sum.denominator();
	auto lower = a.floor();
	auto upper = a.ceil();
	auto inverse = a.inv();
	auto power = a.pow(3);
	double approximation = static_cast<double>(a);
	assert(n == 1 && d == 2);
	assert(lower == -1 && upper == 0);
	assert(inverse == F(-3));
	assert(power == F(-1, 27));
	assert(-1 < approximation && approximation < 0);
}

操作	内容・返り値	計算量
Fraction<>() / Fraction<>(n) / Fraction<>(n,d)	0／整数／分数から構築。d != 0	\(O(\log M)\)
a.numerator() / a.denominator()	約分後の分子／正の分母	\(O(1)\)
+a / -a / abs(a)	単項符号／絶対値	\(O(1)\)
a + b / a - b / a * b / a / b	四則演算。整数を左右どちらにも置ける。除数は非零	\(O(\log M)\)
a += b / a -= b / a *= b / a /= b	四則演算の結果を代入	\(O(\log M)\)
++a / a++ / --a / a--	1 を加算／減算	\(O(\log M)\)
a == b / a != b / a < b / a <= b / a > b / a >= b	正確な比較	\(O(1)\)
a.floor() / floor(a)	数学的な切り下げ	\(O(1)\)
a.ceil() / ceil(a)	数学的な切り上げ	\(O(1)\)
a.inv()	逆数。a != 0	\(O(1)\)
a.pow(k) / pow(a,k)	非負整数乗。0 乗は 1	\(O(\log k\log M)\)
static_cast<bool>(a)	0 でないか	\(O(1)\)
static_cast<Int>(a)	0 方向への切り捨て	\(O(1)\)
static_cast<F>(a)	浮動小数点型 F への変換	\(O(1)\)
in >> a / out << a	整数または分数の入力／分子/分母 の出力	文字数に比例、入力の約分は別途 \(O(\log M)\)

Fraction<Int = std::int64_t> は有限の分数です。Int は64 bit以下の標準の符号付き整数型とします。 Fraction<> の別名は fraction。常に約分し、分母は正、0 は 0/1 で保持します。 コンストラクタの引数は Int 型です。整数1個からの変換もできます。

四則演算・複合代入・全比較・単項符号・++・-- に対応します。整数を左右どちらにも置けます。 numerator()・denominator() で分子・分母を取得します。 floor()・ceil() は数学的な切り下げ・切り上げ、static_cast<Int>(a) は0方向への切り捨てです。 float・double・long double には明示的に変換できます。 abs(a)・floor(a)・ceil(a)・pow(a, k) も使えます。k は std::uint64_t で、0乗は1です。 inv() は約分済みの分子と分母を入れ替え、符号だけを整えます。

分母0、0による除算・逆数は不可です。約分後の分子と正の分母が Int に収まることを必要とします。 比較と四則演算の途中の積には幅の広い整数型を使うため、中間値が Int を超えても、約分後に収まる結果を扱えます。 INT64_MIN を分子に持つ値も扱えますが、その符号反転・絶対値や、正の分母が表現範囲を超える逆数は不可です。

ストリーム出力は常に 分子/分母、入力は a/b または整数です。分子と / の間に空白は置きません。 入力の整数は Int に収まる必要があり、分母0・表現不能な値・書式エラーでは failbit を立て、読み込み先を変更しません。

型の最大絶対値を \(M\) として、構築と四則演算は \(O(\log M)\)、比較・値取得・丸めは \(O(1)\)、pow(k) は \(O(\log k\log M)\) 時間です。追加空間は \(O(1)\) です。

コード

#ifndef FRACTION_HPP
#define FRACTION_HPP

#include <cassert>
#include <compare>
#include <concepts>
#include <cstdint>
#include <istream>
#include <limits>
#include <numeric>
#include <ostream>
#include <type_traits>

template <std::signed_integral Int = std::int64_t>
requires (sizeof(Int) <= sizeof(std::int64_t))
class [[gnu::warn_unused]] Fraction {
	using U = std::make_unsigned_t<Int>;
	using W = std::conditional_t<(sizeof(Int) <= 4), std::int64_t, __int128_t>;
	Int num = 0, den = 1;
	static constexpr U magnitude(Int x) { return x < 0 ? U(0) - U(x) : U(x); }
	static constexpr U gcd(U a, U b) {
		if (a == 1 || b == 1) return 1;
		return std::gcd(a, b);
	}
	static constexpr Fraction reduced(W n, W d) {
		assert(std::numeric_limits<Int>::min() <= n && n <= std::numeric_limits<Int>::max());
		assert(0 < d && d <= std::numeric_limits<Int>::max());
		Fraction result;
		result.num = static_cast<Int>(n);
		result.den = static_cast<Int>(d);
		return result;
	}
	static constexpr Int divide(Int n, U d) {
		if (d > U(std::numeric_limits<Int>::max())) return -1;
		return n / static_cast<Int>(d);
	}
	constexpr bool assign(Int n, Int d) {
		if (!d) return false;
		if (!n) { num = 0, den = 1; return true; }
		U a = magnitude(n), b = magnitude(d), g = gcd(a, b);
		a /= g, b /= g;
		bool negative = (n < 0) != (d < 0);
		if (b > U(std::numeric_limits<Int>::max())
			|| a > U(std::numeric_limits<Int>::max()) + U(negative)) return false;
		num = negative ? Int(-static_cast<Int>(a - 1) - 1) : static_cast<Int>(a);
		den = static_cast<Int>(b);
		return true;
	}
	template <bool subtract>
	constexpr Fraction add(Fraction b) const {
		if (!b.num) return *this;
		if (!num) {
			if constexpr (subtract) return -b;
			else return b;
		}
		U g = gcd(U(den), U(b.den));
		Int left = den / static_cast<Int>(g), right = b.den / static_cast<Int>(g);
		W n;
		if constexpr (subtract) n = W(num) * right - W(b.num) * left;
		else n = W(num) * right + W(b.num) * left;
		if (!n) return {};
		U h = 1;
		if (g > 1) {
			U remainder;
			if (std::numeric_limits<Int>::min() <= n && n <= std::numeric_limits<Int>::max())
				remainder = magnitude(static_cast<Int>(n)) % g;
			else {
				W r = n % W(g);
				remainder = static_cast<U>(r < 0 ? -r : r);
			}
			h = gcd(remainder, g);
		}
		if (h > 1) n /= W(h);
		return reduced(n, W(left) * (b.den / static_cast<Int>(h)));
	}

  public:
	constexpr Fraction() = default;
	constexpr Fraction(Int n) : num(n) {}
	constexpr Fraction(Int n, Int d) {
		bool valid = assign(n, d);
		assert(valid);
		(void)valid;
	}
	[[nodiscard]] constexpr Int numerator() const { return num; }
	[[nodiscard]] constexpr Int denominator() const { return den; }
	[[nodiscard]] constexpr Fraction operator+() const { return *this; }
	[[nodiscard]] constexpr Fraction operator-() const { return reduced(-W(num), den); }
	[[nodiscard]] constexpr bool operator==(const Fraction &) const = default;
	[[nodiscard]] constexpr std::strong_ordering operator<=>(Fraction b) const { return W(num) * b.den <=> W(b.num) * den; }
	[[nodiscard]] friend constexpr Fraction operator+(Fraction a, Fraction b) { return a.template add<false>(b); }
	[[nodiscard]] friend constexpr Fraction operator-(Fraction a, Fraction b) { return a.template add<true>(b); }
	[[nodiscard]] friend constexpr Fraction operator*(Fraction a, Fraction b) {
		if (!a.num || !b.num) return {};
		U g = gcd(magnitude(a.num), U(b.den)), h = gcd(magnitude(b.num), U(a.den));
		return reduced(W(divide(a.num, g)) * divide(b.num, h),
			W(a.den / static_cast<Int>(h)) * (b.den / static_cast<Int>(g)));
	}
	[[nodiscard]] friend constexpr Fraction operator/(Fraction a, Fraction b) {
		assert(b.num != 0);
		if (!a.num) return {};
		U g = gcd(magnitude(a.num), magnitude(b.num)), h = gcd(U(a.den), U(b.den));
		W n = W(divide(a.num, g)) * (b.den / static_cast<Int>(h));
		W d = W(a.den / static_cast<Int>(h)) * divide(b.num, g);
		if (d < 0) n = -n, d = -d;
		return reduced(n, d);
	}
	constexpr Fraction &operator+=(Fraction b) { return *this = *this + b; }
	constexpr Fraction &operator-=(Fraction b) { return *this = *this - b; }
	constexpr Fraction &operator*=(Fraction b) { return *this = *this * b; }
	constexpr Fraction &operator/=(Fraction b) { return *this = *this / b; }
	constexpr Fraction &operator++() { return *this += 1; }
	constexpr Fraction &operator--() { return *this -= 1; }
	constexpr Fraction operator++(int) { Fraction old = *this; ++*this; return old; }
	constexpr Fraction operator--(int) { Fraction old = *this; --*this; return old; }
	[[nodiscard]] constexpr explicit operator bool() const { return num != 0; }
	[[nodiscard]] constexpr explicit operator Int() const { return num / den; }
	template <std::floating_point F>
	[[nodiscard]] constexpr explicit operator F() const { return F(num) / F(den); }
	[[nodiscard]] constexpr Int floor() const { return num / den - (num % den < 0); }
	[[nodiscard]] constexpr Int ceil() const { return num / den + (num % den > 0); }
	[[nodiscard]] constexpr Fraction inv() const {
		assert(num != 0);
		return num < 0 ? reduced(-W(den), -W(num)) : reduced(den, num);
	}
	[[nodiscard]] constexpr Fraction pow(std::uint64_t k) const {
		if (!k) return Fraction(1);
		if (!num) return *this;
		Fraction result(1), base = *this;
		auto multiply = [](Fraction a, Fraction b) { return reduced(W(a.num) * b.num, W(a.den) * b.den); };
		while (k) {
			if (k & 1) result = multiply(result, base);
			k >>= 1;
			if (k) base = multiply(base, base);
		}
		return result;
	}
	[[nodiscard]] friend constexpr Fraction abs(Fraction x) { return x.num < 0 ? -x : x; }
	[[nodiscard]] friend constexpr Int floor(Fraction x) { return x.floor(); }
	[[nodiscard]] friend constexpr Int ceil(Fraction x) { return x.ceil(); }
	[[nodiscard]] friend constexpr Fraction pow(Fraction x, std::uint64_t k) { return x.pow(k); }
	friend std::ostream &operator<<(std::ostream &os, Fraction x) {
		return os << std::int64_t(x.num) << '/' << std::int64_t(x.den);
	}
	friend std::istream &operator>>(std::istream &is, Fraction &x) {
		std::int64_t n, d = 1;
		if (!(is >> n)) return is;
		if (!is.eof() && is.peek() == '/') {
			is.get();
			if (!(is >> d)) return is;
		}
		Fraction value;
		if (!d || n < std::numeric_limits<Int>::min() || n > std::numeric_limits<Int>::max()
			|| d < std::numeric_limits<Int>::min() || d > std::numeric_limits<Int>::max()
			|| !value.assign(static_cast<Int>(n), static_cast<Int>(d))) {
			is.setstate(std::ios::failbit);
			return is;
		}
		x = value;
		return is;
	}
};

using fraction = Fraction<>;

#endif

Back to top page