Floyd's Cycle Finding Algorithm

cycle_finding.cpp

#include <optional>

// Let Catch provide main():
#define CATCH_CONFIG_MAIN
#include <catch2/catch.hpp>

constexpr auto cycle_finding(std::uint64_t n) -> std::optional<std::uint64_t> {
  // m.. カメの計算のあまり  p.. ウサギの計算の余り
  std::uint64_t m = 1, p = 1;

  // s.. 循環節の先頭小数桁位置  t.. 循環節の末尾小数桁位置
  std::uint64_t s = 0, t = 0;

  // カメとウサギの余りが一致するまでループを回す。
  do {
    m = m * 10 % n;
    p = p * 10 % n;
    p = p * 10 % n;
  } while (m != p);

  // 循環せず
  if (p == 0) {
    return std::nullopt;
  }

  // 循環節の先頭の検知
  s = 1, p = 1;
  while (m != p) {
    s = s + 1;
    m = m * 10 % n;
    p = p * 10 % n;
  }

  // 循環節の末尾の検知
  p = p * 10 % n;
  t = s;
  while (m != p) {
    t = t + 1;
    p = p * 10 % n;
  }

  return t - s + 1;
}

TEST_CASE("Cycle Finding Algorithm", "[cycle_finding]") {
  REQUIRE(cycle_finding(2) == std::nullopt);           // 1/2=0.5
  REQUIRE(cycle_finding(3) == std::make_optional(1));  // 1/3=0.(3)..
  REQUIRE(cycle_finding(4) == std::nullopt);           // 1/4=0.25
  REQUIRE(cycle_finding(5) == std::nullopt);           // 1/5=0.2
  REQUIRE(cycle_finding(6) == std::make_optional(1));  // 1/6=0.1(6)..
  REQUIRE(cycle_finding(7) == std::make_optional(6));  // 1/7=0.(142857)..
  REQUIRE(cycle_finding(8) == std::nullopt);           // 1/8=0.125
  REQUIRE(cycle_finding(9) == std::make_optional(1));  // 1/9=0.(1)..
  REQUIRE(cycle_finding(10) == std::nullopt);          // 1/10=0.1
}