Stern-Brocot tree
(Mylib/Number/Rational/stern_brocot_tree.cpp)

• View this file on GitHub
• Last update: 2021-04-23 23:44:44+09:00

Operations

Requirements

Notes

Problems

References

• http://www.prefield.com/algorithm/math/stern_brocot_tree.html
• https://en.wikipedia.org/wiki/Stern%E2%80%93Brocot_tree
• http://blue-jam.hatenablog.com/entry/20110306/1299415086

Verified with

• test/aoj/1208/main.test.cpp

Code

#pragma once
#include <cstdint>
#include <utility>

namespace haar_lib {
  template <typename Checker>
  void stern_brocot_tree(
      const Checker &check,
      int n,
      std::pair<int, int> &lower,
      std::pair<int, int> &upper,
      int64_t pl = 0, int64_t ql = 1, int64_t pr = 1, int64_t qr = 0) {
    int64_t pm = pl + pr;
    int64_t qm = ql + qr;

    if (pm > n or qm > n) return;

    auto t = check(pm, qm);

    if (t < 0) {
      lower = {pm, qm};
      stern_brocot_tree(check, n, lower, upper, pm, qm, pr, qr);
    } else if (t > 0) {
      upper = {pm, qm};
      stern_brocot_tree(check, n, lower, upper, pl, ql, pm, qm);
    } else {
      lower = {pm, qm};
      upper = {pm, qm};
    }
  }
}  // namespace haar_lib

#line 2 "Mylib/Number/Rational/stern_brocot_tree.cpp"
#include <cstdint>
#include <utility>

namespace haar_lib {
  template <typename Checker>
  void stern_brocot_tree(
      const Checker &check,
      int n,
      std::pair<int, int> &lower,
      std::pair<int, int> &upper,
      int64_t pl = 0, int64_t ql = 1, int64_t pr = 1, int64_t qr = 0) {
    int64_t pm = pl + pr;
    int64_t qm = ql + qr;

    if (pm > n or qm > n) return;

    auto t = check(pm, qm);

    if (t < 0) {
      lower = {pm, qm};
      stern_brocot_tree(check, n, lower, upper, pm, qm, pr, qr);
    } else if (t > 0) {
      upper = {pm, qm};
      stern_brocot_tree(check, n, lower, upper, pl, ql, pm, qm);
    } else {
      lower = {pm, qm};
      upper = {pm, qm};
    }
  }
}  // namespace haar_lib

Back to top page