Rational — 多倍長有理数
概要
Rational は calx の任意精度有理数型である。
内部表現は (分子 Int, 分母 Int) の対で、値 $x$ を次のように表す。
$$x = \frac{p}{q}, \quad q > 0, \quad \gcd(p, q) = 1$$
分母は常に正、分子と分母は常に約分済みの状態が維持される。
分母がゼロの場合は NaN として扱われる。
- 任意精度 — 分子・分母ともに
Int なので桁数に制限なし
- 自動約分 — 演算のたびに GCD で約分し、正規化された状態を維持
- NaN 安全 — ゼロ除算は NaN を返し、クラッシュしない
- Int/int との混合演算 —
Rational + Int, Rational * int が自然に書ける
コンストラクタ
| シグネチャ | 説明 |
|---|
Rational() | デフォルト構築。値は 0/1 |
Rational(int num, int den = 1) | int の分子/分母から構築 (自動約分) |
Rational(const Int& num) | Int から構築 (分母 = 1) |
Rational(const Int& num, const Int& den, bool doReduce = true) | Int の分子/分母から構築 |
Rational(Int&& num, Int&& den, bool doReduce = true) | ムーブ版 |
Rational(std::string_view str, int base = 10) | 文字列 "p/q" 形式から構築 |
Rational(double value) | double から正確な有理数に変換 |
Rational(float value) | float から正確な有理数に変換 |
Rational(const Float& value) | 多倍長浮動小数点から正確な有理数に変換 |
doReduce = false を指定すると約分をスキップする (呼び出し側が既に約分済みであることを保証する場合)。
アクセサ
| メンバ関数 | 説明 |
|---|
const Int& numerator() const | 分子を返す |
const Int& denominator() const | 分母を返す (常に正) |
friend void swap(Rational& a, Rational& b) noexcept | 2 つの Rational オブジェクトを交換 |
算術演算子
四則演算
| 演算子 | 説明 |
|---|
Rational + Rational | 加算 ($\frac{a}{b} + \frac{c}{d} = \frac{ad+bc}{bd}$, 約分) |
Rational - Rational | 減算 |
Rational * Rational | 乗算 ($\frac{a}{b} \times \frac{c}{d} = \frac{ac}{bd}$, 約分) |
Rational / Rational | 除算 ($\frac{a}{b} \div \frac{c}{d} = \frac{ad}{bc}$, 約分) |
Rational % Rational | 剰余 |
Int および int との混合演算もすべてサポート:
Rational + Int, Int + RationalRational * int, int * Rational- 複合代入:
+=, -=, *=, /=
その他の演算
| 演算 | 説明 |
|---|
-r | 符号反転 |
++r, r++ | インクリメント |
--r, r-- | デクリメント |
r.pow(n) | $r^n$ (int 指数) |
pow(r, e) | $r^e$ (Int 指数) |
r << n | $r \times 2^n$ |
r >> n | $r / 2^n$ |
比較演算子
C++20 三方比較 (<=>) をサポート。std::partial_ordering を返す (NaN を考慮)。
| 比較 | 説明 |
|---|
Rational <=> Rational | 三方比較 |
Rational == Rational | 等値比較 |
Rational <=> Int | Int との比較 |
Rational <=> int | int との比較 |
状態確認
| メンバ関数 | 説明 |
|---|
isZero() | 値が 0 か |
isNonZero() | 値が 0 でないか |
isPositive() | 値が正か |
isNegative() | 値が負か |
isNonPositive() | 値が 0 以下か |
isNonNegative() | 値が 0 以上か |
isOne() | 値が 1 か |
isInteger() | 分母が 1 か (整数値) |
isNaN() | NaN 状態か |
reduce() | 手動で約分を実行し正規化する。コンストラクタの doReduce=false で約分を省略した場合に、後から呼び出す。変更があれば true を返す |
数学関数
| 関数 | 説明 |
|---|
abs(x) | 絶対値 $|x|$ |
inv(x) | 逆数 $1/x$ |
square(x) | $x^2$ |
sgn(x) | 符号 ($-1, 0, 1$) |
floor(x) | $\lfloor x \rfloor$ (Int を返す) |
ceil(x) | $\lceil x \rceil$ (Int を返す) |
trunc(x) | ゼロ方向の切り捨て (Int を返す) |
round(x) | 四捨五入 (Int を返す) |
frac(x) | 小数部分 $x - \lfloor x \rfloor$ |
height(x) | 高さ $\max(|p|, |q|)$ |
gcd(x, y) | 有理数の GCD |
mediant(a, b) | 中間分数 (mediant) $\frac{p_a + p_b}{q_a + q_b}$ |
r.doubled() | $2r$ |
r.halved() | $r/2$ |
r.reciprocal() | 逆数 $q/p$。$O(1)$。ゼロの逆数は NaN |
conj(x) | 共役 (実有理数では自身を返す。Complex<Rational> との互換性のために存在) |
連分数
| 関数 | 説明 |
|---|
r.toContinuedFraction() | 連分数展開 $[a_0; a_1, a_2, \ldots]$ を返す |
Rational::fromContinuedFraction(cf) | 連分数から Rational を復元 |
Rational r(355, 113);
auto cf = r.toContinuedFraction(); // [3; 7, 16]
Rational r2 = Rational::fromContinuedFraction(cf); // 355/113
数論関数
| 関数 | 説明 |
|---|
harmonicNumber(n) | 調和数 $H_n = 1 + \frac{1}{2} + \cdots + \frac{1}{n}$ |
dedekindSum(h, k) | デデキント和 $s(h, k)$ |
reconstructRational(a, m, N, D) | $a \bmod m$ から $p/q$ を復元 ($|p| \le N, 0 < q \le D$) |
mod(x, m) | 有理数の mod: $\frac{p}{q} \bmod m = p \cdot q^{-1} \bmod m$ |
有理数列挙
| 関数 | 説明 |
|---|
nextMinimal(x) | Stern-Brocot 順で次の正有理数 |
nextCalkinWilf(x) | Calkin-Wilf 列で次の正有理数 |
fareyNeighbors(x, Q) | Farey 数列 $F_Q$ における左右近傍 |
simplestBetween(a, b) | 開区間 $(a, b)$ 内の最小高さ有理数 |
数学定数
以下の定数は Rational 値として正確に計算される。計算済みの値はスレッドセーフな静的キャッシュに保存される。
| 関数 | 説明 |
|---|
bernoulli(n) | Bernoulli 数 $B_n$ (標準再帰式) |
stirlingCoefficient(k) | Stirling 近似の係数 $c_k$ |
Rational b0 = bernoulli(0); // 1
Rational b1 = bernoulli(1); // -1/2
Rational b2 = bernoulli(2); // 1/6
Rational b4 = bernoulli(4); // -1/30
Rational b6 = bernoulli(6); // 1/42
変換
| 関数 | 説明 |
|---|
toDouble() | double に変換 |
toFloat() | float に変換 |
toMpFloat(precision) | Float に変換 (指定精度) |
toString(base) | "p/q" 形式の文字列 |
toDecimal(digits) | 10 進小数文字列 (指定桁数) |
explicit operator int() | int に変換 (切り捨て) |
explicit operator double() | double に変換 |
Rational& operator=(double value) | double からの代入 |
Rational& operator=(float value) | float からの代入 |
ストリーム入出力
Rational r(22, 7);
std::cout << r; // 出力: 22/7
Rational s;
std::cin >> s; // 入力: "3/4" → Rational(3, 4)
使用例
#include <math/core/mp/Rational.hpp>
#include <iostream>
using namespace calx;
int main() {
// 基本的な四則演算 (自動約分)
Rational a(1, 3); // 1/3
Rational b(1, 6); // 1/6
std::cout << a + b << std::endl; // 1/2
// Bernoulli 数
for (int n = 0; n <= 10; n += 2)
std::cout << "B(" << n << ") = " << bernoulli(n) << std::endl;
// 連分数展開
Rational pi_approx(355, 113);
auto cf = pi_approx.toContinuedFraction(); // [3; 7, 16]
// 調和数
Rational h10 = harmonicNumber(10); // 7381/2520
std::cout << "H(10) = " << h10 << " = " << h10.toDecimal(15) << std::endl;
// NaN 安全
Rational nan = Rational(1, 0);
std::cout << nan << std::endl; // NaN
}