分数ライブラリをRustで実装しました

概要

競技プログラミングで分数を扱うとき、浮動小数点を使うと誤差が乗るので基本的には避けたいです。
一方で、どうしても割り算を正確に持ちたい、比較を厳密にしたいといった場面があり、そのときは分子・分母を整数で持つ分数ライブラリ が便利です。

自分も以前から使い回していた実装があったのですが、かなり昔に雑に作ったものだったためバグが残っており、コンテスト中に場当たり的に直すという最悪の運用になっていました。(実装自体は素直なのですぐに直せるのがとても悪い)

そこで、改めて整理して実装し直しました。
ある程度「見せられる」形になったので、記事として残しておきます。

このライブラリでできること

Frac は 整数型 T 上の有理数を表します（T: Integer + Signed + Copy）

• 正規化された分数の保持
  • gcd で約分し、分母は常に非負になるように正規化します。
• 四則演算
• AddAssign などの代入演算（+= など）にも対応
• Eq / Ord を実装しているので BTreeSet やソートが可能
• 無限大の表現
  • pinf() / minf() を持ち、分母 0 を「無限大」として扱います

実装

use std::{
    cmp::Ordering,
    ops::{Add, AddAssign, Div, DivAssign, Mul, MulAssign, Neg, Sub, SubAssign},
};

use num_integer::Integer;
use num_traits::Signed;

#[derive(Debug, Clone, Copy, Hash)]
pub struct Frac<T> {
    a: T,
    b: T,
}

impl<T> Frac<T>
where
    T: Integer + Signed + Copy,
{
    pub fn new(a: T, b: T) -> Self {
        let mut f = Self { a, b };
        f.normalize();
        f
    }

    pub fn from_int(x: T) -> Self {
        Self::new(x, T::one())
    }

    pub fn get(&self) -> (T, T) {
        (self.a, self.b)
    }

    pub fn zero() -> Self {
        Self::new(T::zero(), T::one())
    }

    pub fn pinf() -> Self {
        Self::new(T::one(), T::zero())
    }

    pub fn minf() -> Self {
        Self::new(-T::one(), T::zero())
    }

    pub fn inv(&self) -> Self {
        if self.a.is_zero() {
            return Self::new(T::one(), T::zero());
        }
        Self::new(self.b, self.a)
    }

    fn normalize(&mut self) {
        if self.b.is_zero() {
            if self.a.is_zero() {
                self.a = T::one();
            } else {
                self.a = self.a.signum();
            }
            return;
        }
        let g = self.a.gcd(&self.b);
        self.a = self.a / g;
        self.b = self.b / g;

        if self.b.is_negative() {
            self.a = -self.a;
            self.b = -self.b;
        }
    }
    pub fn is_inf(&self) -> bool {
        self.b.is_zero() && !self.a.is_zero()
    }
    pub fn is_pinf(&self) -> bool {
        self.b.is_zero() && self.a.is_positive()
    }
    pub fn is_minf(&self) -> bool {
        self.b.is_zero() && self.a.is_negative()
    }

    pub fn is_zero(&self) -> bool {
        let a = self.a;
        let b = self.b;
        a.is_zero() && b.is_one()
    }
    pub fn is_positive(&self) -> bool {
        if self.is_pinf() {
            return true;
        }
        if self.is_minf() {
            return false;
        }
        self.a.is_positive()
    }
    pub fn is_negative(&self) -> bool {
        if self.is_minf() {
            return true;
        }
        if self.is_pinf() {
            return false;
        }
        self.a.is_negative()
    }
}

impl<T> From<T> for Frac<T>
where
    T: Integer + Signed + Copy,
{
    fn from(value: T) -> Self {
        Self::from_int(value)
    }
}

impl<T> Neg for Frac<T>
where
    T: Integer + Signed + Copy,
{
    type Output = Self;
    fn neg(self) -> Self::Output {
        let a = self.a;
        let b = self.b;
        Self::new(-a, b)
    }
}

// ── Frac<T> と Frac<T>の計算 ────────────────────────────────────────
impl<T> Add for Frac<T>
where
    T: Integer + Signed + Copy,
{
    type Output = Self;
    fn add(self, rhs: Self) -> Self::Output {
        if self.is_inf() || rhs.is_inf() {
            if self.is_pinf() && rhs.is_minf() || self.is_minf() && rhs.is_pinf() {
                panic!("indeterminate form: +inf + -inf");
            }
            return if self.is_inf() { self } else { rhs };
        }
        let (a, b) = (self.a, self.b);
        let (c, d) = (rhs.a, rhs.b);

        let g = b.gcd(&d);
        let b1 = b / g; // b'
        let d1 = d / g; // d'

        let num = a * d1 + c * b1;
        let den = b1 * d;

        let g2 = num.gcd(&g);
        Self::new(num / g2, den / g2)
    }
}

impl<T> Sub for Frac<T>
where
    T: Integer + Signed + Copy,
{
    type Output = Self;
    fn sub(self, rhs: Self) -> Self::Output {
        self + (-rhs)
    }
}

impl<T> Mul for Frac<T>
where
    T: Integer + Signed + Copy,
{
    type Output = Self;
    fn mul(self, rhs: Self) -> Self::Output {
        if self.is_inf() || rhs.is_inf() {
            if (!self.is_inf() && self.a.is_zero()) || (!rhs.is_inf() && rhs.a.is_zero()) {
                panic!("indeterminate form: 0 * inf");
            }
            let s = self.a.signum() * rhs.a.signum();
            return Self::new(s, T::zero());
        }

        let (mut a, mut b) = (self.a, self.b);
        let (mut c, mut d) = (rhs.a, rhs.b);

        let g1 = a.gcd(&d);
        a = a / g1;
        d = d / g1;

        let g2 = c.gcd(&b);
        c = c / g2;
        b = b / g2;

        Self::new(a * c, b * d)
    }
}

impl<T> Div for Frac<T>
where
    T: Integer + Signed + Copy,
{
    type Output = Self;
    fn div(self, rhs: Self) -> Self::Output {
        self * rhs.inv()
    }
}

impl<T> PartialEq for Frac<T>
where
    T: Integer + Signed + Copy,
{
    fn eq(&self, other: &Self) -> bool {
        self.a == other.a && self.b == other.b
    }
}
impl<T> Eq for Frac<T> where T: Integer + Signed + Copy {}

impl<T> PartialOrd for Frac<T>
where
    T: Integer + Signed + Copy,
{
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        if self.b.is_zero() && other.b.is_zero() {
            return Some(self.a.cmp(&other.a));
        }
        if self.b.is_zero() {
            return Some(if self.a.is_positive() {
                Ordering::Greater
            } else {
                Ordering::Less
            });
        }
        if other.b.is_zero() {
            return Some(if other.a.is_positive() {
                Ordering::Less
            } else {
                Ordering::Greater
            });
        }
        Some((self.a * other.b).cmp(&(other.a * self.b)))
    }
}

impl<T> Ord for Frac<T>
where
    T: Integer + Signed + Copy,
{
    fn cmp(&self, other: &Self) -> Ordering {
        self.partial_cmp(other).unwrap()
    }
}

// ── Frac<T>とTの計算 ────────────────────────────────────────────────
impl<T> Add<T> for Frac<T>
where
    T: Integer + Signed + Copy,
{
    type Output = Self;
    fn add(self, rhs: T) -> Self::Output {
        let rhs = Self::from_int(rhs);
        self + rhs
    }
}

impl<T> Sub<T> for Frac<T>
where
    T: Integer + Signed + Copy,
{
    type Output = Self;
    fn sub(self, rhs: T) -> Self::Output {
        let rhs = Self::from_int(rhs);
        self - rhs
    }
}

impl<T> Mul<T> for Frac<T>
where
    T: Integer + Signed + Copy,
{
    type Output = Self;
    fn mul(self, rhs: T) -> Self::Output {
        let rhs = Self::from_int(rhs);
        self * rhs
    }
}

impl<T> Div<T> for Frac<T>
where
    T: Integer + Signed + Copy,
{
    type Output = Self;
    fn div(self, rhs: T) -> Self::Output {
        let rhs = Self::from_int(rhs);
        let inv = rhs.inv();
        self * inv
    }
}

impl<T> PartialEq<T> for Frac<T>
where
    T: Integer + Signed + Copy,
{
    fn eq(&self, other: &T) -> bool {
        let other = Self::from_int(*other);
        self.a == other.a && self.b == other.b
    }
}

impl<T> PartialOrd<T> for Frac<T>
where
    T: Integer + Signed + Copy,
{
    fn partial_cmp(&self, other: &T) -> Option<Ordering> {
        let other = Self::from_int(*other);
        if self.b.is_zero() && other.b.is_zero() {
            return Some(self.a.cmp(&other.a));
        }
        if self.b.is_zero() {
            return Some(if self.a.is_positive() {
                Ordering::Greater
            } else {
                Ordering::Less
            });
        }
        if other.b.is_zero() {
            return Some(if other.a.is_positive() {
                Ordering::Less
            } else {
                Ordering::Greater
            });
        }
        Some((self.a * other.b).cmp(&(other.a * self.b)))
    }
}

// Assign関連
impl<T> AddAssign for Frac<T>
where
    T: Integer + Signed + Copy,
{
    fn add_assign(&mut self, rhs: Self) {
        let t = self.to_owned() + rhs;
        *self = t;
    }
}
impl<T> SubAssign for Frac<T>
where
    T: Integer + Signed + Copy,
{
    fn sub_assign(&mut self, rhs: Self) {
        *self += -rhs;
    }
}
impl<T> MulAssign for Frac<T>
where
    T: Integer + Signed + Copy,
{
    fn mul_assign(&mut self, rhs: Self) {
        let t = self.to_owned() * rhs;
        *self = t
    }
}
impl<T> DivAssign for Frac<T>
where
    T: Integer + Signed + Copy,
{
    fn div_assign(&mut self, rhs: Self) {
        let inv = rhs.inv();
        *self *= inv
    }
}
impl<T> AddAssign<T> for Frac<T>
where
    T: Integer + Signed + Copy,
{
    fn add_assign(&mut self, rhs: T) {
        let rhs = Self::from_int(rhs);
        *self += rhs;
    }
}
impl<T> SubAssign<T> for Frac<T>
where
    T: Integer + Signed + Copy,
{
    fn sub_assign(&mut self, rhs: T) {
        let rhs = Self::from_int(rhs);
        *self -= rhs;
    }
}
impl<T> MulAssign<T> for Frac<T>
where
    T: Integer + Signed + Copy,
{
    fn mul_assign(&mut self, rhs: T) {
        let rhs = Self::from_int(rhs);
        *self *= rhs
    }
}
impl<T> DivAssign<T> for Frac<T>
where
    T: Integer + Signed + Copy,
{
    fn div_assign(&mut self, rhs: T) {
        let rhs = Self::from_int(rhs);
        *self /= rhs
    }
}

各APIの概要と計算量

T の演算コストは定数とし、gcd の計算量は O(log M)（M は値の大きさ）程度として扱います。
また、四則演算では gcd を数回呼ぶため、概ねその分だけ log が乗ります。

API / 演算	内容	計算量（目安）	備考
Frac::new(a, b)	生成して正規化	O(log M)	normalize() が gcd を使う
Frac::from_int(x) / From<T>	整数から生成	O(1)	実際は new(x, 1)
get()	(a, b) を返す	O(1)
zero()	0/1 を返す	O(1)
pinf() / minf()	±inf を返す	O(1)	±1/0
inv()	逆数	O(log M)	new(b, a) を作るため正規化あり
is_inf() / is_pinf() / is_minf()	無限大判定	O(1)	分母 0 を見る
is_zero()	0 判定	O(1)	正規化済み前提で 0/1 を見る
is_positive() / is_negative()	符号判定	O(1)	±inf の場合も考慮
-x (Neg)	符号反転	O(log M)	new(-a, b) を呼ぶので正規化あり
x + y (Add)	加算	O(log M)	gcd を複数回。無限大の分岐あり
x - y (Sub)	減算	O(log M)	x + (-y)
x * y (Mul)	乗算	O(log M)	事前に約分してオーバーフローを減らす設計
x / y (Div)	除算	O(log M)	x * y.inv()
cmp / partial_cmp	比較	O(1)	※a*d 等の乗算は発生
+=, -=, *=, /=	代入演算	元の演算と同程度	いったん演算して代入

注意点

• Frac::new(0, 0) は +inf 扱いになります
  • 実装上、分母 0 のとき a を signum()（ただし a=0 の場合は a=1）に寄せるため、(0,0) は (1,0) に正規化されます。
• 不定形は panic! します
  • +inf + -inf（またはその逆）
  • 0 * inf（有限の 0 と無限大の積）
• 分母 0 を「無限大」として扱う設計なので、用途によっては「未定義」や「NaN」も欲しくなるかもしれません。お好みで実装を修正してください。

使い方

あまりいい問題が見つからなかったのですが、例えば以下の問題。
想定解もa1 * (a2 + b2) > a2 * (a1 + b1)をキーにしてソートすればいいだけで、あまりお得感がないのですが、このライブラリを使うことで言われていることを素直にやるだけで正解できます。

fn main() {
    input! {
        n: usize,
        mut ab: [(isize, isize); n]
    }
    let ans = ab
        .iter()
        .enumerate()
        .map(|(idx, &(a, b))| (Frac::new(a, a + b), idx + 1))
        .sorted_by_key(|&e| (Reverse(e.0), e.1))
        .map(|e| e.1)
        .join(" ");
    println!("{}", ans);
}

終わりに

より良い実装があればおしえてください！！