Dyadic rational, surreal number （二進分数・固定小数点数，Conway の構成）
(number/dyadic_rational.hpp)

View this file on GitHub
Last update: 2022-01-30 12:05:36+09:00
Include: #include "number/dyadic_rational.hpp"
Link: https://atcoder.jp/contests/abc229/submissions/28887690

分母が二冪の有理数 DyadicRational<Int, Uint = unsigned long long> の実装，また超現実数の構成法に基づく $\{ l \mid r \}$ の計算．組合せゲーム理論などへの応用がある．

Int が整数部分を表すための符号付整数型で int や long long の利用を想定，Uint が小数部分を表すための符号なし整数型で unsigned や unsigned long long の利用を想定（__uint128_t も動くかもしれない）．メンバ変数 integ, frac がそれぞれ整数部分と小数部分に対応し，

$\displaystyle x = \mathrm{integ} + \frac{\mathrm{frac}}{2^\mathrm{FracLen}} $

がこのクラスのインスタンスが表す有理数 $x$ である．実装の制約上分母のオーダーは（Uint = unsigned long long の場合）$2^{63}$ が上限となる．

使用方法

`DyadicRational<Int>(Int x)`

コンストラクタ．整数 x に対応する元を生成する．

`double to_double()`

インスタンスが表す有理数 $x$ を double 型に変換．

`DyadicRational<Int> right()`

Surreal number （超現実数）の構成過程を表す木において，現在の値 $x$ の右側の子の値を返す．

`DyadicRational<Int> left()`

right() とは逆に，現在の値 $x$ の左側の子の値を返す．

`DyadicRational<Int> DyadicRational<Int>::surreal(DyadicRational<Int> l, DyadicRational<Int> r)`

$l < r$ を満たす二進分数 $l$, $r$ について，$l < x < r$ を満たし surreal number の構成過程を表す木で根（$0$）に最も近い要素（Conway の記法に基づくと $\{ l \mid r \}$）の値を返す．$l < r$ を満たさない場合 runtime error となる．

現在は根から一歩ずつ right() または left() で探索していく実装になっているが，場合分けと bit 演算を頑張れば $O(1)$ になると思われる．

問題例

AtCoder Beginner Contest 229 H - Advance or Eat

リンク

組合せゲーム理論入門(1) 組合せゲーム理論の観点からの解説．
解説 - NECプログラミングコンテスト2021(AtCoder Beginner Contest 229) 非不偏ゲーム（Partisan Game）の問題例とその解き方．
- 提出 #27486895 - NECプログラミングコンテスト2021(AtCoder Beginner Contest 229) Nyaan さんの実装．

Code

#include <cassert>
#include <limits>
#include <type_traits>

// Dyadic rational, surreal numbers （超現実数）
// https://atcoder.jp/contests/abc229/submissions/28887690
template <class Int, class Uint = unsigned long long> struct DyadicRational {
    Int integ; // 整数部分
    Uint frac; // 小数部分の分子

    static constexpr int FracLen = std::numeric_limits<Uint>::digits - 1; // 2^63
    static constexpr Uint denom = Uint(1) << FracLen;                     // 小数部分の分母

    DyadicRational(Int x = 0) : integ(x), frac(0) {
        static_assert(
            0 < FracLen and FracLen < std::numeric_limits<Uint>::digits, "FracLen value error");
        static_assert(std::is_signed<Int>::value == true, "Int must be signed");
    }
    static DyadicRational _construct(Int x, Uint frac_) {
        DyadicRational ret(x);
        ret.frac = frac_;
        return ret;
    }
    double to_double() const { return integ + double(frac) / denom; }

    // static DyadicRational from_rational(Int num, int lg_den);
    bool operator==(const DyadicRational &r) const { return integ == r.integ and frac == r.frac; }
    bool operator!=(const DyadicRational &r) const { return integ != r.integ or frac != r.frac; }
    bool operator<(const DyadicRational &r) const {
        return integ != r.integ ? integ < r.integ : frac < r.frac;
    }
    bool operator<=(const DyadicRational &r) const { return (*this == r) or (*this < r); }
    bool operator>(const DyadicRational &r) const { return r < *this; }
    bool operator>=(const DyadicRational &r) const { return r <= *this; }

    DyadicRational operator+(const DyadicRational &r) const {
        auto i = integ + r.integ;
        auto f = frac + r.frac;
        if (f >= denom) ++i, f -= denom; // overflow
        return DyadicRational::_construct(i, f);
    }
    DyadicRational operator-(const DyadicRational &r) const {
        auto i = integ - r.integ;
        auto f = frac - r.frac;
        if (f > denom) --i, f += denom; // overflow
        return DyadicRational::_construct(i, f);
    }
    DyadicRational operator-() const { return DyadicRational() - *this; }
    DyadicRational &operator+=(const DyadicRational &r) { return *this = *this + r; }

    DyadicRational right() const {
        if (frac == 0) {
            if (integ >= 0) {
                return DyadicRational(integ + 1);
            } else {
                return DyadicRational::_construct(integ, Uint(1) << (FracLen - 1));
            }
        }
        int d = __builtin_ctzll(frac);
        return DyadicRational::_construct(integ, frac ^ (Uint(1) << (d - 1)));
    }
    DyadicRational left() const {
        if (frac == 0) {
            if (integ <= 0) {
                return DyadicRational(integ - 1);
            } else {
                return DyadicRational::_construct(integ - 1, Uint(1) << (FracLen - 1));
            }
        }
        int d = __builtin_ctzll(frac);
        return DyadicRational::_construct(integ, frac ^ (Uint(3) << (d - 1)));
    }

    // Surreal number { l | r }
    static DyadicRational surreal(const DyadicRational &l, const DyadicRational &r) {
        assert(l < r);
        DyadicRational x(0);
        if (l.integ > 0) x = DyadicRational(l.integ);
        if (r.integ < 0) x = DyadicRational(r.integ);
        while (true) {
            if (x <= l) {
                x = x.right();
            } else if (x >= r) {
                x = x.left();
            } else {
                break;
            }
        }
        return x;
    }
    template <class OStream> friend OStream &operator<<(OStream &os, const DyadicRational &x) {
        return os << x.to_double();
    }
};
// using dyrational = DyadicRational<long long>;

#line 1 "number/dyadic_rational.hpp"
#include <cassert>
#include <limits>
#include <type_traits>

// Dyadic rational, surreal numbers （超現実数）
// https://atcoder.jp/contests/abc229/submissions/28887690
template <class Int, class Uint = unsigned long long> struct DyadicRational {
    Int integ; // 整数部分
    Uint frac; // 小数部分の分子

    static constexpr int FracLen = std::numeric_limits<Uint>::digits - 1; // 2^63
    static constexpr Uint denom = Uint(1) << FracLen;                     // 小数部分の分母

    DyadicRational(Int x = 0) : integ(x), frac(0) {
        static_assert(
            0 < FracLen and FracLen < std::numeric_limits<Uint>::digits, "FracLen value error");
        static_assert(std::is_signed<Int>::value == true, "Int must be signed");
    }
    static DyadicRational _construct(Int x, Uint frac_) {
        DyadicRational ret(x);
        ret.frac = frac_;
        return ret;
    }
    double to_double() const { return integ + double(frac) / denom; }

    // static DyadicRational from_rational(Int num, int lg_den);
    bool operator==(const DyadicRational &r) const { return integ == r.integ and frac == r.frac; }
    bool operator!=(const DyadicRational &r) const { return integ != r.integ or frac != r.frac; }
    bool operator<(const DyadicRational &r) const {
        return integ != r.integ ? integ < r.integ : frac < r.frac;
    }
    bool operator<=(const DyadicRational &r) const { return (*this == r) or (*this < r); }
    bool operator>(const DyadicRational &r) const { return r < *this; }
    bool operator>=(const DyadicRational &r) const { return r <= *this; }

    DyadicRational operator+(const DyadicRational &r) const {
        auto i = integ + r.integ;
        auto f = frac + r.frac;
        if (f >= denom) ++i, f -= denom; // overflow
        return DyadicRational::_construct(i, f);
    }
    DyadicRational operator-(const DyadicRational &r) const {
        auto i = integ - r.integ;
        auto f = frac - r.frac;
        if (f > denom) --i, f += denom; // overflow
        return DyadicRational::_construct(i, f);
    }
    DyadicRational operator-() const { return DyadicRational() - *this; }
    DyadicRational &operator+=(const DyadicRational &r) { return *this = *this + r; }

    DyadicRational right() const {
        if (frac == 0) {
            if (integ >= 0) {
                return DyadicRational(integ + 1);
            } else {
                return DyadicRational::_construct(integ, Uint(1) << (FracLen - 1));
            }
        }
        int d = __builtin_ctzll(frac);
        return DyadicRational::_construct(integ, frac ^ (Uint(1) << (d - 1)));
    }
    DyadicRational left() const {
        if (frac == 0) {
            if (integ <= 0) {
                return DyadicRational(integ - 1);
            } else {
                return DyadicRational::_construct(integ - 1, Uint(1) << (FracLen - 1));
            }
        }
        int d = __builtin_ctzll(frac);
        return DyadicRational::_construct(integ, frac ^ (Uint(3) << (d - 1)));
    }

    // Surreal number { l | r }
    static DyadicRational surreal(const DyadicRational &l, const DyadicRational &r) {
        assert(l < r);
        DyadicRational x(0);
        if (l.integ > 0) x = DyadicRational(l.integ);
        if (r.integ < 0) x = DyadicRational(r.integ);
        while (true) {
            if (x <= l) {
                x = x.right();
            } else if (x >= r) {
                x = x.left();
            } else {
                break;
            }
        }
        return x;
    }
    template <class OStream> friend OStream &operator<<(OStream &os, const DyadicRational &x) {
        return os << x.to_double();
    }
};
// using dyrational = DyadicRational<long long>;

Dyadic rational, surreal number （二進分数・固定小数点数，Conway の構成） (number/dyadic_rational.hpp)

使用方法

DyadicRational<Int>(Int x)

double to_double()

DyadicRational<Int> right()

DyadicRational<Int> left()

DyadicRational<Int> DyadicRational<Int>::surreal(DyadicRational<Int> l, DyadicRational<Int> r)

問題例

リンク